Двойственная задача линейного программирования

Таблица №1

С	Б	Н	x1	x2	X3	x4	x5	X6	x7
	x5									25.2
	x6									–
	x7
	P		-26	-35	-18	-30

Если все оценочные коэффициенты (зеленый цвет) неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0, максимум целевой функции указан правее буквы P. Если же есть отрицательный оценочный коэффициент, то находят самый малый из них. Если в столбце коэффициентов над ним (голубой цвет) нет положительных, то задача не имеет решения. Задача оптимального планирования не может быть таковой, поэтому ищут минимальное отношение свободных членов к положительным элементам указанного столбца (это отношение указано справа от таблицы голубым цветом, а минимальное отношение – красным). В пересечении двух голубых строки и столбца получаем разрешающий элемент (красный цвет) и затем строим новую таблицу.

Таблица №2

С	Б	Н	x1	x2	x3	x4	x5	x6	X7
	x2	25.2	2/5		1/5	4/5	1/5			63.75
	x6
	x7	49.8	8/5		19/5	-4/5	-1/5			31.125
	P		-12		-11	-2

Если есть отрицательные оценочные коэффициенты (зеленый цвет), то проделываем то же самое еще раз (см. выше).

Таблица №3

С	Б	Н	x1	x2	x3	x4	x5	x6	x7
	x2				-11/15	8/15	1/5	-2/15
	x1				7/3	2/3		1/3
	x7				1/15	-28/15	-1/5	-8/15
	P

Оптимальное решение: x₁=28, x₂=14, x₇=5, все остальные переменные равны 0; максимум целевой функции равен 1218; значение переменной с номером i большим 4 есть остаток (i-4)-го ресурса.

Так как все оценочные коэффициенты (зеленый цвет) неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0, максимум целевой функции указан правее буквы P. Выше выписан ответ.

Расшивка узких мест

Таблица №3

С	Б	Н	x1	x2	x3	x4	x5	x6	x7
	x2				-11/15	8/15	1/5	-2/15
	x1				7/3	2/3		1/3
	x7				1/15	-28/15	-1/5	-8/15
	P

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют «узкие места производства». Будем их заказывать дополнительно. Пусть – вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие , где Н – значения базисных переменных в последней симплексной таблице, а Q^-1 – обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор , максимизирующий суммарный рост прибыли

(1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции)

(2)

предполагая, что можно надеяться получить дополнительно не более первоначального объема ресурса каждого вида (3)

причем по смыслу задачи , (4)

Переписав неравенства (2) и (3) в виде: (5)

; (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. Допустимое множество закрашено серым цветом. Программа «расшивки» имеет вид:

Ответ: максимальный прирост прибыли составит maxW=175.

1.4. Задача о комплектном плане

Задачу ЛП с двумя переменными можно решить графически. Возьмем на плоскости систему координат: ось OX₁ направим горизонтально и вправо, ось OX₂ – вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник.

Вторая из двух основных теорем ЛП гласит: Если экстремум целевой функции достигается на допустимом множестве, то функция принимает его в какой-то вершине многоугольника – допустимого множества. Исходя из этой теоремы, найти искомый экстремум можно просто перебрав вершины многоугольника и определив ту, в которой значение функции экстремально. Чаще делают по-другому: строят линию уровня целевой функции и двигают ее параллельно в направлении экстремума, стараясь уловить последнюю точку пересечения линии с допустимым множеством. Зададим задачу ЛП с тремя ограничениями и четырьмя переменными, затем зададим выражения x₃ и x₄ через x₁ и x₂ . Теперь переменных осталось две и задача может быть решена графически.

Предположим, что в линейной производственной задаче продукция производится комплектно: продукции 3-го вида надо произвести в 2 раза больше, чем 1-го, а 4-го столько же, сколько и 2-го вида продукции. Т.е. имеем соотношения x₃=2x₁ и x₄=x₂.

P=62x₁+65x₂→max

4x₁+9x₂≤126 (1)

17x₁+2x₂≤84 (2)

10x₁+1x₂≤75 (3)

x₁, x₂³0

Искомая точка находится как решение системы:

Ответ: x₁=3.48; x₂=12.42; maxP=1023.06.

Таблица №1

С	Б	Н	x1	x2	X3	x4	x5	X6	x7
	x5									25.2
	x6									–
	x7
	P		-26	-35	-18	-30

Если все оценочные коэффициенты (зеленый цвет) неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0, максимум целевой функции указан правее буквы P. Если же есть отрицательный оценочный коэффициент, то находят самый малый из них. Если в столбце коэффициентов над ним (голубой цвет) нет положительных, то задача не имеет решения. Задача оптимального планирования не может быть таковой, поэтому ищут минимальное отношение свободных членов к положительным элементам указанного столбца (это отношение указано справа от таблицы голубым цветом, а минимальное отношение – красным). В пересечении двух голубых строки и столбца получаем разрешающий элемент (красный цвет) и затем строим новую таблицу.

Таблица №2

С	Б	Н	x1	x2	x3	x4	x5	x6	X7
	x2	25.2	2/5		1/5	4/5	1/5			63.75
	x6
	x7	49.8	8/5		19/5	-4/5	-1/5			31.125
	P		-12		-11	-2

Если есть отрицательные оценочные коэффициенты (зеленый цвет), то проделываем то же самое еще раз (см. выше).

Таблица №3

С	Б	Н	x1	x2	x3	x4	x5	x6	x7
	x2				-11/15	8/15	1/5	-2/15
	x1				7/3	2/3		1/3
	x7				1/15	-28/15	-1/5	-8/15
	P

Оптимальное решение: x₁=28, x₂=14, x₇=5, все остальные переменные равны 0; максимум целевой функции равен 1218; значение переменной с номером i большим 4 есть остаток (i-4)-го ресурса.

Так как все оценочные коэффициенты (зеленый цвет) неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0, максимум целевой функции указан правее буквы P. Выше выписан ответ.

Двойственная задача линейного программирования

Задача линейного оптимального планирования – исходная в своей паре симметричных двойственных задач. Вообще же другая задача в двойственной паре строится так:

1) меняется тип экстремума целевой функции (max на min и наоборот);

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

