Каноническая форма задачи ЛП

Для численного решения задачи ЛП требуется предварительно привести ее к каноническому виду:

Каноническая форма задачи ЛП - student2.ru

Каноническая форма задачи ЛП - student2.ru (1)

………………………

Каноническая форма задачи ЛП - student2.ru

Каноническая форма задачи ЛП - student2.ru

Каноническая форма (КФ) (1) задачи характеризуется следующими тремя признаками:

― однородная система ограничений в виде системы уравнений;

― однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче;

― минимизация (максимизация) целевой функции.

Известно, что для произвольной задачи ЛП можно построить эквивалентную ей каноническую задачу ЛП (эквивалентность двух задач означает, что оптимальному решению одной задачи соответствует оптимальное решение другой)[1,2,3].

Пример построения канонической формы

Привести задачу к КФ на минимум:

Каноническая форма задачи ЛП - student2.ru (2)

В данной задаче (2) нарушены все три признака КФ.

1. Начнем с преобразования смешанной системы ограничений в систему уравнений. Для этого введем в первое и второе ограничения неотрицательные переменные y1, y2, которые называются дополнительными или слабыми. В результате система ограничений запишется в следующем виде:

Каноническая форма задачи ЛП - student2.ru (3)

2. Условия неотрицательности в (3) не выполняются только для переменной x2. Для приведения задачи к однородным условиям неотрицательности можно воспользоваться двумя приемами.

Первый прием. Представим переменную x2 в виде разности двух неотрицательных переменных: Каноническая форма задачи ЛП - student2.ru После преобразования системы ограничений и целевой функции получим задачу

Каноническая форма задачи ЛП - student2.ru (4)

Каноническая форма задачи ЛП - student2.ru

Второй прием. Найдем из какого-либо уравнения (4) переменную x2. Пусть из первого уравнения Каноническая форма задачи ЛП - student2.ru . Подставим это выражение во все уравнения и в целевую функцию, исключив таким образом переменную x2 из задачи. Получим

Каноническая форма задачи ЛП - student2.ru (5)

3. Переход к задаче минимизации целевой функции L в задаче (5) осуществляется путем введения новой функции Каноническая форма задачи ЛП - student2.ru из равенства

Каноническая форма задачи ЛП - student2.ru в первом случае,

Каноническая форма задачи ЛП - student2.ru во втором случае.

1.3. Общие рекомендации к графическому решению задач ЛП

1. Графически могут решаться [1]:

a) задачи, заданные в произвольной форме, содержащие не более двух переменных;

b) задачи, заданные в канонической форме, с числом свободных переменных Каноническая форма задачи ЛП - student2.ru ;

c) задачи в произвольной форме записи, которые после приведения к канонической форме будут содержать не более двух свободных переменных Каноническая форма задачи ЛП - student2.ru .

2. Основной формой для графического решения является 1-й тип задач. Поэтому, если встречается 2-й или 3-й тип задач, то предварительно их модель должна быть приведена к первому типу.

3. Решение задач 1-го типа выполняется в два этапа:

этап 1 – построение области допустимых решений;

этап 2 – построение в допустимой области оптимального решения.

4. При построении области допустимых решений может встретиться один из трех случаев:

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

Каноническая форма задачи ЛП - student2.ru

б) выпуклый многоугольник – задача всегда имеет оптимальное решение;

Каноническая форма задачи ЛП - student2.ru

в) неограниченная выпуклая многогранная область – в зависимости от направления вектора c (вектора коэффициентов целевой функции L) задача может иметь или не иметь решение. Последнее связано с неограниченностью целевой функции в области допустимых решений.

Каноническая форма задачи ЛП - student2.ru

5. Если оптимальное решение существует, то возможен один из трех исходов:

а) оптимальное решение единственное и совпадает с одной из вершин области;

Каноническая форма задачи ЛП - student2.ru

б) оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины области Каноническая форма задачи ЛП - student2.ru и Каноническая форма задачи ЛП - student2.ru : Каноническая форма задачи ЛП - student2.ru

