Читать учебное пособие по математике: "Алгоритмы по математике" Страница 1

(Назад) (Cкачать работу)

Стандартная форма ЗЛП имеет канонический вид, если в каждом уравнении системы ограничений существует переменная с коэффициентом +1, причем в других ограничениях и в целевой функции этой переменной нет, т.е. коэффициент равен 0. Каноническая форма называется допустимой, если все , иначе - недопустимой.

Алгоритм перехода к стандартной форме ЗЛП

Избавиться от переменных неопределенного знака. Для этого заменить каждую такую переменнуюразностью:, где

Сориентировать целевую функцию , учитывая соотношение.

Используя уравновешивающие переменные, преобразовать имеющиеся неравенства в уравнения.

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

1. Избавиться от переменных неопределенного знака. Для этого необходимо заменить каждую такую переменнуюразностью

, где

Сориентировать целевую функцию , учитывая соотношение

В системе ограничений каждое уравнение без переменной, создающей канонический вид, записать в виде двух неравенств ().

Используя уравновешивающие переменные, преобразовать неравенства в уравнения. При необходимости уравнения можно умножить на (-1).

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

1. Построить область допустимых решений: всем ограничениям системы ограничений ставят в соответствие уравнения, для которых строят прямые; после чего определяют полуплоскости, удовлетворяющие исходным неравенствам системы ограничений.

. Выделить штриховкой область допустимых решений (полученное выпуклое множество).

Построить линию уровня целевой функции .

3. Построить градиент , где .

Градиент перпендикулярен линии уровня.

4. Линию уровня перемещаем до крайней точки допустимой области по направлению градиента (при задании целевой функции на максимум) или антиградиента (при ).

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

Вычислить значение F.

Замечание: если в исходной задаче более двух переменных, то элементарными преобразованиями сводят задачу к двум переменным.

Условием для решения ЗЛП симплекс-методом является наличие модели задачи, записанной в каноническом виде стандартной формы.

Для удобства решения задачи составляют таблицу

0

…

…

…

…

…

…

…

…

В зависимости от знаков(значений свободных членов, стоящих в правых частях системы ограничений) и(коэффициентов целевой функции ) возможны различные методы решения ЗЛП:

Похожие работы