- •Глава III
- •3.1. Метод жесткого многогранника
- •3.2. Метод случайного поиска
- •Рубежный тестовый контроль
- •2. Метод жесткого многогранника
- •Глава IV. Линейное программирование
- •4.1. Необходимые сведения
- •4.2. Примеры задач линейного программирования
- •4.3. Основная задача линейного программирования (озлп)
- •4.4. Эквивалентная задача линейного программирования
- •4.5. Симплекс-метод
- •4.6. Геометрическая интерпретация задачи линейного программирования
- •Рубежный тестовый контроль
4.6. Геометрическая интерпретация задачи линейного программирования
Воспользуемся эквивалентной постановкой задачи линейного программирования и рассмотрим частный случай . Пусть задача (4.52) – (4.54) имеет следующий вид
(4.71)
(4.72)
Заметим, что всякое выражение вида
д елит плоскость на две полуплоскости так, как это показано на рис. 4.1
Исходя из этого, ограничения (4.71) на плоскости выделят некоторую допустимую область D для переменных , , см. рис. 4.2. Область D выделена жирной линией.
С реди бесконечного количества точек области D, которой принадлежит и граница, нужно найти такую точку, в которой достигает минимума.
Воспользуемся градиентным подходом: выберем произвольную точку , построим антиградиент в этой точке для . Антиградиент направляем по нормали к линии уровня в этой точке. Линия уровня , т.е. есть прямая, где с – произвольная константа.
В любой точке, принадлежащей линии уровня, принимает одно и то же значение, равное с. Так что минимум функции на такой линии искать не приходится, его нужно искать, передвигая линию в плоскости. Для различных с получим набор линий уровня, параллельных друг другу, т.к. угловой коэффициент их один и тот же и равен . Направление убывания величины с указывает антиградиент
,
т.е.
.
Л инии уровня и антиградиент показаны на рис. 4.3.
Смещая прямую параллельно самой себе в направлении антиградиента , будем получать все меньшие и меньшие значения для . Последнее ее положение то, которое связано с точкой (4;4). Это и будет решение задачи линейного программирования. Другими словами, решение задачи линейного программирования достигается в одной из вершин области D, см. рис. 4.2. Этот вывод является общим, т.е. он справедлив для любого . Таким образом, наметим следующий способ решения простейших задач линейного программирования. Необходимо найти значение целевой функции во всех вершинах области D (число вершин всегда конечно, т.к. конечно число ограничений типа неравенств), выбрать вершину с наименьшим значением целевой функции. Эта вершина и будет решением задачи линейного программирования. Из сказанного вытекает, что решение задачи линейного программирования для неограниченной области D может и не существовать. Кроме того, решений может быть и бесчисленное множество, если прямая (плоскость) параллельна одной из сторон (граней) многоугольника (многогранника), ограничивающего область D, рис. 4.4.
Пример. Пусть задача линейного программирования в эквивалентной постановке имеет следующий вид
;
;
; ;
.
Устанавливаем вид области D, рис. 4.5.
И сследуются три точки , , . В этих точках , , .
Точка А – решение задачи линейного программирования. Этот столь простой на первый взгляд метод решения задачи линейного программирования все же не пригоден, если вершин много, т.к. найти координаты их достаточно сложно. Поэтому и применяется симплекс-метод.
Рубежный тестовый контроль
Название раздела «линейное программирование» объясняется тем, что
ограничения типа «равенства и неравенства», а также целевая функция являются линейными;
целевая функция – линейная;
ограничения в виде равенств и они линейные;
отсутствуют ограничения в виде неравенств.
Ранг матрицы это
наибольшее из чисел m и n;
наименьшее из чисел m и n;
наибольший порядок из отличных от нуля миноров этой матрицы;
наибольший порядок минора этой матрицы.
Матричная система линейных уравнений является совместной, если
система имеет хотя бы одно решение;
система имеет хотя бы одно нетривиальное решение;
к системе применима теорема Кронекера-Капелли;
выполняется условие .
Постановка задачи линейного программирования
;
, , ,
является
основной постановкой;
эквивалентной;
не корректной;
не приведенной к стандартному виду.
Для применения симплекс-метода задача линейного программирования
должна быть приведена к основной постановке;
должна иметь форму эквивалентной задачи;
может содержать как равенства, так и неравенства;
должна иметь неизвестных больше, чем количество ограничений в виде равенств.
Геометрическая интерпретация задачи линейного программирования утверждает, что решение задачи линейного программирования
лежит в допустимой области D;
на границе допустимой области D;
в одной из вершин области D;
в наиболее удаленной вершине допустимой области D.