Видеоурок по решению транспортной задачи в Excel с помощью надстройки поиск решения.
Ниже приведены условие задачи, текстовый отчет о решении и видеоурок. Закачка полного решения(документы doc и xlsx в архиве zip) начнется автоматически через 10 секунд.
Условие:
Готовая продукция заводов ai (i=1-3) направляется на склады Bj (j=l-4). Заводы ai производят аi, тыс. изделий. Пропускная способность складов Bj за это время характеризуется величинами bj, тыс. изделий. Стоимость перевозки с завода ai, на склад Bj одной тысячи изделий равна Сij (ден.ед.).
с11 |
с12 |
с13 |
с14 |
а1 |
|
9 |
5 |
1 |
8 |
290 |
с21 |
с22 |
с23 |
с24 |
а2 |
= |
1 |
2 |
4 |
3 |
210 |
с31 |
с32 |
с33 |
с34 |
а3 |
|
3 |
7 |
2 |
6 |
140 |
b1 |
b2 |
b3 |
b4 |
k |
|
250 |
280 |
170 |
100 |
2 |
Требуется:
1) составить экономико-математическую модель задачи, которая позволила бы найти план перевозки готовой продукции заводов на склады с минимальными затратами;
2) методом потенциалов найти оптимальный план перевозки готовой продукции на склады при дополнительном условии, что на складе Вк созданы лучшие условия для хранения готовой продукции, а поэтому он должен быть загружен полностью;
3) найти величину fmin минимальных транспортных затрат;
4) указать склады, пропускная способность которых использована не полностью, и величину резерва складских помещений в них.
Решение:
1. Запишем начальные условия задачи в форме табл. 1.
Табл.1
Мощности заводов Аi, (шт) |
Склады и их спрос |
|||
В1 (250 ) |
В2 ( 280 ) |
В3 (170 ) |
В4 (100 ) |
|
А1 ( 290)
|
9 X11 |
5 X12 |
1 X13 |
8 X14 |
А2 (210 )
|
1 X21 |
2 X22 |
4 X23 |
3 X24 |
А3 (140)
|
3 X31 |
7 X32 |
2 X33 |
6 X34 |
Обозначим через Хij (i = 1,3; j = 1,4) количество изделий, которое планируется перевезти с завода Аi, на склад bj, а через f - общие транспортные затраты.
Целевая функция задачи запишется в виде:
f= 9 • X11 + 5• X12 +...+ 6•X34 (min) (3.1)
Сравнивая суммарную мощность заводов 290+210+140=640 с потребностью
складов bj 250+280+170+100=800 , видим, что эти суммы не совпадают. Следовательно, данная транспортная задача обладает открытой моделью. Часть продукции ( 160 единиц) останется недопоставленной.
Переходя к ограничениям на переменные Хij, следует учесть, что количество продукции, вывозимой из каждого завода Аi, не может превышать мощности производства на этом заводе, т.е.
X11 + X12 + X13+ X14 290
X21 + X22 + X23 + X24 210 (3.2)
X31 + X32+ X33 + X34 140
В то же время склады bj должны быть обеспечены полностью, т.е. сумма поставок, направляемых на каждый склад Bj со всех заводов Аi , должна равняться их потребности. Эти требования можно выразить следующими равенствами:
X11 + X21 + X31 = 250
X12 + X22 + X32 = 280
X13 + X23+ X33 = 170
X14 + X24+ X34 = 100 (3.3)
Если исключить обратные перевозки, то должны выполняться условия
Хij ≥0 (i=1,3; j=1,4) (3.4)
Соотношения (3.1) - (3.4) образуют экономико-математическую модель рассматриваемой задачи.
Таким образом, математическая модель задачи: целевая функция (3.1), описывающая транспортные затраты, минимизируется при ограничениях (3.2) - (3.4).
2. Введем в рассмотрение фиктивный завод А4 с мощностью производства, равной небалансу, т.е.
800-640=160 изделий с одинаковыми затратами на перевозку, равными нулю: C4j= 0 (j=1,4).
Однако по условиям задачи необходимо найти оптимальный план задачи при дополнительном условии, что склад В2 должен быть загружен полностью. Это ограничение будет соблюдено в том случае, если в заключительной таблице с оптимальным планом клетки (4; 2) останутся свободными. Чтобы добиться этого на время решения условно завысим показатель критерия оптимальности в клетках (4 ;2), например, до значения
(+100). Понятно, что теперь занимать клетки (4; 2) будет явно невыгодно.
Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1=3+5-1-7 клеток.
Таблица 2
Мощности заводов Аi, (шт) |
Склады и их спрос |
||||
В1 (250 ) |
В2 ( 280 ) |
В3 (170 ) |
В4 (100 ) |
Ui |
|
А1 ( 290)
|
9
|
5 120 |
1 170 |
8
|
U1= 0 |
А2 (210 )
|
1 50 |
2 160 |
4
|
3
|
U2= -3 |
А3 (140)
|
3 140 |
7
|
2
|
6
|
U3= -1 |
А4 (110)
|
0 60 |
+100
|
0
|
0 100 |
U4= -4 |
Vj |
V1=4 |
V2=5 |
V3=1 |
V4=4 |
|
Построим исходный опорный план методом минимального элемента.
Для исследования плана на оптимальность необходимо найти оценки свободных клеток. Для этого надо знать потенциалы Ui и Vj заводов Аi и складов bj, которые определяются в результате решения системы уравнений
U1 + V2 = 5
U1 + V3 = 1
U2+ V1 = 1 (3.5)
U2+ V2 = 2
U3+ V1 = 3
U4+ V1 = 0
U4+ V3 = 0
составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U1= 0. Тогда остальные неизвестные находятся из системы (3.5): Получаем: U1= 0, U2 = -3, U3 = -1, U4 = -4, V1 = 4, V2 = 5 ,V3 = 1 ,V4 = 4
Теперь можно найти оценки свободных клеток: S11= C11 - (U1 + V1 ) = 9- (0-4) = 13 , S14=4, S23=6, S24=2, S32=3, S33=2, S34=3, S43=3.
Поскольку в табл. 2 свободных клеток с отрицательными оценками
нет, то опорный план является оптимальным. Итак, получен оптимальный
план:
|
0 |
120 |
170 |
0 |
X*= |
50 |
160 |
0 |
0 |
|
140 |
0 |
0 |
0 |
|
|
|
|
|
3. Значение целевой функции - минимальные транспортные затраты -по оптимальному плану составляют:
fmin= 120·5 + 170·1 + 50·1 + 160·2 + 140·3 =1560 ден.ед.
4. Склад В1 недополучит продукции в размере 60 ед., склад В4 недополучит продукции в размере 100 ед..
Имя файла: TranspZ.zip
Размер файла: 25.72 Kb
Если закачивание файла не начнется через 10 сек, кликните по этой ссылке