Симплексный метод решения задач

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

Пример 1. Допустим, система ограничений задачи задана следующим образом:

          

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

          

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

Кроме того, для проведения симплекс-метода необходимо, чтобы система равенств – ограничений была записана в так называемом предпочтительном виде.

Это означает:

1. Значения свободных коэффициентов должны быть неотрицательные. Если среди уравнений системы встречаются уравнения с отрицательными , то эти уравнения необходимо умножить на (-1).
2. Матрица коэффициентов окончательно полученной системы ограничения в каноническом виде и с неотрицательными свободными членами должна содержать единичную матрицу размером, равной рангу самой системы уравнений. В этом случае переменные системы можно сразу разделить на базисные и свободные.

Пример 2. Пусть система ограничений задана в виде.

         

Коэффициенты все положительны. Выпишем матрицу системы:

Таблица 1

1 0 0	0 1 0	0 0 1	1 -2 3	-2 1 1	1 2 3

Система содержит единичную матрицу размера 3, равную рангу системы. Можно выделить базисные переменные и свободные . 

Пример.3. Привести систему ограничений к каноническому, предпочтительному виду:

       

Введём дополнительные переменные .

 С помощью них получим  систему:

             

Построим матрицу системы:

  Таблица 2

1	1	1	0	0	6
3	10	0	1	0	26
1	11	0	0	1	20

 

Видно, что матрица содержит единичную матрицу размера 3. Можно выделить базисные переменные и свободные .

Пример 4. Привести систему к каноническому предпочтительному виду.

      

Введём дополнительные неотрицательные переменные .

  Получим:

       

Рассмотрим матрицу системы:

 

 

Таблица 3

2	1	1	0	0	10
-2	3	0	1	0	6
2	4	0	0	-1	8

 

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

  Таблица 4

0	-3	1	0	1	2
0	7	0	1	-1	14
1	2	0	0	-1/2	4

Система содержит единичную матрицу. Базисные переменные , свободные .

Пример 5. Представить систему в предпочтительном виде.

       

          

Система представлена не в предпочтительном виде, т.к. нельзя выделить единичную матрицу и соответственно базисные переменные. Методом Жордана-Гаусса преобразуем систему:

    Таблица 5

1	4	4	1	5
1	7	8	2	9

 

1	4	4	1	5
0	3	4	1	4

 

1	1	0	0	1
0	3	4	1	4

Получим систему, равносильную прежней, но в предпочтительном виде. Базисные переменные , свободные .

Перейдём теперь непосредственно к построению симплекс-таблицы.

Покажем это на конкретном примере.

Пример 6. Найти максимальное значение целевой функции.

         

при условиях:

        

Представим условия ограничения в каноническом виде. Введём дополнительные переменные такие, что

       

Система уравнений представлена в каноническом и предпочтительном виде . можно принять за базисные, причём =360, =193, =180, а свободные переменные . Это одно из допустимых опорных решений. Построим симплекс-таблицу.

 

         Таблица 6

		9	10	16	0	0	0
0		18	15	12	1	0	0	360
0		6	4	8	0	1	0	193
0		5	3	3	0	0	1	180
		-9	-10	-16	0	0	0	0

0		9	9	0	1	-3/2	0	72
16		3/4	1/2	1	0	1/8	0	24
0		11/4	3/2	0	0	-3/8	1	108
		3	-2	0	0	2	0	384

 

10		1	1	0	1/9	-1/6	0	8
16		1/4	0	1	-1/18	5/24	0	20
0		5/4	0	0	-1/6	-1/8	1	96
		5	0	0	2/9	5/3	0	400