--PAGE_BREAK--
Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю — эти величины обозначаются В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые.
Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:
При этом каждый потребитель получает нужное количество продукта:
и каждый поставщик отгружает весь произведенный им продукт:
Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может.
Рассмотрим таблицу.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют свободными, а ненулевые — занятыми (xi,j>0).
Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.
В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д.
Производственно-транспортная задача
Это оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т. е. прикрепления поставщиков к потребителям). Она имеет особое значение для так называемых многотоннажных производств, где важен транспортный фактор (например, черные металлы, минеральные удобрения, нефтепереработка).
Такие задачи математически могут быть представлены в двух видах: в сетевой и в матричной постановке. Будучи основанными на принципах транспортной задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов.
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х517,
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$11, реализующие граничные условия. После ввода последнего ограничения $F$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х37,8*1*22
ч/шт.*шт./мес. ч/см.*см./дн.*дн./мес.
ч/мес. ч/мес.
· Ограничения по запасу расходуемых в производстве материалов (по запасу используемых для производства полок деталей)…
Целесообразно ориентироваться не на количество листов ДСП, а на количество комплектов для полок, которые можно получить из имеющегося запаса ДСП. Поскольку листы ДСП можно раскраивает различными способами и получать при этом различное количество деталей и комплектов, то обозначим месячный запас комплектов в правой части как Yкомпл и рассмотрим способ его численного определения позже.
1х2+1х3 Yкомпл
Компл./шт.*шт./мес. Компл./мес.
Компл./мес. Компл./мес.
Аналогично составляем ограничения по запасу задних стенок из ДВП для полок В1, В2:
1х2+1х3215*6
Задняя стенка/шт.*шт./мес. лист ДВП/мес.*задняя стенка/лист ДВП
Задняя стенка/мес. Задняя стенка/мес.
Где 215 – ежемесячный запас листов ДВП
6 – количество задних стенок полок из каждого листа ДВП.
Ограничения по запасу стекол для полок А и В2:
2х1+2х3240*13
стекло/шт.*шт./мес. лист стекла /мес.*стекло /лист стекла
стекло/мес. стекло/мес.
Где 240 – ежемесячный запас стекол
13 – количество стекол из каждого листа стекла.
· Ограничения по емкости вспомогательных помещений и рынка.
Ограничение по количеству полок А, которые может вместить сушилка:
х1 55*22
шт./мес. шт./дн.*дн./мес.
шт./мес. шт./мес.
где 55 – количество полок, которые могут быть просушены в течение месяца.
Ограничение на количество полок всех видов, которые может вместить склад готовой продукции:
х1+х2+х3370-80+72*22
шт./мес. шт./мес.-шт./мес.+шт./дн.*дн./мес.
шт./мес. шт./мес.
Здесь учитывается, что общая емкость склада уменьшается на остаток полок, которые остались невывезенными с прошлого месяца. Кроме того, в течение месяца каждый день будет освобождаться по N мест для полок.
Ограничение по примерной емкости рынка:
х1+х2+х31100
шт./мес. шт./мес.
1100 – емкость рынка по всем видам полок.
· Ограничение по гарантированному заказу.
х15,
х312
шт./мес. шт./мес.
Необходимо произвести как минимум 5 полок А и 12 полок В3.
· Ограничения по соотношению объемов продаж различных товаров.
Процентное отношение количество полок А и В1 ко всему объему продаж:
(х1-5)+х20,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х14752;
0,1х1+0,15х2+0,167х31232;
0,5х1162,8;
0,011х1+0,011х3156,2;
0,143х2+0,143х3171,6;
х2+х33515;
х2+х31290;
2х1+2х33120;
х11210;
х1+х2+х31874;
х1+х2+х31100;
х15;
х312;
0,57х1+0.57х2+0,43х3-2,31;
х1, х2, х30
Решим задачу с использованием функции Поиск решения в MS Excel аналогично пунктам 3.1.2-3.1.3.
В ячейку Е5 введем целевую функцию, в ячейки В6: В19 – ограничения, переменные будем изменять в ячейках В3: В5 (рис.12).
Решив задачу, получаем:
х1=326шт./мес., х2=762 шт./мес., х3 = 12 шт./мес.,
L(X) = 39753 руб./мес.,
продолжение
--PAGE_BREAK--