Симплекс метод

Вариант 2

Задание 1

Для выпуска двух видов продукции требуются затраты сырья, рабочего времени и оборудования. Исходные данные в таблице:

Найдите оптимальный план выпуска продукции по критерию «максимум прибыли».

Определите остатки каждого вида сырья.

1) Составьте математическую модель задачи.

2) Решите задачу симплекс-методом.

3) Решите задачу графическим методом. Покажите соответствие опорных решений, полученных при решении симплекс-методом, и угловых точек – вершин допустимой области.

4) Найдите решение двойственной задачи, используя теоремы двойственности.

(Двойственную задачу симплекс-методом решать не нужно)

Решение

1) Составим математическую модель задачи:                                                                     

Вводим переменные: х1 - количество продукции первого вида;

х2 -  количество продукции второго вида;

Составим целевую функцию:   20х1 - цена продукции первого вида;

40х2 - цена продукции второго вида;                                                                     

F(x1,x2)=5x1+7x2(max) - общая прибыль от реализации всей продукции.                                                       

Вводим ограничения: х1+7х2<=56

                                      3x1+4x2<=49                                                       

         2x1+x2 <=26

                                    x1>=0; x2>=0                           

2) Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений – неравенств к равенствам. Для этого введем дополнительные балансовые неотрицательные переменные.

              х1+7х2+х3=56

              3x1+4x2+х4=49

2x1+x2 +х5=26

x1>=0; x2>=0

F(x1,x2)=20x1+40x2+0x3+0x4+0x5 (max)

Теперь можно приступить к заполнению симплекс-таблицы:

Т.к. среди оценок ∆ есть отрицательные, то опорный план (0,0,56,49,26) не оптимальный.

Разрешающий  элемент в ячейке (2;2) - 2. Выводим из базиса переменную х3 и вводим х2. Теперь с помощью метода Гаусса обнуляем другие коэффициенты во втором столбце, это приводит к смене базиса.

Т.к. среди оценок ∆ есть отрицательные, то полученный план (0,8,0,17,18) не оптимальный.

Разрешающий  элемент в ячейке (2;1) – 17/7. Выводим из базиса переменную х4 и вводим х1.

Т.к. среди оценок ∆ нет отрицательных, то полученный план (7,7,0,0,5) оптимальный.

F(x1,x2)=40*7+20*7=420 (max) - общая прибыль от реализации всей продукции.                           

3) графический метод. Заменяем знаки на «=» в системе ограничений и строим все прямые на одном графике:

Область допустимых решений – замкнутый многоугольник 0ABCD. Определим линию уровня 20x1+40x2=0 или x2=-1/2x1(f=a(x))

В нашем примере прямая f=a пересевает область ABCDE в точке В(7,7). Поскольку это последняя точка пересечения, max(f)=f(В)=f(7;7)=420.

4) Составим расширенную матрицу из коэффициентов при переменных системы функциональных ограничений, столбца свободных членов и дополнительной строки из коэффициентов f(x).

Транспонируем матрицу А

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

y1 + 3y2 + 2y3  >=20

7 y1 + 4y2+ y3 >=40

yi >=0, i=1,2,3.

g(y1,у2,у3)=56y1+49y2+26y3 (min)

Найдем ее оптимальный план с помощью теорем двойственности.

Max f(x) оптим. = min g(y) оптим. – если одна из задач пары имеет оптимальное решение, то и другая так же имеет оптимальное решение.

Значения целевых функций при оптимальных решениях численно равны, т.е. g(y) min = 420 – стоимость затрат на ресурсы (из первой теоремы двойственности).

Здесь уi – цена единицы ресурса вида i. Найдем y1,y2,y3 .

Применяем вторую теорему двойственности:

x1*( y1 + 3y2 + 2y3-20) = 0, где х1=7

х2*( 7 y1 + 4y2+ y3 -40) = 0, где х2=7

                          7*( y1 + 3y2 + 2y3-20) = 0,               y1 + 3y2 + 2y3=20

7*(7 y1 + 4y2+ y3 -40)=0,                            7 y1 + 4y2+ y3 =40

Применяем вторую формулу: (переменных три).

у1*(х1+7х2– 56) = 0, где х1=7, х2=7.

у1*(7+49-56) = 0

у1*(0) = 0

запас ресурса «Сырье» израсходуется полностью.

у2*(3 x1+4x2– 49) = 0              х1=7, х2=7.

у2*( 21+28 –49) = 0

у2*(0) = 0

запас  ресурса «Рабочее время» израсходуется полностью.

у3*( 2x1+x2 -26) = 0              х1=7, х2=7.

у3*(14+7-26) = 0

у3*(-5)=0

у3 = 0 - запас ресурса «Оборудование» израсходуется не полностью.

Составим систему уравнений:

y1 + 3y2 + 2y3=20

7 y1 + 4y2+ y3 =40

у3 = 0. Подставляем в первые два уравнения:

y1 + 3y2 =20

7 y1 + 4y2 =40

17y2 = 100,               то у2=100/17.

у1=20-3*100/17              у1=40/17

Итак, получили у = (40/17; 100/17; 0) – допустимое решение двойственной задачи.

Применяем первую теорему двойственности:

g(y)=56*40/17 + 49*100/17 +26*0 =7140/17=420 (min)

g(y)= f(x)=420.

Вывод: у= (40/17; 100/17; 0) – оптимальное решение двойственной задачи.

В оптимальном плане двойственной задачи значение у3=0. Это означает, что запас ресурса «Оборудование» израсходуется не полностью. y1>0,y2>0 – это означает, что запасы сырья и рабочего времени израсходуются полностью.

Задание 2

1)Решите симплексным методом с искусственным базисом задачу линейного программирования.

2)Составьте задачу, двойственную исходной задаче.

F(x)=2x1+x2 (max)