Линейное программирование, решение задач симплексным методом

--PAGE_BREAK--

: aij,


где  brs =  arsaij -  arjais (i ≠ r, j ≠ s),
причем все элементы таблицы нужно разделить на aij.

       Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил:

1)       разрешающий элемент заменяется единицей

2)       остальные элементы разрешающего столбца j остаются без изменения.

3)       остальные элементы разрешающей строки iменяют лишь свои знаки.

4)       остальные элементы  brsвычисляются по формуле brs =  arsaij -  arjais

5)       все элементыновой таблицы делятся на разрешающий элемент aij.
Пример 1. Для таблицы





X1

X2

X3

Y1 =

1

-2

3

Y2 =

-1

1

2

Y3 =

2

-1

-1

 

один шаг жорданова исключения с разрешающими 2-й строкой и 3-м столбцом приводим к таблице                 





X1

X2

Y2

Y1 =

5

-7

3

X3 =

1

-1

1

Y3 =

3

-1

-1


: 2


        Жордановы исключения позволяют от случайно взятой декартовой системы координатных плоскостей перейти к новой системе, в которой координатами точек являются их уклонения от более интересной для той или другой задачи системы плоскостей.
Модифицированные жордановы исключения
          Если исходную систему уравнений     ai1x1 + ai2x2 + … + ainxn = bi, гдеi = 1,m,   
записать в виде   –ai1(-x1) – ai2(-x2) — … — ain(-xn) = bi
и составить таблицу




-X1

-X2

…-Xn

b1 =

–a11

–a12

…–a1n

….

…………..

bm =

–am1

–am2

…–amn



то в этих случаях вместо ОЖИ пользуются МЖИ.

Один шаг МЖИ с разрешающим элементом  “-ars”, означает переход к новой таблице





-X1…

-Yr …

-Xn

b1 =

b11 ...

a1s …

b1n

….

…………………….

xs =

-ar1 …

1   …

-arn

….

…………………….

bm =

bm1…

ams  …

bmn


: (-ars)


которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями:

1)       остальные элементы разрешающей строки остаются без изменения

2)       остальные элементы разрешающего столбца меняют лишь свои знаки

Рассмотрим систему
     2X1 + 3X2 – 5X3 = 16 = b1,   

     3X1 — 2X2 + 4X3 = 36 = b2,   

     5X1 + 7X2 – 11X3 = 44 = b3.
Запишем ее в виде таблицы
   



-x1

-x2

-x3

b1 =

-2

-3

5

b2 =

-3

2

-4

b3 =

-5

-7

11


и произведем один шаг МЖИ с разрешающим элементом “2”





-x1

-b2

-x3

b1 =

-13

3

-2

x2 =

-3

1

-4

b3 =

-31

7

-6


: 2



Экстремумы линейной функции
          Пусть рассматривается общая задача линейного програм­мирования. Воснове вычислительных методов ЛП лежит следующая фундаментальная теорема.

          Теорема. Если задача линейного программирования име­ет оптимальное решение

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

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

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

Следовательно, принципиальная схема решения задач линейного программирования следующая:
1. С помощью ЖИ найдем все опорные решения систе­мы.
a11x1 + a12x2 + … + a1nxn = b1,

……...................

ak1x1 + ak2x2 + … + aknxn = bk,

ak+1,1x1 + ak+1,2x2 + … + ak+1nxn ≤ bk+1,

……...................

am1x1 + am2x2 + … + amnxn ≤ bm.
2. Вычислим для каждого из них значение функции Z, определяемое соотношением.
        Z = c1x1 + c2x2 + … + cnxn.
3. Выберем из них экстремальное Z.
        Следует отметить, что может оказаться очень большое число опорных решений, поэтому нужно производить упо­рядоченный перебор опорных решений, добиваясь на

каж­дом шаге монотонного изменения функции Z.

        Такая идея последовательного улучшения решения и за­ложена в основном вычислительном методе решения задач линейного программирования, получившим название симп­лексного метода.
