Решение оптимизационных экономических задач методами линейного программирования

 

Этой таблице соответствует  допустимый план:

x₅ = 2;

x₆ = 5;

x_1…4 = 0;

F = 27*0 + 10*0 + 15*0 + 28*0 + 0*2 + 0*5 = 0.

 

Проверим полученный план на оптимальность, вычислив для  этого оценки Δ_i:

Δ₁ = (0*3 + 0*3) – 27 = -27

Δ₂ = (0*2 + 0*1) – 10 = -10

Δ₃ = (0*1 + 0*3) – 15 = -15

Δ₄ = (0*2 + 0*4) – 28 = -28

Δ₅ = (0*1 + 0*0) – 0 = 0

Δ₆ = (0*0 + 0*1) – 0 = 0

 

План не оптимален, т.к. содержит отрицательные оценки.

В качестве направляющего выберем столбец, соответствующий переменной x₄, так как у нее наибольший коэффициент по модулю. Из столбца выберем наименьшее значение: min (2/2=1;5/4=1,25). Следовательно, первая строка является ведущей, т.к. у нее наименьшее значение. Разрешающий элемент равен 2 и находится на пересечении ведущего столбца и ведущей строки. Значит, из базиса необходимо убрать вектор A₅.

Теперь необходимо скомбинировать строки так, чтобы на месте разрешающего элемента появилась единица, а оставшийся элемент направляющего вектора  преобразовался в ноль:

1) Первую строку разделим  на два, т.е. S₁/2.

2) Из второй строки вычтем первую, помноженную на два, т.е. S₂ - S₁*2

 

После этого можно  составить вторую симплекс-таблицу:

Базис	Cб.	B	C1 = 27	C2 = 10	C3 = 15	C4 = 28	C5 = 0	C6 = 0
			A1	A2	A3	A4	A5	A6
A4	28	1	1,5	1	0,5	1	0,5	0
A6	0	1	-3	-3	1	0	-2	1
Δi =			15	18	-1	0	14	0

 

Этой таблице соответствует  допустимый план:

x₄ = 1;

x₆ = 1;

x_1,2,3,5 = 0;

F = 27*0 + 10*0 + 15*0 + 28*1 + 0*0 + 0*1 = 28.

 

Проверим полученный план на оптимальность:

Δ₁ = (28*1,5 + 0*(-3)) – 27 = 15

Δ₂ = (28*1 + 0*(-3)) – 10 = 18

Δ₃ = (28*0,5 + 0*1) – 15 = -1

Δ₄ = (28*1 + 0*0) – 28 = 0

Δ₅ = (28*0,5 + 0*(-2)) – 0 = 14

Δ₆ = (28*0 + 0*1) – 0 = 0

План не оптимален, т.к. все еще содержит отрицательную оценку.

В качестве направляющего столбца выберем столбец, соответствующий переменной x₃. Из столбца выберем наименьшее значение: min (1/0,5=2 ; 1/1=1). Следовательно, вторая строка является ведущей. На этот раз из базиса необходимо убрать вектор A₆.

Снова комбинируем строки так, чтобы на месте разрешающего элемента появилась единица, а оставшийся элемент направляющего вектора преобразовался в ноль:

1) Из первой строки  вычтем вторую, деленную на два,  т.е. S₁ - S₂/2.

2) Вторую строку оставим нетронутой, т.е. S₂ /1.

 

После этого можно  составить третью симплекс-таблицу:

Базис	Cб.	B	C1 = 27	C2 = 10	C3 = 15	C4 = 28	C5 = 0	C6 = 0
			A1	A2	A3	A4	A5	A6
A4	28	0,5	3	2,5	0	1	1,5	-0,5
A3	15	1	-3	-3	1	0	-2	1
Δi =			12	15	0	0	12	1

 

Этой таблице соответствует  допустимый план:

x₄ = 0,5;

x₃ = 1;

x_1,2,5,6 = 0;

F = 27*0 + 10*0 + 15*1 + 28*0,5 + 0*0 + 0*1 = 29.

 

Проверим полученный план на оптимальность:

Δ₁ = (28*3 + 15*(-3)) – 27 = 12

Δ₂ = (28*2,5 + 15*(-3)) – 10 = 15

Δ₃ = (28*0 + 15*1) – 15 = 0

Δ₄ = (28*1 + 15*0) – 28 = 0

