Таблица N 3

Оптимальное решение (производственная программа): Xоpt=(34; 0; 22; 0); максимум целевой функции равен 2328.

Значение переменной с номером i большим 4-х есть остаток (i-4)-ro ресурса. 'Гак как все оценочные коэффициенты неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0.

Следует обратить внимание на экономический смысл элементов послед­ней строки последней симплексной таблицы. Например, коэффициент Δ2=7 при переменной х2 показывает, что если произвести одну единицу продукции второго вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

Заметим, что в рассматриваемом примере ли­нейной производственной задачи возможна самопроверка результата.

Воспользуемся тем, что в оптимальной производственной программе х2=0, х4=0. Предположим, что вторую и четвертую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя перемен­ными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

L(x1,x3)=48xl+29x3 àmax

3х1+4х3≤198

2х1+ х3 ≤ 96

6х1+ х3≤228

x1≥0, x3≥0

Задачу линейного программирования с двумя переменными можно решить графически. Возьмем на плоскости систему координат: ось OX3 направим горизонтально и вправо, ось OХ1 -вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник. Вторая из двух основных теорем линейного программирования гласит: Если экстремум целевой функции достигается на допустимом множестве, то функция принимает его в какой-то вершине многоугольника-допустимого множества. Исходя из этой теоремы, найти искомый экстремум можно просто перебрав вершины многоугольника и определив ту, в которой значение функции экстремально. Чаще делают по-другому: строят линию уровня целевой функции и двигают ее параллельно в направлении экстремума, стараясь уловить последнюю точку пересечения линии с допустимым множеством.

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

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

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

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

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

4)тип неравенств меняется (≤ на ≥ и наоборот);

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

исходная задача двойственная задача

L=(c,x)àmax Z=(b,y)àmin

Ax≤b, x≥0 Ya≥c, y≥0,

L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 àmax Z(y1,y2,y3,y4)=198yl+96y2+228y3 à min

3х1+2х2+4х3+3х4≤198 3y1+2y2+6y3≥48

2х1+3х2+1х3+2х4≤96 2y1+3y2+5y3≥30

6х1+5х2+1х3+0х4≤228 4y1+ y2 + y3≥29

xj≥0, jєN4 3y1+2y2≥10

yj≥0, jєN3

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x1, x2, x3, x4) и Y(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий:

x1(3y1+2y2+6y3-48)=0 y1 (3х1+2х2+4х3+3х4)-198=0

x2(2y1+3y2+5y3-30)=0 y2 (2х1+3х2+1х3+2х4)-96=0

x3(4y1+1y2+1y3-29)=0 y3 (6х1+5х2+1х3+0х4)-228=0

x4(3y1+2y2+0y3-10)=0

В решении исходной задачи х1>0, х3>0, поэтому

3y1+2y2+6y3-48=0

4y1+1y2+1y3-29=0

Учитывая, что второй ресурс был избыточным и, согласно теореме двойственности его оценка равна нулю – y2=0, то приходим к системе:

3y1+6y3-48=0

4y1+1y3-29=0

из которой следует, что y1=6; y3=5.

Таким образом получили двойственные оценки ресурсов: y1=6; y2=0; y3=5; общая оценка всех ресурсов Z=198y1+228y3=2328.

Заметим, что полученное решение содержалось в последней строке последней симплексной таблицы исходной задачи

Таблица N 3