Симплексный метод на основе полных таблиц
Постановка задачи об определении оптимального ассортимента продукции
        Предприятие может производить два вида изделий А и В, располагая для их изготовления ограниченными ресурса­ми материала чугуна и стали соответственно в количествах 350 и 392 кг и оборудования в количестве 408 станко-часов. Данные, представленные в виде таблицы, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия А и В.

Требуется определить сколько изделий А и В должно про­изводить предприятие, чтобы достичь наибольшей прибыли.


Виды ресурсов



Объем ресурсов



Затраты на одно изделие

А

В

 Чугун

350

14

5

 Сталь

392

14

8

 Оборудование

408

6

12

 Прибыль в руб.



10

5



        Введем искомые неизвестные Х1 и X2, обозначающие число изделий А и В, которые должно производить пред­приятие.

        Тогда математически задачу можно сформулировать сле­дующим образом.

Среди множества неотрицательных решений системы неравенств
        14X1+ 5Х2 ≤ 350,    (1.1)

        14Х1 + 8Х2 ≤ 392,

        6Х1 + 12Х2 ≤ 408,
найти такое решение, для которого функция
        Z= 10 Х1 + 5 Х2
достигает наибольшего значения.
Геометрическое решение задачи
        Прежде всего, построим область допустимых решений, соответствующую системе неравенств.

       Для этого, заменив каждое из неравенств равенством
              14Х1 + 5Х2 = 350, (1-я прямая),

              14X1 + 8Х2 = 392, (2-я прямая),

              6Х1 + 12Х2 = 408, (3-я прямая),
строим граничную линию. Учитывая, что Х1 ≥ 0 и Х2 ≥ 0, полу­чаем заштрихованную часть плоскости, образующую много­угольник решений OABCD (рис.1).

        Затем строим линию уровня 10Х1 + 5Х2 = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линей­ной функции.

        Действительно
Z0= 10X10 + 5Х20 = 10 * 0 + 5 * 0 = 0,

ZА = 10X1A + 5Х2A = 10 * 0 + 5 * 34 = 170,

ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 и т. д.
         Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает minзначение функции Z, а другая проходит через точку С и функция Z для нее прини­мает mах значение. Эти линии уровня называются опорными.






Рис. 1
        Точка C образована первой и второй прямыми. Следова­тельно, решая систему уравнений
        14Хl + 5Х2 = 350,

        14Х1 + 8Х2 = 392,
найдем координаты точки C
         Х1 = 20, Х2 = 14,
при этом Zmax = 10 * 20 + 5 * 14 = 270 руб.

        Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изде­лий вида В.
Отыскание максимума линейной функции


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

Добавляя к левой части неравенств
        14X1+ 5Х2 ≤ 350,

        14Х1 + 8Х2 ≤ 392,

        6Х1 + 12Х2 ≤ 408,
некоторую нео­трицательную величину Yj ≥ 0 (i = 1, 2, 3),      (1.2)

называемую выравнивающей или базисной переменной, пре­вратим их в уравнения:


 


 


14

 Х1 + 5Х2 + У1



 = 350,

 
14

 Х1 + 8Х2

+ У2

 = 392,

 
6

 X1 + 12Х2

         + У3

 =408,

 
-10

 X1 — 5Х2



 +Z =0.


 


(1.3)
 
        При этом можно показать, что каждому решению систе­мы неравенств (1.1) соответствует единственное решение си­стемы уравнений (1.3) и неравенств (1.2) и наоборот.
        Каждая из переменных Y1, У2, У3 входит только в одно уравнение и зависит от переменных Х1 и X2, которые мы на­зываем свободными.

Системе (1.3) соответствует исходное допустимое базис­ное решение X1 = X2 = 0; 

Y1 = 350;  Y2 = 392; Y3 = 408 и Z = 0.

        Выполняем первое тождественное преобразование системы уравнений (1.3). Выбираем разрешающий столбец, соот­ветствующий наименьшему отрицательному элементу в Z стро­ке, ибо теоретически установлено, что при этом можно ожи­дать при прочих равных условиях большего увеличения фун­кции Z. Правую часть уравнений делим на элементы разре­шающего столбца и выбираем наименьшее положительное отношение, соответствующее разрешающей строке (уравне­нию). На пересечении выделенных столбца и строки стоит разрешающее число.

        Первое уравнение делим на разрешающее число и вы­писываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):



 


 
 
