Задание 2. Решение задач линейного программирования графическим методом

1. I Психологические принципы, задачи и функции социальной работы
2. I. 1.1. Пример разработки модели задачи технического контроля
3. I. 1.2. Общая постановка задачи линейного программирования
4. I. 2.1. Графический метод решения задачи ЛП
5. I. 3.1. Двойственная задача линейного программирования
6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
7. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
8. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
9. I. Решение логических задач средствами алгебры логики
10. I. Розв’язати задачі
11. I. Ситуационные задачи и тестовые задания.
12. I. Цель и задачи дисциплины

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

Построим первую прямую . Для этого запишем уравнение в виде: .

При такой форме записи в знаменатели показаны отрезки, которые отсекает прямая на осях координат, поэтому прямая будет проходить через две точки (0;15) и (15;0).

Если от уравнения перейти к неравенству: , то его можно представить графически в виде полуплоскости. Часть плоскости, которая удовлетворяет неравенству, будет лежать по левую сторону от этой прямой, как показано стрелкой. Эта полуплоскость является областью допустимых решений (см. рис. 2.1).

Алгоритм построения остальных прямых-ограничений аналогичен и результат построения показан на рис. 2.2.

Рис. 2.2

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

Полученное таким образом область допустимых решений Р - планов ЗЛП есть многоугольник ABCDE - замкнутое, ограниченное, выпуклое множество с пятью крайними или угловыми точками: A, B, C, D, E.

2 шаг. Строим вектор градиент целевой функции . В условиях примера . Напомним, что этот вектор указывает направление возрастания целевой функции.

3 шаг. Строим прямую - линию уровня (т.е. линию, где функция принимает постоянное значение, ), перпендикулярную вектору-градиенту .

Результаты построений, соответствующие 2 и 3 шагу приведены на рис. 2.3.

Рис. 2.3

4 шаг. Линию уровня целевой функции передвигаем вдоль градиента (в случае её максимизации) или вдоль антиградиента (в случае её минимизации) до тех пор, пока она в какой-нибудь из крайних (или угловых) точек не покинет область Р. Координаты этой точки (функция в ней будет иметь максимальное или минимальное значение) являются оптимальным планом или решением задачи (см. рис. 2.4).

Крайняя точка С - точка минимума ,

лежит на пересечении прямых (3) и (5). Она имеет координаты (2;10), что означает . Подставляя эти значения в целевую функцию, найдем .

Рис. 2.4

Решить задачу линейного программирования в соответствии с номером в журнале группы.