Освоение симплекс-метода решения задач ЛП. Целевая функция и ограничения модели в стандартной форме

Лабораторная работа № 5

Цель работы: Освоить симплекс-метод решения задач ЛП.

Постановка задачи: решить задачу линейного программирования maxF=3x₁+3x₂ симплекс-методом при условиях x₁-4x₂≤4, 3x₁+2x₂≤6, -x₁+x₂≤1, x₁+2x₂≥2 (-x₁+x₂≤3, 4x₁+3x₂≤20)

Ход работы:

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

                    z-3x₁-3x₂                     =0         (целевая функция)

(ограничения).

                                 

x₁-4x₂+s₁                    =4

3x₁+ 2x₂    +s₂             =6

-x1+x2             +s3        =1

x1 +2x2                 +s4   =2    

Как отмечалось ранее, в качестве начального пробного решения используется решение системы уравнений, в которой две (6—4) переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка x₁=x₂=0 сразу же приводит к следующему результату: s₁=4, s₂=6, s₃=1, s₄=2  (т.е. решению, соответствующему точке C на графике из предыдущей лабораторной). Полученные результаты удобно представить в виде таблицы 1.

                        Таблица 1. Исходная симплекс-таблица

Анализируя z-уравнение, нетрудно заметить, что обе небазисные переменные x₁ и x₂, равные нулю, имеют отрицательные коэффициенты. Так как мы имеем дело с задачей максимизации, значение z может быть улучшено при увеличении как x1, так и x2 . Однако всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента (в z-уравнении), так как в этом случае оптимум достигается быстрее. Применяя условие оптимальности к таблице 1, выберем в качестве переменной, включаемой в базис, переменную x₁ . Переменная должна быть выбрана из совокупности базисных переменных s₁, s₂, s₃, s₄. Процедура выбора исключаемой переменной предполагает проверку условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та из переменных текущего базиса, которая первой обращается в нуль при увеличении включаемой переменной x₂ вплоть до значения, соответствующего смежной экстремальной точке. Симплекс-таблица 2, получаемая после проверки условия допустимости (т. е. после вычисления соответствующих отношений и определения исключаемой переменной) приведена ниже.

                              Таблица 2. Определение ведущего элемента

Базисные переменные	X1	X2	S1	S2	S3	S4	Решение b	Отношения
z	-3	-3	0	0	0	0	0	0
S1	1	-4	1	0	0	0	4	4/1
S2	3	2	3	1	0	0	6	6/2
S3	-1	1	0	0	1	0	1	1/1
S4	1	1	0	0	0	1	2	8/2

Из таблицы видно что строка S₂ является ведущей, а столбец X1 является ведущим столбцом, из этого следует, что 3 это ведущий элемент.

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

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

Тип 1 (формирование ведущего уравнения).

Новая ведущая строка = Предыдущая ведущая строка/ Ведущий элемент

Тип 2 (формирование всех остальных уравнений, включая z-уравнение).

Новое уравнение = Предыдущее уравнение—

          Коэффициент

         ведущего столбца

  —    предыдущего             (Новая ведущая строка).  

         уравнения

Процедура 1 приводит к следующим изменениям исходной симплекс-таблицы (таблица 3).

Таблица 3. Новая ведущая строка.

Базисные переменные	X1	X2	S1	S2	S3	S4	Решение   b
Z
S1
X1	1	2/3	0	1/3	0	0	6/2=3
S3
S4

Чтобы составить новую симплекс-таблицу, выполним необходимые вычислительные процедуры типа 2.

1. z-уравнение.

Предыдущее z-уравнение:  (-3   -3   0   0    0    0    0  )

-(-3) × Новая ведущая строка:  ( 3    2    0   1    0    0    9  )

=Новое z-уравнение:        ( 0   -1    0   1    0    0    9  )

2. s₁-уравнение

Предыдущее s₁-уравнение: (1    -4    1    0    0    0    4)

-(1) × Новая ведущая строка:  (-1    -2/3    0    -1/3    0    0    -3)

= Новое s₁-уравнение:       (0    -14/3    1    -1/3    0    0    1)

3. s₃-уравнение.

Предыдущее s₃-уравнение: (-1    1    0    0    1    0    1)

-(-1) × Новая ведущая строка:    (1    2/3    0    1/3    0    0    3) 

= Новое s₃-уравнение:         (0    5/3    0    1/3    1    0    4)

4. s4-уравнение.

Предыдущее s₃-уравнение: (1    1    0    0    0    1    2)

-(1) × Новая ведущая строка:    (-1    -2/3    0    -1/3    0    0    -3) 

= Новое s₃-уравнение:         (0    1/3    0    -1/3    0    1    -1)

Результат вычислений с помощью рассмотренных операций представлен в таблице 4.

Таблица 4. Промежуточное решение.

Базисные переменные	X1	X2	S1	S2	S3	S4	Реше- ние b	Отно-шения
Z	0	-1	0	1	0	0	12
S1	0	-14/3	1	-1/3	0	0	1	1/(-14/3)
X1	1	2/3	0	1/3	0	0	3	3/(2/3)
S3	0	5/3	0	1/3	1	0	4	4/(5/3)
S4	0	1/3	0	-1/3	0	1	-1	-1/(1/3)

В новом решении x₂=1 и x₁=0 (точка A на рисунке предыдущей лабараторной). Из таблицы 4 следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать x₂, так как коэффициент при этой переменной в z-уравнении равен -1. Исходя из условия допустимости, определяем, что исключаемой переменной будет s₁. Отношения, фигурирующие в правой части таблицы 4, показывают, что в новом базисном решении значение включаемой переменной x₂ будет равно -3/14. Оптимальное решение представлено в симплекс-таблице 5 (результирующие значения были найдены по аналогии с предыдущей таблицей).

Таблица 5. Оптимальное решение.

Базисные переменные	X1	X2	S1	S2	S3	S4	Решение b
Z	0	1	-3/14	1/14	0	0	3/14
X2	0	0	3/14	15/14	0	0	3
X1	1	0	1/7	-0,43	0	0	1,3
S3	0	0	0,12	10,7	0	0	4,2
S4	0	0	9/14	-0,54	0	0	5/14

В новом базисном решении x₁=1,3 и x₂=3 (точка В на рисунке