X1 +

 5/14

 X2 + 1/4 Y1                           = 25,



      3

 Х2–Y1 +  Y2



 = 42,

 


138/14

 X2–6/14 Y1         + У3

 =258,

 
-20/14

 X2+10/14 Y1

 +Z =250.


 
(1.4)
       
          Подобное тождественное преобразование, при котором выбор разрешающего числа производится по указанному правилу, будем называть симплексным преобразованием.

        Таким образом, симплексное преобразование выполня­ется по следующему правилу:
1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному           элементу в Z — строке.

2. Выбирается разрешающая строка, которая соответству­ет наименьшему     положительному из отношений элементов правой части уравнений на соответствующие элементы раз­решающего столбца. На пересечении разрешающего столбца и разрешающей    строки стоит разрешающее число.

3. Элементы разрешающей строки делятся на разрешаю­щее число.

4. Вычисляются элементы всех остальных строк по фор­муле:


Новые эл-ты

=

Старые эл-ты



_

соответствующее число в разрешающей строке



*

соответствующее число в разре­шающем столбце

разрешающее число



 




      продолжение
--PAGE_BREAK--
                                                                                                                                   
          Из системы (1.4) находим второе допустимое базисное решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, которому соответствует новое увеличенное значение функции Z = 250.

          Таким образом, процесс последовательных симплексных преобразований является процессом последовательного улуч­шения решения. При этом:
     1. Если в Z — строке найдется хотя бы один отрицатель­ный элемент и

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

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

     2. Если все элементы в Z — строке неотрицательны, то достигнуто оптимальное решение.

         Это и есть достаточные условия существования оптималь­ного плана решения.

В системе (1.4) коэффициент при Х2 в Z — строке отри­цательный, поэтому второй столбец будет разрешающим. Находим, что вторая строка будет разрешающей. Далее про­изводим симплексное преобразование системы (1.4) соглас­ном указанному правилу:
          X1 + 8/42 Y1 – 5/42 Y2 = 20,

          X2 – 1/3 Y1 + 1/3 Y2 = 14,

         20/7 Y1 – 23/7 Y2 + Y3 = 120,

         10/42 Y1 + 20/42 Y2 + Z = 270,       (1.5)
                Так как в Z — строке все элементы неотрицательны, то данный план является оптимальным. При этом Yl = Y2 = 0; X1 = 20; Х2 = 14 и Zmax = 270.

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

            Каждое симплексное преобразование системы сводится к переходу от одной симплексной таблицы к другой.

            Соответственно исходной системе уравнений (1.3) состав­ляем первую симплекс-таблицу (табл. 1.1).







X1

X2

Y1

Y2

Y3

контр. столбец

Y1

350

14

5

1





370

Y2

392

14

8



1



415

Y3

408

6

12





1

427

 Z



-10

-5







-15


Таблица 1.1


           Первый столбец — это столбец базисных переменных, во втором столбце стоят свободные коэффициенты правой части уравнений (1.3), в первой строке располагаются все переменные, последний столбец — это контрольный столбец и коэффициенты в нем равны сумме всех коэффициентов по строке.

Из табл. 1.1 имеем первое допустимое решение системы (1.3) Х1 = Х2 = 0, Y1 = 350,

Y2 = 392, Y3 = 408, Z = 0, которое соответствует вершине О (0,0) многоугольника допустимых решений OABCD (рис.1).

Переход ко второй симплекс-таблице (табл. 1.2) выпол­няется согласно указанному в этом пункте правилу для сим­плексных преобразований систем уравнений, при этом раз­решающая переменная Х1 идет в базис вместо разрешающей переменной Y1 Получаем табл. 1.2.







X1

X2

Y1

Y2

Y3

контр. столбец

X1

25

1

5/14

1/14





370/14

Y2

42



3

-1

1



45

Y3

258



138/14

-6/14



1

3758/14

 Z

250



-20/14

10/14





3490/14


