10.4. Многоцелевые задачи линейного программирования
Задачи, решаемые с учетом множества показателей или критериев, носят название многоцелевых. Планы задач, полученные по разным критериям, будут отличаться один от другого. Можно для каждого плана определить все интересующие нас показатели, и после их сравнения остановиться на том, который позволяет получить достаточно высокую эффективность всего производства. Если же из полученных планов нельзя выбрать план, который обеспечивал бы необходимую эффективность, можно воспользоваться специальным методом, так называемым методом уступок.
Рассмотрим первый прием на конкретной задаче.
С помощью двух операций производится два вида продукции - А и В. При производстве продукта А на каждой операции затрачивается 3 часа, а при производстве продукта В соответственно 4 и 5 часов. Общее наличие времени для первой и втЬрой операции 18 и 21 час. Стоимость единицы продукции А — 3 руб., а продукции В - 8 руб.
Провести анализ работы предприятия с учетом различных целей:
а) максимум прибыли;
б) максимум выпуска продукции;
в) наилучшее использование оборудования.
Обозначим через хх и х2 количество продукции видов А и В, выпущенных предприятием.
Используя введенные переменные, ограничения можно записать
Зх{ + 4Х2 < 18;
Зх{ + 5Х2 < 21;
Xj >0; х2 > 0.
Полученные ограничения можно записать в виде уравнений
3xj + 4х2 + х3 = 18;
3xj + 5х2 + х4 = 21,
где х3 и х4 выражают неиспользованное время на первой и второй операциях.
Целевые функции согласно трем сформулированным цеЛям можно представить в виде:
а) Zmax = Зх\ + 8х2 +0 • + 0 • х4;
б) Zmax = х, + х2 +0 • х3 + 0 • х4;
в) Zmin = 0 • хх + 0 • х2 + х3 + х4.
Решение задачи «а» представлено в табл.
10.1.Таблица 10.1
Решение задачи по а) критерию 0 3 8 0 0 *2 *з *4 X 0 *з 18 3 4 1 0 26 0 *4 21 3 S 0 1 30 0 -3 -8 0 0 -11 0 *3 6/5 3/5 0 1 -4/5 2 8 *2 21/5 3/5 1 0 1/5 6 168/5 9/5 0 0 8/5 37
В индексной строке нет отрицательных элементов, следовательно, получено решение (план), соответствующее максимальной прибыли:
(0; 21/5; 6/5; 0); Zmax = 33,6.
Анализ решения
Продукция вида А не производится хх = 0, а продукция вида В производится 21/6 единиц.
х3 = 6/5 указывает на то, что по этому плану производственное оборудование при выполнении первой операции простаивает 6/5 ч.
Максимальная прибыль равна 33,6 руб.
Элемент 9/5 в индексной строке указывает на то, что дополнительное производство одной единицы продукции А уменьшает прибыль на 9/5 руб.
Значение индекса 3/5 указывает на то, что дополнительный час работы оборудования при выполнении второй операции увеличивает прибыль на 8/5 руб. Соответственно сокращение времени работы на один час уменьшает прибыль на 8/5 руб.
Решение задачи «б» симплекс-методом представлено в табл. 10.2.
Решение задачи по б) критерию 0 1 1 0 0 *2 *з х4 Z 0 18 ш 4 1 0 26 0 х4 21 3 5 0 1 30 0 -1 -1 0 0 -2 1 6 1 4/3 1/3 0 29/3 0 х4 3 3/05 1 -1 1 4 6 9/05 1/3 І/3 0 20/3
Анализ решения
Производится шесть единиц продукции А X] = 6, продукция вида В не производится х2 = 0.
х3 = 0 производственные мощности при выполнении первой операции используются полностью. х4 = 3 — производственные мощности при выполнении второй операции не использованы в течение 3 часов.
1/3 в столбце х2 показывает, насколько сократился объем продукции, если изготовить единицу продукции вида В. 1/3 в столбце х3 означает, что увеличение времени работы на первой операции (на 1 час) позволит выпустить добавочно 1/3 изделия вида.
Общая прибыль равна 6 • 3 = 18 руб.
Решение задачи «в» симплекс-методом представлено в табл. 10.3.
Анализ решения
Нуль в столбце констант показывает, что имеющиеся мощности используются полностью.
(Время простоя оборудования равно 0).Продукции видаЛ производятся две единицы (х{ = 2), а продукции вида В три единицы (х2 = 3).
Прибыль при осуществлении программы максимального использования оборудования равна 3 • 2 + 3 • 8 = 30 руб.
Для сравнения полученных решений сведем результаты в таблицу (табл. 10.4).
Если оценивать работу предприятия по трем показателям (табл. 10.4), то вполне очевидно, что третий вариант наилучший.
Рассмотрим второй способ (метод уступок), вначале сформулируем алгоритм метода.
Решение задачи по в) критерию 0 0 0 -1 -1 *2 *з х4 Z -1 *з 18 3 4 1 0 26 -1 х4 21 3 ш 0 1 30 -39 -6 -9 0 0 -54 -1 *3 6/5 3/5 0 1 -4/5 2 0 *2 21/5 3/5 1 0 1/5 6 -6/5 ~3/5 0 0 9/5 0 0 2 1 0 5/3 -4/3 10/3 0 *2 3 0 1 -1 1 4 0 0 0 1 1 2
х = (2; 3; 0; 0),
Таблица 10.4
Решение задачи по трем критериям Критерий Количество изделий, ед. Общее количе-ство, ед. Прибыль Неиспользованная мощность А В I II всего Максимум при-были 0 4,2 4,2 33,6 1,2 0 1,2 Максимум про-дукции 6 0 6 18,0 0 3 3 Минимум времени простоя оборудования 2 3 5 30,0 0 0 0
Расположить критерии по их значимости (наиболее важный считается первым).
Решить задачу по первому критерию, Zx = Z* , т. е. отыскать экстремальное значение Z{* целевой функции Zv
Сделать уступку по первому критерию, иными словами, уменьшить величину Zx до значения Zx = К{ Z{*; 0 < К{ < 1.
В задачу ввести дополнительное ограничение Zx > KXZX*.
Решить задачу по второму критерию Z2 = Z2*.
Обратиться к пункту 3, сделать уступку для второго критерия Z2 = K2Z2*; 0 < К2 < 1.
Ввести в задачу дополнительное ограничение Z2 > K2Z2*.
Новую задачу, уже с двумя дополнительными ограничениями, решить по третьему критерию и т. д.
Процесс итерации заканчивается, когда решение будет получено по всем критериям.
Проведем геометрическую интерпретацию этого метода.
Решить задачу по двум критериям, считая первый наиболее предпочтительным. Его отклонение от максимального составляет не более 10%.
Zlmax + ^min = xl + ХЪ
хх + 2х2> 6;
X! < 4;
Х2 * 5; хх > 0; х2 > 0.
Решение
Используя первый критерий, находим область допустимых решений АВСД. Максимальное значение целевой функции достигается в точке С (4,5), представленной на графике (рис. 10.7).
Делаем уступку на 10% fx = 0,9 . 14 = 12,6; получаем дополнительное ограничение хх + 2х2> 12,6 (на рис. 10.7 — прямая). С учетом дополнительного ограничения областью решения является треугольник ЕСК. Минимальное значение целевой функции Zj достигается в точке Е (2,6; 5).
Таким образом, план в точке Е (2,6; 5) будет наиболее эффективным при данных условиях
х = (2,6;5), Zlmax = 12,6; Z2v({m = 7,6.