Каноническая форма задачи ЛП - student2.ru

в) оптимальные решения соответствуют всем точкам допустимого луча, исходящего из вершины области Каноническая форма задачи ЛП - student2.ru : Каноническая форма задачи ЛП - student2.ru

Каноническая форма задачи ЛП - student2.ru

Пример графического решения

Решить графически задачу ЛП, заданную в канонической форме:

Каноническая форма задачи ЛП - student2.ru (6)

Каноническая форма задачи ЛП - student2.ru

Каноническая форма задачи ЛП - student2.ru (7)

Каноническая форма задачи ЛП - student2.ru (8)

Число уравнений задачи m=3, число неизвестных n=5. Тогда n-m=2 и задача может быть сведена к задаче на плоскости относительно свободных переменных. Возьмем в качестве базисных переменные Каноническая форма задачи ЛП - student2.ru и выразим их через свободные (небазисные переменные):

Каноническая форма задачи ЛП - student2.ru (9)

По условию (8) переменные могут принимать только неотрицательные значения, т. е. допустимой областью задачи ЛП (6) - (8) будет область, определяемая условиями (8), (9), или

Каноническая форма задачи ЛП - student2.ru (10)

Чтобы получить задачу ЛП относительно переменных Каноническая форма задачи ЛП - student2.ru , подставим значения базисных переменных (9) в целевую функцию (6). В результате получим

Каноническая форма задачи ЛП - student2.ru (11)

Задача (10), (11) эквивалентна задаче (6) - (8), поэтому решая графически задачу (10), (11), получим решение задачи (6) - (8).

Этап 1. Построение допустимой области.

Каждое из неравенств (10) определяет некоторую полуплоскость Каноническая форма задачи ЛП - student2.ru :

Каноническая форма задачи ЛП - student2.ru

Так, неравенство Каноническая форма задачи ЛП - student2.ru определяет правую полуплоскость. Неравенство Каноническая форма задачи ЛП - student2.ru определяет полуплоскость, лежащую по ту сторону от прямой Каноническая форма задачи ЛП - student2.ru , где Каноническая форма задачи ЛП - student2.ru . Подставляя значения Каноническая форма задачи ЛП - student2.ru в это неравенство, получим 0>-2, значит, координаты (0,0) удовлетворяют первому неравенству (10) и область решений этого неравенства включает начало координат. Аналогично определяют полуплоскости остальных неравенств (10).

На рисунке прямые, соответствующие условию Каноническая форма задачи ЛП - student2.ru , отмечены цифрой в скобках.

Получили допустимую область M – выпуклый пятиугольник OABCD.

Этап 2. В допустимой области M находим оптимальное решение.

Строим прямую Каноническая форма задачи ЛП - student2.ru и определяем направление возрастания функции Каноническая форма задачи ЛП - student2.ru , это направление вектора Каноническая форма задачи ЛП - student2.ru . Перемещая прямую L параллельно самой себе в направлении вектора Каноническая форма задачи ЛП - student2.ru до тех пор, пока она будет сохранять общие точки с областью допустимых решений, найдем, что в крайнем возможном положении прямая L пройдет через точку Каноническая форма задачи ЛП - student2.ru . Этому положению прямой L соответствует значение Каноническая форма задачи ЛП - student2.ru . Для нахождения координат точки Каноническая форма задачи ЛП - student2.ru необходимо совместно решить систему уравнений граничных прямых, на которых лежит точка Каноническая форма задачи ЛП - student2.ru :

Каноническая форма задачи ЛП - student2.ru

В результате получаем искомое оптимальное решение Каноническая форма задачи ЛП - student2.ru . Подставляя значения Каноническая форма задачи ЛП - student2.ru и Каноническая форма задачи ЛП - student2.ru в целевую функцию и в равенства (9), получим оптимальное значение целевой функции Каноническая форма задачи ЛП - student2.ru и оптимальное решение: Каноническая форма задачи ЛП - student2.ru

Наши рекомендации