Таблица 1.2
 

           После заполнения табл. 1.2 следует проверить правиль­ность ее заполнения, для чего суммируем коэффициент по строкам и эта сумма должна быть равна коэффициентам, сто­ящим в соответствующих клетках контрольного столбца. Из табл. 1.2 второе допустимое решение будет Х1 = 25, Х2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250.

          Нетрудно видеть, что эта таблица соответствует систе­ме (1.4), а опорное решение

Х1 = 25, Х2 = 0 соответствует вершине D(25,0) многоугольника решений.

          Так как в Z — строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. 1.3.







X1

X2

Y1

Y2

Y3

контр. столбец

X1

20

1



4/21

-5/42



295/14

X2

14



1

-1/3

1/3



15

Y3

120





20/7

-23/7

1

844/7

 Z

270





5/21

10/21



1895/7


Таблица 1.
3
* Примечание. Для простоты вычислений следует помнить, что в новой таб­лице на месте элементов разрешающего столбца (кроме разрешающего элемента) стоят нули. Если в разрешающей строке стоят нули, то в новую таблицу соответствующие столбцы переносятся без изменения:
           Так как в Z — строке нет отрицательных элементов, то данное решение будет оптимальным.

Табл. 1.3 соответствует системе уравнений (1.5) и опти­мальному решению Х1 = 20,

Х2 = 14 и Zmax = 270 и вершине С (20,14) многоугольника допустимых решений OABCD.

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

        
Симплексный метод на основе укороченных таблиц
Рассмотрим систему уравнений (1.3) и запишем ее в виде таблицы1.4



        СП

БП

1

X1

X2

Y1

350

14

5

Y2

392

14

8

Y3

408

6

12

Z

0

-10

-5


Таблица 1.4


         В первый столбец записываем базисные переменные (БП), а в первую строку – свободные переменные (СП). Далее переход к новой таблице 1.5 совершаем по правилу:
1)       меняем местами СП и БП

2)       на месте разрешающего элемента стоит величина ему обратная

3)       элементы разрешающей стоки делим на разрешающее число

4)       элементы разрешающего столбца делим на разрешающее чисто и меняем знак

5) остальные элементы находятся как в главе “Отыскание максимума линейнойфункции” правило 4 (правило прямоугольников для ОЖИ). Получаем таблицу 1.5.
 

        СП

БП

1

Y1

X2

X1

25

1/14

5/14

Y2

42

-1

3

Y3

258

-6/14

138/14

Z

250

10/14

-20/14


Таблица 1.5
Улучшаем этот опорный план, производя симплексное преобразование с разрешающим элементом “3” (табл. 1.6).



        СП

БП

1

Y1

Y2

X1

20

4/21

-5/42

X2

14

-1/3

1/3

Y3

120

20/7

-23/7

Z

270

5/21

10/21


Таблица 1.6
Получили оптимальный план Zmax = 270 при X1 =20, X2 = 14, а ресурсы оборудования оказались в избытке в количестве 120 станко–часов.


Решение задачи линейного программирования
Найти максимум целевой функции
F = 10x + 5y
при ограничениях
14x + 5y ≤ 350        

7x + 4y ≤ 196

x + 2y ≤ 68

 

Решение задачи с использованием программы
Microsoft
Excel.


Отведем А3 и B3 под значения переменных xи y.
В ячейку C4 введем функцию цели
                      = 10*A3 + 5*B3
В ячейки A7:A9 введем левые части ограничений
                      = 14*A3 + 5*B3

                      = 7*A3 + 4*B3

                      = A3 + 2*B3
а в ячейки B7:B9 – правые части ограничений.
    После этого выберем команду Сервис,  Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver) как показано на рис. 2. После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (SolverResults), которое сообщает, что решение найдено (рис. 3).
 
Рис. 2. Поиск решения
  
Рис. 3. Результаты поиска решения
Геометрическое решение задачи с применением программы
MATHCAD 2000.

