Особые случаи решения ЗЛП графическим методом

Алгоритм решения ЗЛП с двумя переменными графическим методом

1. Построить область допустимых решений (ОДР) ЗЛП.

2. Построить вектор-градиент целевой функции , перпендикулярно ему провести прямую (линию уровня).

3. Перемещать линию уровня в направлении вектора-градиента при решении задачи на max, в обратном направлении – при решении задачи на min.

4. Последняя точка области при этом движении и является точкой оптимального решения.

Возможны следующие особые случаи:

1. Линия уровня параллельна некоторой стороне многоугольника (ОДР). В этом случае каждая угловая точка этой стороны многоугольника и любая точка между ними является оптимальным решением ЗЛП (бесконечное множество решений).

2. ОДР является неограниченной, целевая функция на ОДР не ограничена сверху (задача на max не имеет решения).

3. Система ограничений несовместима, ОДР есть пустое множество (ЗЛП не имеет решения).

8. Основы симплексного метода решения ЗЛП: идеология и общая схема метода. Получение оптимальных решений средствами MS Excel

Сначала кратко напомним некоторые математические понятия и факты.

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

Определение 1. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (свободными).

Определение 2. Базисным решением системы m линейных уравнений с n переменными (m < n) называется всякое её решение, в котором неосновные переменные имеют нулевое значение.

Определение 3. Решение системы m линейных уравнений с n переменными (m < n) называется допустимым, если в нём все основные переменные неотрицательны.

Теорема. Существует взаимнооднозначное соответствие между угловыми точками множества допустимых решений системы m линейных уравнений с n переменными (m < n) и её допустимыми базисными решениями.

Сначала необходимо ЗЛП привести к каноническому виду (КЗЛП).

Доказано, что оптимальное решение ЗЛП (если оно существует и притом единственное) совпадает с одним из допустимых базисных решений системы ограничений, следовательно, с угловой точкой многогранника решений.

Однако для реальных задач число допустимых базисных решений может быть очень велико и провести перебор всех угловых точек многогранника затруднительно. Этот перебор можно сократить, используя идею симплексного метода (метод предложен в 1949 г. американским ученым Дж. Данцигом).

Для реализации симплекс-метода – метода последовательного улучшения плана – необходимо знать три основные операции:

1) способ определения какого-либо первоначального допустимого базисного решения;

2) алгоритм перехода от одного допустимого базисного решения к другому;

3) критерий проверки оптимальности решения.

Замечание. Если первоначальное базисное решение недопустимо, то удобно использовать симплекс-метод с искусственным базисом.

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