Сборник задач по линейному программированию (стр. 9 )

       

       

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

Исходные условия задачи линейного программирования могут быть представлены в различных видах.

1. В симметричном (или стандартном) виде. В этом случае условия ограничения заданы в виде неравенств:

где - заданные постоянные величины.

       2. В каноническом виде: все ограничения заданы в виде равенств:

                       II

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

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

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

 

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

 

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

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

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

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

Пример 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

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