Установите режим автоматических вычислений. Запишите в виде y = kx + b уравнения прямых, ограничивающих область допустимых значений переменных. Для того чтобы ввести и разрешить относительно y ограничение 14x + 5y ≤ 350,  введите левую часть неравенства, нажмите кнопку Ctrl и нажмите одновременно кнопку =, удерживая предыдущую до тех пор пока выскочит жирный знак =, пометьте выделяющей рамкой переменную y, щелкните в меню Symbolic (Символы)  по строке Solve(Вычислить) – результат вычислений будет выведен в рабочем документе справа от уравнения; введите имя функции (в рассматриваемом примере y1(x)) и присвойте ей полученное выражение. Таким образом, определено уравнение одной из прямых, ограничивающих область допустимых значений. Аналогично введите остальные ограничения. Введите уравнение 10x + 5y = Cлинии уровня (опорная прямая) целевой функции. Действуйте так же, как и при вводе ограничений, но перед тем как разрешить уравнение относительно y, присвойте какое-нибудь значение константе C. Изобразите на графике соответствующие прямые и определите область допустимых решений системы. Изменяя значения константы C, например C = 100,150,200,250,..., наблюдайте за движением опорной прямой и сформулируйте вывод о разрешимости задачи. Если задача имеет единственное решение, найдите вершину, в которой Z = Zmax. В нашем примере максимум целевой функции достигается в точке пересечения прямых 14x + 5y = 350 и 7x + 14y = 196. Найдите координаты точки, используя функцию Find. Вычислите значение целевой функции в найденной точке.

14x + 5y = 350    (-14/5)x + 70       y1(x):= (-14/5)x + 70
7x + 4y = 196      (-7/4)x + 49         y2(x):= (-7/4)x + 49    

 

x + 2y = 68          (-1/2)x + 34         y3(x):= (-1/2)x + 34
10x + 5y = C       -2x + (1/5)C        y4(x):= -2x + (1/5)C         
C:= 100;

    продолжение
--PAGE_BREAK--
Рис. 4.
Данным
14x + 5x = 360

7x + 4y = 196
Найти (x, y) → (20, 14)

f(x, y): = 10x + 5y

fmin: = f(20, 14)

fmin: = 270

 
Аналитическое решение задачи с применением программы
MATHCAD 2000.


Аналитическое решение задачи в MathCADзначительно проще.


Установите режим автоматических вычислений. Запишите задачу произвольным xи y присвойте произвольные (допустимые) значения, чтобы программа могла начать счет.


Z(x, y): = 10x + 5y

X: = 1y: = 1
Данным
14x + 5x≤ 360

7x + 4y≤ 196

x + 2y≤ 68
M: = Максимизировать (z, x, y)     M = (20, 14)     Z (M0, M1) = 270
Задача максимизации линейной функции при наличии отрицательных свободных коэффициентов
Найти максимум линейной функции
Z = X1 + X2
при ограничениях
X1 – X2 ≤ 3,

X1 + X2 ≥ 5,

2X1 – 3X2 ≤ 6,

X2 ≤ 6,

X1 ≥ 0, X2 ≥ 0.
Запишем систему в виде
Y1 = -X1 + X2 + 3 ≥ 0

Y2 = X1 + X2 — 5 ≥ 0

Y3 = -2X1 + 3X2 + 6 ≥ 0

Y4 = -X2 + 6 ≥ 0
Составим таблицу.





-X1

-X2

1

Y1

1

-1

3

Y2

-1

-1

-5

Y3

2

-3

6

Y4



1

6

Z

-1

-1





В столбце имеется отрицательный элемент “-5”, его надо убрать, чтобы на этом месте был положительный элемент. Совершаем ШМЖИ с разрешающим элементом 1. Получаем таблицу.





-Y1

-X2

1

X1

1

-1

3

Y2

1

-2

-2

Y3

-2

-1

0

Y4



1

6

Z

1

-2

3


Продолжаем работать со 2-й строкой, так как отрицательный элемент не пропал. Совершаем ШМЖИ с разрешающим элементом -2. Получаем таблицу.





-Y1

-Y2

1

X1

1/2

-1/2

4

X2

-1/2

-1/2

1

Y3

-5/2

-1/2

1

Y4

1/2

1/2

5

Z

0

-1

5



Все свободные переменные положительные, находим опорное решение, полагая

