Графический метод решения ПЗЛП

Построение математических моделей. Решение задачи оптимального распределения ресурсов в среде EXCEL

Цель занятия: знакомство студентов с задачами линейного программирования.

Задачи занятия:

- изучение формы моделей задачи линейного программирования (ЗЛП);

- получение навыка решения ЗЛП в среде EXCEL

Методические указания

.

R=

В ячейке А1 введем целевую функцию, в ячейках С1-5 задавая неизвестные пока значения переменных целевой функции:

В ячейке В задаем левые части неравенств системы ограничений:

Через СЕРВИС/НАДСТРОЙКИ установить Поиск решения:

Через СЕРВИС/ПОИСК РЕШЕНИЯ открыть окно поиска решения и выбрать А1 целевой ячейкой:

В окне «Изменяя ячейки» выбираем С1-С5 и вводим ограничения (кнопка ДОБАВИТЬ):

Нажав кнопку ВЫПОЛНИТЬ, получим решение:

Задачи:

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

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

Методические указания

Рассмотрим следующую задачу линейного программирования[1]:

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

Рис. 4.1. Геометрическая интерпретация решения задачи

Геометрическую интерпретацию имеют ЗЛП с двумя переменными.

Исследуем целевую функцию 30 х₁ + 40 х₂. Данной целевой функции соответствует семейство прямых 30 х₁ + 40 х₂ = L, представляющих собой множество параллельных прямых, каждая из которых соответствует определенному значению параметра L. Тогда задачу линейного программирования можно сформулировать следующим образом. Найти такое максимальное значение L, при котором прямая 30 х₁ + 40 х₂ = L пересекает допустимое множество.

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

Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент целевой функции Ñ f (` X) на плоскости Х₁ОХ₂. Этот вектор показывает направление наискорейшего изменения целевой функции, он равен

,

где и - единичные векторы по осям ОХ₁ и ОХ₂ соответственно. Таким образом, Ñ f (` X) = ( ¶ f/ ¶ x<sub>1</sub>, ( ¶ f/ ¶ x<sub>2</sub>). Координатами вектора-градиента целевой функции Ñ f (` X) являются коэффициенты целевой функции f (` X).

В рассматриваемом примере, если двигать прямую 30 х₁ + 40 х₂ = L из начала координат по направлению вектора-градиента целевой функции, то точкой, в которой достигается самая верхняя линия уровня является точка М пересечения прямых 5 x₁ + 2 x₂ = 1000 и x₁ + 2 x₂ = 4000 с координатами x₁ = 1500 и x₂ = 1250. Таким образом, оптимальное решение достигается в точке М (1500; 1250). При этом значение целевой функции составит f (` X^*) =30 * 1500 + 40 * 1250 = 95000.

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

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

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

(7)

1) Форма записи означает, что j принимает последовательно значения 1, 2, 3

[1] Михайлова Э.А., Смирнов А.О. Методы нахождения оптимального управления экономическими системами: пособие для практических занятий / РГАТА. Кафедра экономики. - Рыбинск, 1998. - 42 с.

Дата добавления: 2014-12-27