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

Методы оптимизации

 

Сборник заданийдля практических занятий

 

 

Омск 2007

Составитель: А. В. Зыкина

 

Данные методические указания предназначены для обеспечения практических занятий по дисциплине «Методы оптимизации». Предлагаемые задания для практических занятий могут быть использованы как варианты для самостоятельной работы.

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

 

Для студентов специальности 230102 и направления подготовки 23010062

 

 

Печатается по решению редакционно-издательского совета Омского
государственного технического университета.

Первый раздел сборника заданий посвящен примерам решения типовых задач.

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

Данные методические указания окажут помощь при выполнении численных расчетов при выполнении задания курсового проектирования по дисциплине «Теория принятия решения», состоящего в построении математической модели практической задачи и численном решении полученной задачи по выбранному алгоритму.

 

ПРИМЕРЫ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ

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

 

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

 

                   (1)

 

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

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

             (2)

 

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

Первый прием. Представим переменную x₂ в виде разности двух неотрицательных переменных:  После преобразования системы ограничений и целевой функции получим задачу

                             (3)

 

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

                 (4)

 

             (5)

 

3. Переход к задаче минимизации целевой функции (4) осуществляется путем введения новой функции  из равенства

в первом случае,

во втором случае.

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

 

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

 

      (6)

 

               (7)

 

                                     

                                            (8)

 

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

                                                                                           (9)

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

                                (10)

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

 

                            (11)

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

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

Каждое из неравенств (10) определяет некоторую полуплоскость :

 

 

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

На рисунке прямые, соответствующие условию , отмечены цифрой в скобках.

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

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

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

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