Y1 = Y2 = 0, X1 = 4, X2 = 1, Y3 = 1, Y4 = 5. Так как план не оптимальный, то совершаем ШМЖИ с разрешающим элементом 1/2. Получаем таблицу, из которой имеем оптимальное решение X1 = 9, X2 = 6 и Zmax = 15.





-Y1

-Y4

1

X1

1

1

9

X2



1

6

Y3

-2

1

6

Y2

1

2

10

Z

1

2

15


 
Задача минимизации линейной функции
Сведение задачи минимизации к задаче максимизации линейной функции


Мы рассматривали решение симплекс-методом задачи отыскания максимума линейной функции
W = c1x1 + c2x2 + … + cnxn.
Однако во многих экономических задачах требуется найти минимум линейной функции. Для этого достаточно положить
W = -Z = -c1x1 – c2x2 — … — cnxn
и решать задачу максимизации полученной функции W при соответствующих ограничениях. Так как ясно, что
minZ = -maxW.
Минимизировать линейную функцию
Z = -2X1 + 5X2
при выполнении ограничений
7X1 + 2X2 ≥ 14,

5X1 + 6X2 ≤ 30,

3X1 + 8X2 ≥ 24,

X1 ≥ 0, X2 ≥ 0.
Геометрическое решение задачи на (рис. 5) и ему отвечает оптимальное решение в точке

С (48/11, 15/11) и при этом Zmin = -21/11.

Рис 5. Геометрическое решение задачи
Вводя выравнивающие переменные Yi≥ 0 и функцию W = -Z = 2X1 — 5X2 → max, задачу запишем в виде.
Y1= 7X1+ 2X2— 14,

Y2= -5X1 — 6X2 + 30,

Y3 = 3X1 + 8X2 — 24,

W = 2X1 — 5X2.
Записываем эту систему в виде таблицы.





-X1

-X2

1

Y1

-7

-2

-14

Y2

5

6

30

Y3

-3

-8

-24

W

2

5





Так как имеются отрицательные свободные члены, то от них избавляемся. Выбираем наименьший отрицательный член в Y3 – строке и в этой строке берем отрицательный элемент “-8”, который соответствует разрешающему столбцу. Свободные члены делим на соответствующие элементы разрешающего столбца и выбираем наименьшее положительное отношение, тогда Y3 – строка разрешающая. Производя ШМЖИ с разрешающим элементом “-8”, получаем таблицу.





-X1

-Y3

1

Y1

-50/8

-2/8

-8

Y2

22/8

6/8

12

X2

3/8

-1/8

3

W

-31/8

5/8

-15


Избавляемся от отрицательного свободного члена в Y1 – строке, совершая ШМЖИ с разрешающим элементом “-50/8”, получаем таблицу.




-Y1

-Y3

1

X1

-8/50

2/50

64/50

Y2

22/50

32/50

424/50

X2

3/50

-7/50

126/50

W

-31/50

39/50

-52/50


Так как все свободные члены в 1 – столбце неотрицательные, то выбираем разрешающий элемент как в МЖИ для задачи на max. Совершаем ШМЖИ с разрешающим элементом “22/50”, получаем таблицу.




-Y2

-Y3

1

X1

4/11

3/11

48/11

Y1

25/11

16/11

212/11

X2

-3/22

-5/22

15/11

W

31/22

37/22

21/11



Так как в W – строке и в 1 – столбце нет отрицательных элементов, то получили оптимальное решение X1 = 48/11, X2 = 15/11, Wmax – 21/11 или  Zmin = –Wmax = -21/11,
Практическая часть
1.  Решить задачу симплекс методом.
X1 + 3X2 ≤ 300        F = 2X1 + 3X2 →  max

X1 + X2 ≤ 150

X1 ≥ 0

X2 ≥ 0
Решение


X1 + 3X2 + X3 = 300        F — 2X1 — 3X2  = 0

X1 + X2 + X4 =150



Б

С.Ч

X1

X2

X3

X4

X3

300

1

3

1

0

X4

150

1

1

0

1

F

0

-2

-3

0

0
    продолжение
--PAGE_BREAK--