Δ₅ = (28*1,5 + 15*(-2)) – 0 = 12

Δ₆ = (28*(-0,5) + 15*1) – 0 = 1

Все оценки положительны – значит, теперь план оптимален.

7. Теоремы двойственности и их использование в задачах ЛП

 

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

 

                                                                                                              (1)

 

 

 

 

 

 Определение: задача, состоящая в нахождении минимального значения функции                                                                          при условиях:

 

                                                                                                     (2)

 

 

 

 

 

называется двойственной по отношению к задаче (1). Задачи (1) и (2) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, мы видим, что двойственная задача составляется согласно следующим правилам:

 

1. Целевая функция  исходной задачи (1) задается на максимум, а целевая функция двойственной (2) - на минимум.

2. Матрица

 

 

составленная из коэффициентов  при неизвестных в системе  ограничений исходной задачи (1), и аналогичная матрица

 

 

в двойственной задаче (2) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3. Число переменных  в двойственной задаче (2) равно числу ограничений в системе исходной задачи (1), а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при  неизвестных в целевой функции двойственной задачи (2) являются свободные члены в системе исходной задачи (1), а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная x_j исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида « ≥ ». Если же переменная x_j может принимать как положительные, так и отрицательные значения, то j-е соотношение в системе двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i-тое соотношение в системе исходной задачи — неравенство, то i-я переменная двойственной задачи y_i ≥ 0. В противном случае переменная y_i может принимать как положительные, так и отрицательные значения.

Двойственные пары задач  обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и соотношения двойственной задачи являются неравенствами вида “ ". Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

 

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

Лемма 1: если x - некоторый план исходной задачи, а y - произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане х не превосходит значение целевой функции двойственной задачи при плане y, т.е. F(x) ≤ G(y).

Лемма 2: если F(x*) = G(y*) для некоторых планов х* и y* прямой и двойственной задач, то х* - это оптимальный план исходной задачи, а y* - это оптимальный план двойственной задачи.

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

F_max = G_min

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

Теорема 2 (вторая теорема двойственности): план задачи и план задачи, являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство:

 

8. Пример решения двойственной задачи

 

а) Дана прямая (исходная) задача, необходимо составить к ней двойственную:

Для изготовления 4-ех видов продукции P₁, P₂, P₃, P₄  используют два вида сырья: S₁ и S₂ . Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2. Составить план производства, обеспечивающий получений максимальной прибыли.

Вид сырья	Запас сырья	Количество  единиц сырья, идущих на изготовление единицы продукции
		P1	P2	P3	P4
S1	2	3	2	1	2
S2	5	3	1	3	4
Прибыль от единицы  продукции		27	10	15	28

 

F = 27x₁ + 10x₂ + 15x₃ + 28x₄ → max

 

Из представленной задачи необходимо сформулировать условие  двойственной задачи. Для этого нужно придерживаться следующих правил:

1) Если в одной из  двойственных задач необходимо  найти max, то в другой – min, и наоборот.

2) Вектор правых частей  системы ограничений одной из  задач является вектором коэффициентов  в целевой функции другой задачи.

3) Матрицы коэффициентов в левых частях систем ограничений этих задач получаются одна из другой - транспонированием.

4) Знаки неравенств (кроме  условий неотрицательности переменных) в ограничениях этих задач  противоположны.

В итоге мы получим следующую двойственную задачу:

G = 2y₁ + 5y₂ → min

 

б) Необходимо решить полученную двойственную задачу любым методом.

Т.к. задача имеет всего 2 переменных – ее будет проще  решить графическим методом. На нем  и остановимся.

Построим прямые уравнения, для чего заменим в ограничениях знаки неравенств на точные равенства:

(1) 3y₁ + 3y₂ = 27

Точки, через которые  проходит прямая:

y₁ = 9, y₂ = 0; y₁ = 0, y₂ = 9.

 

(2) 2y₁ + y₂ = 10

Точки, через которые  проходит прямая:

y₁ = 5, y₂ = 0 ; y₁ = 3, y₂ = 4.

 

(3) y₁ + 3y₂ = 15

Точки, через которые  проходит прямая:

y₁ = 0, y₂ = 5 ; y₁ = 6, y₂ = 3.

 

(4) 2y₁ + 4y₂ = 28

Точки, через которые  проходит прямая: