Материал: 2_Оптимизационные задачи
ТРАНСПОРТНАЯ ЗАДАЧА
Имеется m пунктов A1, … , Am поставщиков однородного продукта и n пунктов B1, … , Bn потребителей этого продукта.
o ai – объем производства в пункте Ai. o bj – объем потребления в пункте Bj.
o cij – стоимость перевозки единицы продукции от Ai в Bj (удельные транспортные издержки).
o ai , bj , cij >= 0.
Требуется найти план перевозок, который:
1.Не выводит за пределы производительности поставщиков
2.Полностью удовлетворяет спрос всех потребителей Минимизирует суммарные транспортные затраты.
Общая модель транспортной задачи в матричной постановке:
m n
F(x) =∑∑cij ×xij →min i=1 j=1
∑n
j =1∑m
i =1
x ij |
= a i |
, |
i 1 : m , |
x ij |
= b j |
, |
j 1 : n , |
x ij |
≥ 0 , |
c ij ≥ 0 . |
|
Предполагается, что ∑m |
a i = ∑n b j |
i =1 |
j =1 |
Задание 6.
С трех баз надо перевезти грузы в два магазина. Количество груза (в штуках) на базах – в таблице:
База 1 |
База 2 |
База 3 |
|
|
|
18 |
75 |
31 |
|
|
|
Потребность магазинов в этих грузах в таблице:
Магазин 1 |
Магазин 2 |
|
|
45 |
79 |
|
|
Стоимость перевозки единицы груза с баз в магазины – в таблице:
|
Магазин 1 |
Магазин 2 |
|
|
|
База 1 |
17 |
6 |
|
|
|
База 2 |
12 |
13 |
|
|
|
База 3 |
9 |
8 |
|
|
|
Определить, сколько груза надо перевезти с каждой базы в каждый магазин, чтобы стоимость перевозки была минимальной.
Примечание. Груз измеряется в штуках, следовательно, решение должно быть получено в целых числах. Для этого необходимо добавить ограничение на проектные параметры – установить, что они должны быть целыми числами (и, естественно, неотрицательными).
Рекомендации по выполнению.
Создать таблицу, как указано на рис. 10. Для ячеек введите следующие формулы:
|
|
|
|
K |
|
|
|
||
|
|
2 |
|
=СУММ(G2:H2) |
|
|
|
||
|
|
3 |
|
=СУММ(G3:H3) |
|
|
|
||
|
|
4 |
|
=СУММ(G4:H4) |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
G |
|
|
H |
|
|
||
6 |
|
=СУММ(G2:G4) |
|
=СУММ(H2:H4) |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
B |
|
C |
|
D |
|
E |
|
9 |
|
=B2*G2 |
|
=C2*H2 |
|
|
|
=СУММ(B9:C9) |
|
10 |
|
=B3*G3 |
|
=C3*H3 |
|
|
|
=СУММ(B10:C10) |
|
11 |
|
=B4*G4 |
|
=C4*H4 |
|
|
|
=СУММ(B11:C11) |
|
12 |
|
|
|
|
|
|
|
=СУММПРОИЗВ(B2:C4,G2:H4) |
|
Рисунок 10 Форма для расчета транспортной задачи
Выполните команду Сервис/Поиск решения… Заполните вызванное окно в соответствии с рис. 11.
Рисунок 11 Окно поиска решения для транспортной задачи
После заполнения окна Поиска решений… перейдите по кнопке Параметры в окно Параметры поиска решений (рис. 4) и установите там флажки напротив полей: Линейная модель и Неотрицательные значения. Далее выполните команду ОК, и нажмите клавишу Выполнить в окне Поиска решений.
В результате выполнения задания должно появиться следующее решение данной оптимизационной задачи рис. 12.
Рисунок 12 Результат выполнения задания 6
Переименуйте Лист 6 в задание_6 и сохраните изменения в файле.
Задание 7.
Три автобазы А1, А2 и А3 предоставляют бульдозеры для работы на четырёх объектах О1, О2, О3 и О4. Число бульдозеров на автобазах представлено в таблице:
А1 |
А2 |
А3 |
|
|
|
11 |
11 |
8 |
|
|
|
Количество бульдозеров, необходимых на объектах – в таблице:
О1 |
О2 |
О3 |
О4 |
|
|
|
|
5 |
9 |
9 |
7 |
|
|
|
|
Время, затрачиваемое бульдозером на переезд с автобаз на объекты, приведено в таблице:
|
О1 |
О2 |
О3 |
О4 |
|
|
|
|
|
А1 |
7 |
8 |
5 |
3 |
|
|
|
|
|
А2 |
2 |
4 |
5 |
9 |
|
|
|
|
|
А3 |
6 |
3 |
1 |
2 |
|
|
|
|
|
Рассчитать, какое количество бульдозеров с каждой автобазы должно быть направлено на каждый объект, чтобы суммарное время, затрачиваемое на переезд, было минимальным. (Число бульдозеров – целое неотрицательное).
Рекомендации по выполнению.
Выполнение задания производиться аналогично заданию 6, правильность найденного решения проверьте согласно рис. 13.