На складах трех поставщиков А1 А2 А3 хранится 190
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
На складах трех поставщиков А1,А2,А3 хранится 190, 290, 280 тонн одного и того же товара. Этот товар требуется доставить четырем потребителям В1,В2,В3, В4, заказы которых составляют 270, 140, 180, 160 тонн товара соответственно. Стоимости перевозок Сij с тонны товара с i-го склада j-му потребителю составляют С11=1б С12=7, С13=3, С14=3, С21=2, С22=3, С23=10, С24=4, С31=8, С32=4, С33=8, С34=5.
1.Выяснить , является задача открытой и закрытой.
2. Составить первоначальный план с помощью метода северо-западного угла.
3. Составить первоначальный план с помощью метода наименьше стоимости.
4. С помощью метода потенциалов найти оптимальный план перевозок, обеспечивающий их минимальную стоимость
5. Найти минимальную стоимость перевозок.
Нужно полное решение этой работы?
Ответ
минимальная стоимость перевозок 1950 ден ед, Х=100090017012000002000901600
Решение
1.Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 190 + 290 + 180 = 660
∑b = 270 + 140 + 180 + 160 = 750
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 90 (660—750). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 Запасы
A1 1 7 3 3 190
A2 2 3 10 4 290
A3 8 4 8 5 180
A4 0 0 0 0 90
Потребности 270 140 180 160
2. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 Запасы
A1 1[190] 7 3 3 190
A2 2[80] 3[140] 10[70] 4 290
A3 8 4 8[110] 5[70] 180
A4 0 0 0 0[90] 90
Потребности 270 140 180 160
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. F(x) = 1*190 + 2*80 + 3*140 + 10*70 + 8*110 + 5*70 + 0*90 = 2700
3. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 Запасы
A1 1[190] 7 3 3 190
A2 2[80] 3[140] 10 4[70] 290
A3 8 4 8[90] 5[90] 180
A4 0 0 0[90] 0 90
Потребности 270 140 180 160
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7
. Следовательно, опорный план является невырожденным. F(x) = 1*190 + 2*80 + 3*140 + 4*70 + 8*90 + 5*90 + 0*90 = 2220
4.Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
v1=1 v2=2 v3=6 v4=3
u1=0 1[190] 7 3 3
u2=1 2[80] 3[140] 10 4[70]
u3=2 8 4 8[90] 5[90]
u4=-6 0 0 0[90] 0
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;3): 0 + 6 > 3; ∆13 = 0 + 6 - 3 = 3 > 0
1 2 3 4 Запасы
1 1[190][-] 7 3[+] 3 190
2 2[80][+] 3[140] 10 4[70][-] 290
3 8 4 8[90][-] 5[90][+] 180
4 0 0 0[90] 0 90
Потребности 270 140 180 160
Цикл приведен в таблице (1,3 → 1,1 → 2,1 → 2,4 → 3,4 → 3,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Хij, стоящих в минусовых клетках
Задать вопрос
на новый заказ в Автор24.
