|
Целевой функцией в данном случае является прибыль, которую необходимо максимизировать:
ВП = 25 * Х + 40 * У.
Имеются ограничения по производительности сборочного и отделочного цехов:
2 * Х + 4 * У меньше или равно 100;
3 * Х + 2 * У меньше или равно 90,
а также требование неотрицательности элементов – Х, У больше 0.
Решается методом итераций (подбора значений). После каждого шага проверяется соблюдение ограничений. В результате получаем решение Х=20, У = 15. Максимальная прибыль составит 1100 тыс.р. при полной загрузке обоих цехов.
В задачах линейного программирования может представлять интерес вопрос, имеет ли смысл увеличивать объем доступного ресурса. Например, какова цена увеличения рабочего времени в сборочном цехе на один час в неделю. Эта цена – добавочная валовая прибыль, которая может быть получена, называется двойственной оценкой данного ресурса. Двойственную оценку можно рассматривать как упущенную выгоду или как прибыль, недополученную в результате нехватки ресурса. Если в приведенном примере рабочую неделю в сборочном цехе увеличить на восемь часов, то новое оптимальное решение будет выглядеть следующим образом:
Х = 18;
У = 18.
Валовая прибыль при этом составит 1170 тыс.р.
Решение задач линейного программирования может проводиться графическим методом. Для этого найдем в плоскости координат область, соответствующую всем ограничениям.
Первые два ограничения можно представить в виде:
У ≤ 25 – 0,5 * Х;
У ≤ 45 – 1,5 * Х.
Двум оставшимся ограничениям соответствуют сами оси Х и У.
На рисунке линия номер один соответствует первому ограничению, линия номер два соответствует второму ограничению. Очевидно, что допустимая область решений находится в зоне, ограниченной пересечением двух прямых и осей координат.
Какая же точка этой области соответствует оптимальному решению? Целевая функция описывается выражением ВП = 25 * Х + 40 * У или У = ВП – 0,625 * Х .
Переменная ВП должна быть максимальна. График этой функции можно представить несколькими линиями при разных значениях ВП. На рисунке представлены три штриховые линии, соответствующие ВП = 5, 10, 15.
45
2
25
15
10 1
5
8 16 24 30 50
Рис. 3.1. Решение задачи линейного программирования
Нетрудно заметить, что чем дальше от центра координат находится прямая, тем больше значение ВП. Это означает, что функция 25 * Х + 40 * У примет максимально значение в точке пересечении прямых 1 и 2. Координаты этой точки можно найти, решив систему линейных уравнений:
У = 25 – 0,5 * Х У = 15;
У = 45 – 1,5 * Х Х = 20.
Методы динамического программирования применяются при решении задач оптимизации, которая описывается нелинейными функциями. Типичным примером является разновидность транспортной задачи, когда необходимо загрузить транспортное средство различными видами товаров, которые к тому же имеют различный вес, таким образом, чтобы стоимость груза являлась максимальной. Если обозначить:
В – максимальная загрузка транспортного средства;
в – масса одного предмета каждого вида;
с – стоимость предмета каждого вида;
При использовании материалов активная ссылка на источник обязательна.