Задача 4. Транспортная задача с правильным балансом
Пункты Отправления Аi |
Пункты назначения Вj |
Запасы Груза ai |
||
В1 |
В2 |
В3 |
||
А1 |
с11 = 4,0 |
с12 = 9,0 |
с13 = 3,0 |
20 |
А2 |
с21 = 4,0 |
с22 = 8,0 |
с23 = 1,0 |
30 |
Потребности в грузе bj |
10 |
30 |
10 |
|
Сформулировать математическую модель задачи как ТЗ. Определить оптимальный план перевозок, при котором общая стоимость перевозок была бы наименьшей.
Решение:
Поскольку данная модель сбалансирована (суммарный объем запасов груза равен суммарному объему потребностей в нём), то в этой модели не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции.
Для решения данной задачи построим ее математическую модель:
Неизвестными в данной задаче являются объемы перевозок. Пусть xij – объем перевозок с i-того пункта отправления в j-й пункт назначения. Функция цели – это суммарные транспортные расходы, т. е. где сij – стоимость перевозки единицы продукции с с i-того пункта отправления в j-й пункт назначения. Неизвестные в данной задаче должны удовлетворять следующим ограничениям:
1. Объемы перевозок не могут быть отрицательными.
2. Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены.
В результате имеем следующую модель:
– минимизировать при ограничениях:
;
;
где aij – запас на i-том пункте отправления, bj – потребность в j-м пункте назначения
Решение задачи с помощью MS Excel
1. Вводим данные, как показано на рис. 4.1.
Рис. 4.1. Исходные данные транспортной задачи
В ячейки А1:С3 введены стоимости перевозок. Ячейки А4:С3 отведены под значения неизвестных (объемы перевозок). В ячейки Е4:Е5 введены объемы запасов в пунктах отправления, а в ячейки А7:С7 введена потребность в пунктах назначения. В ячейку D6 введена целевая функция =СУММПРОИЗВ(А1:C3; А4:C5).
В ячейки А5:C5 введены формулы
=СУММ(А4:А5)
=СУММ(В4:В5)
=СУММ(С4:С5), определяющие объем продукции, ввозимой в пункты назначения.
В ячейки D4:D5 введены формулы
=СУММ(А4:С4)
=СУММ(А5:С5), вычисляющие объем продукции, вывозимой из пунктов отправления.
2. Выбраем команду Сервис/Поиск решения и заполняем открывшееся диалоговое окно Поиск решения как показано на рис. 4.1. В диалоговом окне Параметры поиска решения установливаем флажок Линейная модель.
Рис. 4.2. Диалоговое окно Поиск решения для транспортной задачи
3. Нажимаем кнопку Выполнить и средство поиска решений находит оптимальный план отгрузки продукции и соответствующие ему транспортные расходы (рис. .4.3).
Рис. 4.3. Оптимальное решение транспортной задачи
Задача 5. Оптимизация количества оборудования
В цехе выделено 65 м2 площади на приобретение оборудования (станков). На эти цели предприятие может выделить 100 тыс. ден. ед. Приобретаются станки разных видов с характеристиками:
Вид станка |
Цена станка, тыс. ден. ед. |
Производительность станка, ед. продукции |
Потребная площадь, м2 |
А |
5,6 |
27 |
5,1 |
В |
7,5 |
29 |
3,8 |
Определить количество приобретаемых станков разных видов, чтобы производительность цеха была максимальной. Сформулировать математическую модель задачи как ЦЗЛП.
Решение:
Для решения этой задачи необходимо построить математическую модель.
В данном случае банку необходимо спланировать приобретение станков так, чтобы максимизировать производительность. Поэтому переменными являются: х1 – количество станков А, х2 –количество станков В. Суммарная производительность при покупке новых станков равна z = 27*x1+29*x2. Целью цеха является определение среди всех допустимых значений х1 и х2 таких, которые максимизируют производительность, т.е. целевую функцию z. Ограничения, которые налагаются на х1 и х2:
1. Предприятие на приобретение станков выделяет 100 тыс. ден. ед., следовательно 5,6*х1+7,5*х2 ≤ 100;
2. Под новыестанки в цехе выделено 65м2 площади , то есть 5,1*х1+3,8*х2 ≤ 65;
3. Кроме того, количество станков может быть только целым.
Таким образом, математическая модель данной задачи имеет следующий вид:
Максимизировать функцию 27*x1+29*x2 при следующих ограничениях:
5,6*х1+7,5*х2 ≤ 100;
5,1*х1+3,8*х2 ≤ 65;
х1, х2 – целые числа.
Данная модель является линейной, т.к. целевая функция и ограничения линейно зависят от переменных.
Решение задачи с помощью MS Excel
1. Отведем ячейки A3 и ВЗ под значения переменных х1 и х2 (рис.5.1).
Рис. 5.1. Диапазоны, отведенные под переменные, целевую функцию и ограничения
2. В ячейку С4 введем функцию цели: =27*АЗ+29*ВЗ, в ячейки А6:А7 введем левые части ограничений: 5,6*х1+7,5*х2; 5,1*х1+3,8*х2;, а в ячейки В6:В7 – правые части ограничений (рис. 5.1).
3. Выбираем команду Сервис/Поиск решения и заполняем открывшееся диалоговое окно Поиск решения так, как показано на рис. 5.2. Для ввода ограничений нажимаем кнопку Добавить.
Рис. 5.2. Диалоговое окно Поиск решения
В диалоговом окне Параметры поиска решения устанавливаем флажок Линейная модель (рис. 5.3).
Рис. 5.3. Диалоговое окно Параметры поиска решения
4. После нажатия кнопки Выполнить открывается окно Результаты поиска решения, которое сообщает, что решение найдено (рис. 5.4).
Рис. 5.4. Диалоговое окно Результаты поиска решения
5. Результаты расчета задачи представлены на рис. 5.5, из которого видно, что оптимальным является приоретение 3 станков А и 11 станков В, при этом производительность цеха составит 400 ед. продукции.
Рис. 5.5. Результаты расчета с помощью средства поиска решений для задачи оптимизации количества оборудования