Пример решения задачи. Графический метод решения ЗЛП.
Условие задачи
Цех
изготавливает изделия А и Б. Расход сырья, его запас и прибыль от реализации
каждого изделия указаны в таблице.
|
Вид сырья
|
Расход на изделие
|
Запас
|
|
А
|
Б
|
|
48
|
12
|
600
|
|
24
|
21
|
840
|
|
15
|
27
|
1350
|
|
Прибыль
|
12
|
18
|
|
Найти план производства изделий, обеспечивающий предприятию максимальную прибыль от
их реализации. Решить задачу графическим методом.
Решение задачи
Экономико-математическая модель задачи
Через
и
обозначим количество выпускаемой продукции
вида А и Б соответственно.
Тогда
ограничения на ресурсы:
Кроме
того, по смыслу задачи
Целевая
функция, выражающая получаемую прибыль от реализации изделий:
Получаем
следующую экономико-математическую модель:
Построение чертежа
Для построения области допустимых
решений строим в системе координат соответствующие данным ограничениям-неравенствам
граничные прямые:
Найдем точки, через которые проходят
прямые:
Решением каждого неравенства системы
ограничений ЗЛП является полуплоскость, содержащая граничную прямую и
расположенная по одну сторону от нее.
Для определения полуплоскости
возьмём любую точку, например точку
не
принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к.
неравенство верно:
Области решений соответствующего
1-го неравенства соответствует левая полуплоскость
Возьмём любую точку, например точку
не
принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к.
неравенство верно:
Области
решений соответствующего 2-го неравенства соответствует левая полуплоскость
Для определения полуплоскости
возьмём любую точку, например точку
не
принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к.
неравенство верно:
Области
решений соответствующего 3-го неравенства соответствует нижняя полуплоскость
Областью допустимых решений является
фигура
.
Строим вектор
, координаты которого пропорциональны коэффициентам
целевой функции.
Перпендикулярно к построенному
вектору проводим линию уровня
.
Строим вектор
, координаты которого пропорциональны коэффициентам
целевой функции.
Перпендикулярно к построенному
вектору проводим линию уровня
.
Нахождение оптимального плана
Перемещаем линию уровня
в направлении
вектора так, чтобы она касалась области допустимых решений в крайней точке.
Решением на максимум является точка D, координаты которой находим как точку
пересечения прямой (2) и оси
.
Таким образом, необходимо выпускать
40 ед. изделия Б. Изделие а выпускать невыгодно. При этом прибыль будет
максимальной и составит 720 д.е.