4, 3.1. Постановка задачи линейного программирования (лп)

В общем виде задача линейного программирования ставится следующим образом.    

Максимизировать (минимизировать) функцию

                                          (3.1)

при ограничениях

                                       

где x_j,   –управляющие переменные или решения задачи  (3.1)–(3.4); b_j, a_ij,   – параметры, f – целевая функция или критерий эффективности задачи.

Функция (3.1) – линейная, ограничения (3.2)–(3.4) – линейные. Задача содержит п переменных и т ограничений.

Решить задачу линейного программирования  –  это значит найти значения управляющих переменных x_j,   удовлетворяющих ограничениям (3.2)–(3.4), при которых целевая функция (3.1) принимает минимальное или максимальное значение.

В зависимости от вида целевой функции (3.1) и ограничений  (3.2)–(3.4) можно выделить несколько типов задач линейного программирования или линейных моделей: общая линейная задача, транспортная задача, задача о назначениях.

В этой главе рассматривается общая линейная задача.

Приведем пример экономической задачи, сводящейся к линейной модели.

Пример 3.1

Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида. 2000 изделий второго вида и 2500 изделий третьего вида.

Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго – 3000 и третьего – 5000 единицами.

Для изготовления изделий используется 4 типа ресурсов. Количество ресурсов, потребляемых для производства одного изделия, общее количество ресурсов и прибыль от реализации каждого вида изделия заданы в табл. 3.1.

Таблица 3.1

 

 

Тип ресурсов	Вид изделий			Всего ресурсов
	1	2	3
1 2 3 4	500 1000 150 100	300 200 300 200	1000 100 200 400		25000000 30000000 20000000 40000000
Прибыль	20	40	50

Как организовать производство, чтобы:

1) обеспечить заказчиков;

2) не допустить затоваривания;

3) получить максимальную прибыль?

Построение математической модели 3.1.

Выполним последовательно этапы построения математической модели, сформулированные в пункте 3.    

1) Цель – получение максимальной прибыли.

2) Параметрами являются все числовые данные, приведенные в условии задачи.

3) Управляющие переменные:

x₁ – число изделий первого вида;

x₂ – число изделий второго вида;

x₃ – число изделий третьего вида;

4) Ограничения: обеспечить заказчиков, не превысить, запас ресурсов, не допустить затоваривания рынка.

В соответствии с этими ограничениями выпишем область допустимых решений задачи:

                          (3.5)

Первые три неравенства в системе (3.5) соответствуют спросу заказчиков. Неравенства с четвертого по шестое формализуют спрос на рынке. Последние четыре неравенства соответствуют ограничениям по ресурсам.

5)   Целевая функция или критерий эффективности задачи имеет вид

Р = 20х₁ + 40 х₂ + 50 х₃   max.                               (3.6)

В формуле буквой Р обозначена прибыль. Ее надо максимизировать. Каждое слагаемое определяет прибыль от производства изделий каждого вида соответственно в количествах х₁, х₂, х₃ .

(3.5)(3.6)— математическая модель поставленной задачи. Ограничения и целевая функция линейны по управляющим переменным, следовательно, данная модель является линейной. При составлении модели предполагалось, что прибыль линейно зависит от числа реализуемых изделий.

Приведем примеры некоторых типичных экономических и производственных задач, оптимальное решение которых может быть найдено с помощью построения и расчета соответствующих линейных математических моделей.

5, Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий. К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов. Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

 задача об оптимальном использовании ресурсов при производственном планировании;

 задача о смесях (планирование состава продукции);

 задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

 транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

 математические модели большого числа экономических задач линейны относительно искомых переменных;

 данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

 многие задачи линейного программирования, будучи решенными, нашли широкое применение;

 некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных. В общем виде модель записывается следующим образом:

 целевая функция:

= c1x1 + c2x2 + ... + cnxn → max(min);

(2.1)

 ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1, a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ... am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

(2.2)

 требование неотрицательности:

xj ≥ 0,

(2.3)

 При этом a_ij, b_i, c_j (   ) - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор  , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План  , при котором функция (2.1) достигает своего максимального (минимального) значения, называетсяоптимальным.

5. Формы записи ЗЛП

 1. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

(10.10)

при условиях

(10.11)

(10.12)

                                               .                                 (10.13)

Функция  (10.10) называется целевой функцией (или линейной формой) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.

2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.

3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.

Каноническая (основная) форма	Стандартная (симметричная) форма	Общая форма
1) ограничения
Уравнения .	Неравенства .	Уравнения и неравенств .
2) условия неотрицательности
Все переменные ,	Все переменные ,	Часть переменных ,  ,  .
3) цель задачи
max F(x) или minF(x)	max F(x) [min F(x)]	max F(x) или min F(x)

Замечание.

max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].

Указанные выше три формы задачи линейного программирования эквивалентны в том смысле, что каждая из них может быть преобразована к форме другой. Совокупность чисел  , удовлетворяющих ограничениям (10.11) – (10.13), называется допустимым решением (или планом).

Запишем основную задачу линейного программирования в векторной форме. Найти максимум (минимум) функции

при условиях

                                   ,                   (10.14)

где   – скалярное произведение;   и   – m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы уравнений задачи.

План Х называется опорным планом основной задачи линейного программирования, если система векторов  , входящих в разложение (10.14) с положительными коэффициентами  , линейно независима.

Опорный  план  называется  невырожденным,  если  он  содержит ровно m положительных компонент, в противном случае он является вырожденным.

План  , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.

7. На этом шаге мы рассмотрим представление задачи линейного программирования в канонической форме. 

    Если математическая модель задачи линейного программирования имеет вид:

то говорят, что задача представлена в канонической форме.

    Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.

    Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

• если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

• если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x₃ = x₃⁺ - x₃^-, где x₃⁺, x₃^- ≥ 0.