Графическое решение

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

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

Z = 45X₁ + 60X₂ → max

3X₁ + 6X₂ 180

6X₁ + 2X₂ 210

2X₁ + 3X₂ 112

X₁ 0, X₂ 0

X₁ ≤ (180 – 6Х₂)/ 3

X₁ ≤ (210 – 2Х₂)/ 6

X₁ ≤ (112 – 3Х₂)/ 2

X₁ ≤ 60 – 2Х₂ (1)

X₁ ≤ 35 – 1/3Х₂ (2)

X₁ ≤ 56 – 3/2Х₂ (3)

Решая эту задачу графически, получим следующее:

Точка M лежит на пересечении прямых (1) и (2)

3X₁ + 6X₂ = 180

6X₁ + 2X₂ = 210

6X₁ + 12X₂ = 360

6X₁ + 2X₂ = 210

10Х₂ = 150

Х₂ = 15

3Х₁ = 90

Х₁ = 30

Ответ Х₁=30, Х₂=15

Вывод: решение в симплексной таблице верно.

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

В данной задаче требуется оценить единицу каждого вида ресурса. Эта задача является двойственной задаче, решенной в пункте 1.1.

Задача, двойственная исходной строится следующим образом:

1. меняется тип экстремума целевой функции

коэффициент Симплексный метод решения линейной производственной задачи представлен в таблице 1.

Как видно из последней симплексной таблицы, оптимальная производственная программа имеет вид:

Х₁=30, Х₂=15, Х₃=0, Х₄=0,

а максимальная прибыль равна

Z_max = 2250

При этом первый и второй ресурс будут исчерпаны полностью, а третий ресурс имеет остаток Х₇= 7 единиц, т.е. узкие места производства Х₅=0 и Х₆=0

Исходная задача ЛП:	Двойственная задача ЛП:
Z(x1, x2, x3, x4) = 45x1 + 60х2 + 21x3 + 14x4  max (4) 3x1 + 6х2 + 3x3 + 0x4  180 6x1 + 2х2 + 0x3 + 6x4  210 (5) 2x1 + 3х2 + 5x3 + 7x4  112 x1, x2, x3, x4  0	Z(у1, у2, у3) = 180y1 +210y2 +112y3  min 3y1+6y2+2y3 45 6y1+2y2+3y3 60 3y1+0y2+5y3 21 0y1+6y2+7y3 14 y1,y2,y30

Требуется найти вектор двойственных оценок (y₁,y₂,y₃), минимизирующий общую оценку всех ресурсов

Z = 180y₁ +210y₂ + 112y₃  min

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

3y₁+6y₂+2y₃ 45

6y₁+2y₂+3y₃ 60

3y₁+0y₂+5y₃ 21

0y₁+6y₂+7y₃ 14

y₁,y₂,y₃0

y₁ = 9, y₂ = 3, y₃ = 0.

общая оценка всех ресурсов равна 2250.

Решение полученной задачи можно найти с помощью второй основ­ной теоремы двойственности, согласно которой для оптимальных решений х{х₁,х₂,х₃,х₄} и у{у₁,у₂,у₃} пары двойственных задач необходимо и доста­точно выполнение условий:

X₁(3y₁+6y₂+2y₃–45) =0

X₂(6y₁+2y₂+3y₃–60) =0

X₃(3y₁+0y₂+5y₃ –21)=0

X₄(0y₁+6y₂+7y₃–14) =0

Y₁(3x₁ + 6х₂ + 3x₃ + 0x₄ –180) =0

Y₂(6x₁ + 2х₂ + 0x₃ + 6 x₄ –210 )=0

Y₃(2x₁ + 3х₂ + 5x₃ + 7x₄ –112 )=0

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

По­этому

3y₁+6y₂+2y₃= 45

6y₁+2y₂+3y₃= 60

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

3y₁+6y₂= 45| x2

6y₁+2y₂= 60

10y₂=30

y₂=3

3y₁=27

y₁=9

Z=180∙9 + 210∙3 = 1620+630 = 2250

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