Решение задач линейного программирования
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.
3. Решение задач
3.1. Решение задачи линейного программирования
3.1.1.Постановка задачи
Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции.
Составим целевую функцию и зададим ограничения.
Пусть Х1, Х2, Х3, Х4, Х5 – неизвестные переменные
Целевая
функция: L(Х) = 14
х
-9
х2
- х4+6,4
х5—>
min;
Ограничения:
g1: 0,9
х
+ 10 х2-28х4
+5х5
245,
g2:
0,8
х
+
1,7х2
-0,2х3
-0,5х4
=9,
g3:
6
х
+ 4х3
- 7х4
+ 6,3х5
54,
g4:
8
х
+6,2х2
-4,8х4
+2,9х5
17,
![]()
3.1.2.Ввод данных
1. Введем на рабочий лист Excel необходимые данные. В ячейке В5 запишем выражение целевой функции, а в ячейках В8:В11– левые части ограничений.
2.Командой Сервис, Поиск решения откройем диалоговое окно ІПоиск решенияІ (рис. 2) и заполним его данными. В поле Установить целевую ячейку введем адрес целевой функции $В$5, в поле Изменяя ячейки - адреса $B$3:$E$3. Переведите переключатель Равной в положение минимальному значению.
Чтобы ввести ограничения в окне ІПоиск решенияІ нажмем кнопку Добавить и на экране появится диалоговое окно ІДобавление ограниченияІ .
3. Начнем с первого ограничения. Установим курсор в поле Ссылка на ячейку и, выделяя на листе (рис.1) ячейку В8, введем ее адрес $B$8 в это поле.
Кнопкой-стрелкой откроем список и выберем в нем знак <=. В поле Ограничение установите курсор и, выделяя на листе ячейку D8, введем ее адрес $ D $8 в это поле и нажмем кнопку Добавить.
4. Повторим действия п.3 и введем остальные ограничения $В$9=$D$9, $В$10<=$D$10, $В$11>=$D$11, реализующие граничные условия. После ввода последнего ограничения $F$11<=$H$11 вместо кнопки Добавить нажмем кнопку ОК.
Таким образом, в окно ІПоиск решенияІ (рис. 2) будут введены ограничения.
3.1.3. Решение задачи
1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно ІПараметры поиска решенияІ (рис.4).
В этом окне оставьте неизменными установленные по умолчанию Максимальное время: 100 сек, выделяемое на поиск решения (возможно до 9 часов), Предельное число итераций: 100, Относительная погрешность: 0,000001, Допустимое отклонение: 5%, переключатели в положении линейная, прямые, Ньютона.
Установим флажок Линейная, чтобы обеспечить применение симплекс-метода, и нажмите кнопку ОК.
2. В окне ІПоиск решенияІ нажмите кнопку Выполнить. На экране появится диалоговое окно ІРезультаты поиска решенияІ (рис.5) с информацией «Решение найдено. Все ограничения и условия оптимизации выполнены», подтверждающей успешное решение задачи оптимального распределения ресурсов и количественные результаты (значения переменных, ограничений и целевой функции), приведенные на рис.6.
x1 = А3 = 0, x2 = В3 = 14,43, x3 =С3 = 39,93, x4 =D3 =15,10, x5 =Е3=0
При этом значение целевой функции:
L= В5 = -144,99.
3.1.4. Анализ оптимального решения
Анализ оптимального решения начинается после успешного решения задачи, когда на экране появляется диалоговое окно ІРезультаты поиска решенияІ. С его помощью можно подготовить три типа отчетов: по результатам (опция Результаты), по устойчивости (опция Устойчивость), по пределам (опция Пределы).
1. Подготовим отчет по результатам (рис.7).
Отчет состоит из трех таблиц.
В первой таблице (Целевая ячейка) приводятся сведения о целевой функции: исходное значение (в графе «Исходно») и оптимальный результат (в графе «Результат»).
Во второй таблице (Изменяемые ячейки) приводятся исходные (в графе «Исходно») и полученные в результате решения задачи (в графе «Результат») значения переменных x1, x2, x3, x4, x5.
Третья таблица (Ограничения) отображает результаты оптимального решения, касающиеся ограничений и граничных условий.
2. Щелчком на ярлычке Отчет по устойчивости откроем содержимое отчета на рабочем листе (рис. 8).
Отчет по устойчивости содержит две таблицы.
В первой таблице (Изменяемые ячейки) приводятся следующие значения переменных:
результаты решения задачи (графа «Результ. значение»);
нормированная
стоимость,
т.е. дополнительные
двойственные
переменные
vj,
,
которые показывают,
насколько
изменяется
целевая функция
при принудительном
включении
единицы этой
продукции в
оптимальное
решение;
коэффициенты целевой функции (графа «Целевой коэффициент»);
предельные значения приращения коэффициентов Dcj целевой функции (последние две графы), при которых сохраняется набор переменных, входящих в оптимальное решение.
Во второй таблице приводятся значения ограничений:
значения используемых (графа «Результ. Значение») и заданных (графа «Ограничение, правая часть») ресурсов;
теневая цена, т. е. двойственные оценки zi, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;
значения приращения ресурсов Δbi (последние две графы), при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.
3. Отчёт по переделам (рис.9) показывает, в каких пределах может меняться выпуск продукции, вошедшей в оптимальное решение, при сохранении его структуры:
приводятся значения хi в оптимальном решении (графа «Значение»);
даются нижние и верхние пределы изменения хi и соответствующие значения целевой функции (в графах «Целевой результат»).
3.2. Решение одноиндексной задачи линейного программирования
3.2.1. Построение модели
В данной задаче искомыми неизвестными являются количество полок каждого вида, которые будут произведены в текущем месяце. Таким образом, Х1 – количество полок А(шт./мес.); Х2 – количество полок В1(шт./мес.); Х3 – количество полок В2(шт./мес.).
Целевая функция: Прибыль определяется разностью между ценой и себестоимостью, тогда:
L(х)
= (192-150)х1+(154-120)х2+(147-134)х3 мах
Руб./шт.* шт./мес. =руб./мес.
Ограничения:
Ограничения по фонду времени ( с использованием трудоемкости работ)
3,2 х1
27*8*1*22
ч/шт.* шт./мес.
чел.*
ч/(чел.см.)*см./дн.
* дн./мес.
ч/мес.
ч/мес.
3,2 ч/шт. (Тр1) – это время, затрачиваемое на столярные работы при производстве одной полки типа А;
27 чел. (Р1) – это количество столяров;
8ч/(чел.*см) – количество часов работы 1 человека в течении смены;
1см./дн. – количество смен в одном рабочем дне;
22 дн./мес. – количество рабочих дней в месяце
Необходимо произвести проверку единиц измерения!
Аналогично – упаковочные работы:
6/60х1+9/60х2+10/60х3
7,4*8*1*22
ч/мес.
ч/мес
7 чел. (Р2) – это количество упаковщиков
Ограничение по фонду времени на покрытие лаком полок типа А:
1/2*х1
7,4*1*22
ч/шт.*шт./мес.
ч/см.*см./дн.*дн./мес.
ч/мес.
ч/мес.
1/2 – коэффициент, показывающий количество часов, приходящихся на покрытие лаком одной полки типа А.
Автомат работает в смену 7,4 ч в смену (ФВ1).
Ограничение по фонду времени на резку стекла для полок типа А и В2:
2/180х1+2/180х3
7,1*1*22
ч/шт.*шт./мес.
ч/см.*см./дн.*дн./мес.
ч/мес.
ч/мес.
Ограничения по фонду времени на производство комплектующих полок типа В1 и В2:
1/7х2+1/7х3
7,8*1*22
ч/шт.*шт./мес.
ч/см.*см./дн.*дн./мес.
ч/мес.
ч/мес.
Ограничения по запасу расходуемых в производстве материалов (по запасу используемых для производства полок деталей)..
Целесообразно ориентироваться не на количество листов ДСП, а на количество комплектов для полок, которые можно получить из имеющегося запаса ДСП. Поскольку листы ДСП можно раскраивает различными способами и получать при этом различное количество деталей и комплектов, то обозначим месячный запас комплектов в правой части как Yкомпл и рассмотрим способ его численного определения позже.
1х2+1х3
Yкомпл
Компл./шт.*шт./мес.
Компл./мес.
Компл./мес.
Компл./мес.
Аналогично составляем ограничения по запасу задних стенок из ДВП для полок В1, В2:
1х2+1х3
215*6
Задняя
стенка/шт.*шт./мес.
лист
ДВП/мес.*задняя
стенка/лист
ДВП
Задняя стенка/мес.
Задняя
стенка/мес.
Где 215 – ежемесячный запас листов ДВП
6 – количество задних стенок полок из каждого листа ДВП.
Ограничения по запасу стекол для полок А и В2:
2х1+2х3
240*13
стекло/шт.*шт./мес.
лист
стекла /мес.*стекло
/лист стекла
стекло/мес.
стекло/мес.
Где 240 – ежемесячный запас стекол
13 – количество стекол из каждого листа стекла.
Ограничения по емкости вспомогательных помещений и рынка.
Ограничение по количеству полок А, которые может вместить сушилка:
х1
55*22
шт./мес.
шт./дн.*дн./мес.
шт./мес.
шт./мес.
где 55 – количество полок, которые могут быть просушены в течение месяца.
Ограничение на количество полок всех видов, которые может вместить склад готовой продукции:
х1+х2+х3
370-80+72*22
шт./мес.
шт./мес.-шт./мес.+шт./дн.*дн./мес.
шт./мес.
шт./мес.
Здесь учитывается, что общая емкость склада уменьшается на остаток полок, которые остались невывезенными с прошлого месяца. Кроме того, в течение месяца каждый день будет освобождаться по N мест для полок.
Ограничение по примерной емкости рынка:
х1+х2+х3
1100
шт./мес.
шт./мес.
1100 – емкость рынка по всем видам полок.
Ограничение по гарантированному заказу.
х1
5,
х3
12
шт./мес.
шт./мес.
Необходимо произвести как минимум 5 полок А и 12 полок В3.
Ограничения по соотношению объемов продаж различных товаров.
Процентное отношение количество полок А и В1 ко всему объему продаж:
(х1-5)+х2
0,43[(х1-5)+х2+(х3-12)]
0,57х1+0,57х2-0,43х3 - 2,31
Шт./мес.
шт./мес.
Определение количества комплектов для полок В1 и В2
3.2.2. Первый этап решения задачи
В зависимости от размеров листов ДСП и габаритов полок детали В1 и В2 можно выкроить различными способами. Рассмотрим 3 возможных варианта такого раскроя (рис.10).
L(Y)=Yкомпл
мах комппл./мес.
Согласно 1 варианту из одного листа ДСП для полок В1 и В2 можно выкроить 19 деталей верхней и нижней стенок, а также 9 деталей боковых стенок. По 2 варианту раскроя получаем 12 деталей верхней и нижней стенок и 36 деталей боковых стенок. По 3 варианту раскроя получаем 16 деталей верхней или нижней стенок и 18 деталей боковых стенок.
Обозначим количество листов ДСП, раскроенных в течение месяца : по 1-му варранту через у1(лист./мес.); по 2 варианту – у2(лист./мес.); по 3 варианту – у3(лист./мес.). Таким образом, наша цель – укомплектовка максимального количества полок – описывается целевой функцией:
L(Y)=Yкомпл
мах
Количество всех раскроенных листов ДСП не должно превышать 415, то есть ежемесячный запас их на складе:
у1+у2+у3
415
лист./мес.
Количество верхних и нижних стенок, получаемых при раскрои:
19у1+12у2+16у3
2Yкомпл
дет,мес.
дет./мес.
Ограничение, задающие нижнюю границу количества боковых стенок полок:
9у1+36у2+18у3
2Yкомпл
дет,мес.
дет./мес.
Получаем модель задачи, позволяющую раскроить максимальное количество комплектов:
L(Y)=Yкомпл
мах
у1+у2+у3
415
19у1+12у2+16у3
2Yкомпл
9у1+36у2+18у3
2Yкомпл
у1,у2,у3,Yкомпл
0
Решим данную задачу с помощью функции Поиск решения в MS Excel. Для этого повторим все пункты выполнения работы 3.1.2 – 3.1.3 (рис.11).
3.2.3. Решение исходной одноиндексной задачи
Решив задачу для варианта 0 мы получил значение правой части ограничения Y = 3515 комплектов, после чего решаем исходную задачу, модель которой имеет следующий вид:
L(х) =
42х1+34х2+13х3 мах
3,2х1
4752;
0,1х1+0,15х2+0,167х3
1232;
0,5х1
162,8;
0,011х1+0,011х3
156,2;
0,143х2+0,143х3
171,6;
х2+х3
3515;
х2+х3
1290;
2х1+2х3
3120;
х1
1210;
х1+х2+х3
1874;