3) свободные члены одной задачи становятся коэффициентами целевой функции двойственной задачи;

4) тип неравенств меняется ( <= на => и наоборот);

5) каждый столбец одной задачи порождает строку ограничений другой задачи и наоборот.

В матрично-векторном виде обе задачи выглядят так:

Исходная задача	Двойственная задача
CX→max AX≤B, X≥0	YB→min YA≥B, X≥0

P=26∙x1+35∙x2+18∙x3+30∙x4→max 2∙x1+5∙x2+1∙x3+4∙x4≤126 3∙x1+0∙x2+7∙x3+2∙x4≤84 2∙x1+1∙x2+4∙x3+0∙x4≤75 x1, x2, x3, x4≥0

S=126∙y1+84∙y2+75∙y3→min 2∙y1+3∙y2+2∙y3≥26 5∙y1+0∙y2+1∙y3≥35 1∙y1+7∙y2+4∙y3≥18 4∙y1+2∙y2+0∙y3≥30 y1, y2, y3≥0

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x₁, x₂, x₃, x₄) и Y(y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий:

x1∙(2∙y1+3∙y2+2∙y3-26)=0, x2∙(5∙y1+0∙y2+1∙y3-35)=0, x3∙(1∙y1+7∙y2+4∙y3 -18)=0, x4∙(4∙y1+2∙y2+0∙y3-30)=0.

y1∙(2∙x1+5∙x2+1∙x3+4∙x4-126)=0, y2∙(3∙x1+0∙x2+7∙x3+2∙x4-84)=0, y3∙(2∙x1+1∙x2+4∙x3+0∙x4-75)=0.

Ранее было найдено, что в решении исходной задачи x₁>0, x₂>0. Поэтому:

2∙y₁+3∙y₂+2∙y₃-26=0,

5∙y₁+0∙y₂+1∙y₃-35=0.

Если же учесть, что третий ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю y₃=0, то приходим к системе уравнений:

Таким образом, получили двойственные оценки ресурсов y₁=7, y₂=4, y₃=0, причем общая оценка всех ресурсов равна 1218.

Заметим, что решение содержалось в последней строке симплексной таблицы исходной задачи. Очень важен экономический смысл всех элементов этой строки. Например, двойственная оценка второго ресурса y₂=4 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4 единицы.

Расшивка узких мест

Таблица №3

С	Б	Н	x1	x2	x3	x4	x5	x6	x7
	x2				-11/15	8/15	1/5	-2/15
	x1				7/3	2/3		1/3
	x7				1/15	-28/15	-1/5	-8/15
	P

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют «узкие места производства». Будем их заказывать дополнительно. Пусть – вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие , где Н – значения базисных переменных в последней симплексной таблице, а Q^-1 – обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор , максимизирующий суммарный рост прибыли

(1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции)

(2)

предполагая, что можно надеяться получить дополнительно не более первоначального объема ресурса каждого вида (3)

причем по смыслу задачи , (4)

Переписав неравенства (2) и (3) в виде: (5)

; (6)

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. Допустимое множество закрашено серым цветом. Программа «расшивки» имеет вид:

Ответ: максимальный прирост прибыли составит maxW=175.

1.4. Задача о комплектном плане

Задачу ЛП с двумя переменными можно решить графически. Возьмем на плоскости систему координат: ось OX₁ направим горизонтально и вправо, ось OX₂ – вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник.

Вторая из двух основных теорем ЛП гласит: Если экстремум целевой функции достигается на допустимом множестве, то функция принимает его в какой-то вершине многоугольника – допустимого множества. Исходя из этой теоремы, найти искомый экстремум можно просто перебрав вершины многоугольника и определив ту, в которой значение функции экстремально. Чаще делают по-другому: строят линию уровня целевой функции и двигают ее параллельно в направлении экстремума, стараясь уловить последнюю точку пересечения линии с допустимым множеством. Зададим задачу ЛП с тремя ограничениями и четырьмя переменными, затем зададим выражения x₃ и x₄ через x₁ и x₂ . Теперь переменных осталось две и задача может быть решена графически.

Предположим, что в линейной производственной задаче продукция производится комплектно: продукции 3-го вида надо произвести в 2 раза больше, чем 1-го, а 4-го столько же, сколько и 2-го вида продукции. Т.е. имеем соотношения x₃=2x₁ и x₄=x₂.

P=62x₁+65x₂→max

4x₁+9x₂≤126 (1)

17x₁+2x₂≤84 (2)

10x₁+1x₂≤75 (3)

x₁, x₂³0

Искомая точка находится как решение системы:

Ответ: x₁=3.48; x₂=12.42; maxP=1023.06.