Алгоритм решения канонической задачи ЛП симплексным методом

Покажем решение данного примера графически.

Пример.

Ответы

Графический способ решения задачи ЛП.

Геометрическая интерпретация решения задачи ЛП.

Дана общая задача ЛП:

(1)

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

;

;

;

;

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

Базис; свободные переменные

Пусть тогда В выражении для F можно увеличивать при этом F будет уменьшаться. Примем будет увеличивать до 5, т.к. при этом Поскольку «ненадежнее» всех в базисе, выведем его из базиса, а в базис введем Выразим F и новые базисные переменные через найдём и подставим его в выражения (1),(2),(3).

В итоге получим:

min(*)

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

.

Допустимое базисное решение следующее:Свободные переменные.

Решая пример далее, видим, что увеличивать нельзя, так как будет возрастатать (а нам нужно минимизировать). Значит. Свободную переменную можно увеличивать, но до иначе будет отрицательна.)

Итак, самая «ненадёжная» переменная Выводим из базиса, а вместо её в базис вводим «провокатора» переменную Свободные переменные.

Из «ненадёжного» уравнения для

находим

и подставляем *). Получим:

Рис.2

min

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

Допустимое базисное решение:

Здесь можно увеличивать до 6, так как

При этом

Достигнуто оптимальное решение: В процессе перехода от одного базисного решения к другому значение F постоянно уменьшалось.

На координатные оси нанесем систему неравенств (см. пример). Выпуклая область (рис.2) соответствует совокупности решений системы неравенств. Минимальное и максимальное значения целевой функции достигаются в точках пересечения этого многогранника решений с «опорными» прямыми, проведенными перпендикулярно вектору Выпишем из базисных решений:

Вектор указывает положительное направление, при движении в котором F увеличивается. Целевая функция задачи ЛП достигает минимума (максимума) в крайней точке выпуклой области. Если F принимает оптимальное значение в нескольких точках, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек (случай, когда целевая функция достигает минимума на грани многогранника) [1]. Множество всех планов задачи ЛП выпукло [1-4]. Отыскание оптимума целевой функции сводится к перебору крайних точек выпуклого многогранника.

Основная задача ЛП называется канонической, если система уравнений каноническая, а целевая функция выражена через свободные неизвестные.

Рассмотрим алгоритм решения канонической задачи ЛП симплексным методом:

Минимизировать

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

;

Это общая задача ЛП. Переходим к каноническому виду:

Дата добавления: 2014-01-06