Эквивалентные формы задач линейного программирования

В зависимости от особенностей ограничений различают три эквивалентные формы задач линейного программирования: стандартную, каноническую и общую. Задача (1), (2), (3) имеет стандартный вид. Итак, стандартная задача – это задача с однотипными ограничениями–неравенствами и неотрицательными переменными.

Канонической называется задача, где ограничения системы (2) имеют форму равенств и все переменные неотрицательны. Частным случаем канонической задачи является задача в базисной форме, отличающаяся тем, что все , и в каждом условии имеется переменная с коэффициентом +1, которая не входит ни в одно из остальных уравнений. Переменная с таким свойством называется базисной.

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

Нахождение решения задач линейного программирования

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

При решении задач двумерного пространства в основном применяется графический метод.

Пусть дана задача:

, (4)

(5)

, . (6)

Каждое неравенство системы (5) геометрически определяет полуплоскость с граничной прямой . Условие неотрицательности (6) определяет полуплоскости соответственно с граничными прямыми , . Если система условий задачи совместна (т. е. имеет хотя бы одно решение), то полуплоскости, пересекаясь, образуют общую часть, называемую многоугольником решений (рис. 1).

Рис. 1. Графическое изображение задачи линейного программирования

Линии I, II, III, IV: .

Линия V: .

Линия VI: .

Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

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

Итак, нахождение решения задачи линейного программирования графическим методом включает следующие этапы:

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях (5), (6) знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор .

5. Строят прямую .

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

7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

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

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

(7)

(8)

, , … , , , , … , . (9)

Вычислительная схема симплекс-метода для задачи в базисной форме ( максимизируется):

1. Находят первое опорное решение: , , , … , .

2. Составляют симплекс-таблицу (табл. 1). Первые  строк заполняют, используя запись задачи в базисной форме и найденный опорный план. В столбце  записывают номера строк. В столбце  перечисляются базисные переменные. Соответствующие базисным переменным коэффи­циенты целевой функции заносят в столбец  , а значения базисных переменных при рассматриваемом опорном плане – в столбец  . В столбцах переменных записывают коэффициенты  из системы (8). Показатели -ой строки вычисляют. Для определения значения  используется формула:

, (10)

а для расчёта -оценок – , . (11)

Таблица 1.

Первая симплексная таблица

…

…

…

…

1

…

…

2

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

3. Опорный план проверяют на оптимальность: если все , то задача решена (признак оптимальности для нахождения минимума функции цели – все  ). Если не все , то переходят к шагу 4.

4. Среди значений  находят наибольшее по абсолютной величине (если находится минимум функции цели, выбирают наибольшее значение  из ). Соответствующий ему столбец называется ключевым. Он указывает на переменную, которую необходимо ввести в базис. Пусть это будет столбец с номером  . Если в ключевом столбце все элементы  , целевая функция не ограничена. Решение окончено. Если не все  , то переходят к шагу 5.

5. Для каждого элемента  ключевого столбца находят отношение:

. (12)

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

6. Составляют новую симплекс-таблицу. В столбце  в  -ой строке записывают переменную , а в столбце  – соответствующий ей коэф­фициент  . Остальные элементы столбцов  и  переносят из предыдущей таблицы без изменений. Элементы  и    получают из соответствующих элементов ключевой строки предыдущей таблицы делением их на величину ключевого элемента. В  -м столбце в  -ой строке получается 1, а в остальные строки этого столбца записывают нули. Остальные элементы  и  пересчитывают из элементов предыдущей таблицы по правилу прямоугольника (формулы (13), (14)):

, (13)

. (14)

Для определения показателей оценочной строки снова используют формулы (10), (11) или правило прямоугольника (формулы (15), (16)):

, (15)

. (16)

Переходят к шагу 3.

Пример 1. Решить симплекс-методом задачу:

,

, , .

Приведём задачу к каноническому виду:

,

, , , , , .

Получили задачу в базисной форме, где переменные  – базис­ные. Находим первое опорное решение:  ,    . Значение целевой функции при данном плане равно  .

Используя запись задачи в базисной форме и найденный опорный план, заполняем первые три строки первой симплексной таблицы (табл. 2).

Таблица 2.

Первая симплексная таблица

				-1	3	-1	0	0	0
1	0		7	3	-1	2	1	0	0	–
2	0		12	-2	4 -1	0	0	1	0	3
3	0		10	-4	3	8	0	0	1	10/3
4			0	1	-3	1	0	0	0

Показатели четвёртой строки рассчитываем при помощи формул (10) и (11):

,

,

, , , , .

Так как оценка  отрицательна, то ключевым на данной итерации будет столбец переменной  . Наличие в ключевом столбце положительных элементов позволяет определить ключевую строку. Выбираем её по наимень­шему из отношений  и  . Ключевой элемент  возьмём в рамку.

Переходим ко второй симплексной таблице (табл. 3).

Таблица 3.

Вторая симплексная таблица

				-1	3	-1	0	0	0
1	0		10	5/2	0	2	1	1/4	0	4
2	3		3	-1/2	1	0	0	1/4	0	–
3	0		1	-5/2	0	8	0	-3/4	1	–
4			9	-1/2	0	1	0	3/4	0

В столбце  вместо переменной  записываем переменную  . Соответствующий переменной  коэффициент в столбце  равен 3. Остальные элементы столбцов  и  переносим из предыдущей таблицы без изменений. Элементы  и    получаем из соответствующих элементов первой симплексной таблицы делением их на 4. В столбце переменной  в 1, 3 строках записываем 0. Остальные элементы  и  пересчитываем по формулам (13), (14). Например, для вычисления  находим в таблице 2:

1. число, соответствующее старому значению пересчитываемого элемента (7);

2. число, стоящее на пересечении столбца, в котором расположен пересчитываемый элемент, и ключевой строки (12);

3. число, стоящее на пересечении ключевого столбца и строки, в которой расположен пересчитываемый элемент (-1);

4. число, соответствующее ключевому элементу (4).

Искомый элемент равен:

.

Показатели оценочной строки определим по формулам (10), (11) или (15), (16). Например,

или .

Новый опорный план задачи:  ,  ,  ,  ; (см. столбцы  и  второй симплексной таблицы). Так как в оценочной строке имеется оценка  , то полученное решение не является оптимальным. Наличие в столбце переменной  положительного элемента позволяет перейти к следующему опорному плану:  ,  , , ; (табл. 4).

Таблица 4.

Третья симплексная таблица

				-1	3	-1	0	0	0
1	-1		4	1	0	4/5	2/5	1/10	0
2	3		5	0	1	2/5	1/5	3/10	0
3	0		11	0	0	10	1	-1/2	1
4			11	0	0	7/5	1/5	4/5	0

Значения всех  -оценок неотрицательны, поэтому полученное решение является оптимальным и при этом целевая функция принимает значение .