1.12. Переход к симметричной форме записи
Переход к симметричной форме записи можно осуществить двумя способами.
Первый способ. Пусть в общей задаче линейного программирования имеются ограничения равенства
(
);
Каждое ограничение-равенство эквивалентно системе неравенств:
Неравенство вида умножением обеих частей на –1 превращается в неравенство вида , и наоборот.
Второй способ. Рассмотрим задачу линейного программирования в каноническом виде
при ограничениях
(
);
(
).
Приведем ее к симметричной форме. Пусть ранг системы ограничений равен r.
Определение: Рангом системы уравнений называют количество линейно независимых уравнений.
Если r<n, то система будет иметь бесконечное множество решений. Не ограничивая общности, можно считать, что в матрице системы линейно независимы первые r столбцов. Методом Гаусса систему преобразуем к виду:
(i=
). (1)
Переменные
называют базисными,
- свободными.
Отсюда:
(i=
).
Так как все
переменные
(
),
то можно составить следующие неравенства:
,
(i=
).
Перенесем свободные члены неравенств в левую часть:
,
(i=
).
Целевая функция
в исходной задаче исследуется на max,
следовательно, в системе ограничений
все неравенства должны быть «
».
Для того чтобы полученные неравенства
привести к требуемому виду, умножим обе
части его на –1.
,
(i=
).
Выразим целевую
функцию через свободные переменные.
Для этого подставим значения
из равенств (1) в формулу:
Обозначим:
…………………………………….
Подставим полученные значения в целевую функцию. Получим:
Следовательно, после всех преобразований мы получим следующую задачу линейного программирования:
при
,
(i=
).
(
).
Полученная задача является симметричной.
К данному способу преобразований мы вернемся при изучении симплексного метода решения задач линейного программирования.
Блок 2.
2.1. Геометрическая интерпретация задачи линейного программирования
Одним из возможных вариантов решения задачи линейного программирования является графический метод. Это специальный метод, не предназначенный для решения любых задач. Его можно использовать при решении ЗЛП, в котором всего две переменные. Это условие накладывается потому, что точная графическая интерпретация ЗЛП, позволяющая найти решение, возможна лишь на плоскости.
Пусть задача линейного программирования имеет вид:
при
Для того, чтобы интерпретировать задачу линейного программирования, заданную подобным образом, необходимо интерпретировать систему ограничений и целевую функцию.
Интерпретируем систему ограничений. Каждое неравенство системы ограничений графически представляет собой полуплоскость, пересечение полуплоскостей дает часть плоскости, представляющую собой выпуклый многоугольник, может быть неограниченный с одной из сторон.
Примеры возможных расположений многоугольников:
Рис. 2. Рис. 3.
Рис. 4. Рис. 5.
Рис. 6. Рис. 7.
Следовательно, область допустимых решений задачи линейного программирования может быть: выпуклый многоугольник, неограниченная, выпуклая область, единственная точка, прямая линия, отрезок, пустое множество.
Интерпретируем целевую функцию. Графическая интерпретация целевой функции представляет собой систему параллельных линий. Каждую из них мы назовем линией уровня.