1. Проверка разрешимости транспортной задачи Условие разрешимости транспортной задачи

Если сумма запасов груза равна суммарной потребности в нем: , то транспортная задача является закрытой.

Если сумма запасов не совпадает с суммой потребностей: , то транспортная задача является открытой. При этом возможны два варианта:

а) если , то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется не вывезенной. Для решения задачи вводят фиктивного (n + 1) потребителя, потребности которого .

б) если , то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения такой задачи вводят фиктивного (m+ 1) поставщика, запас которого .

Проверим условие разрешимости транспортной задачи: .

15 + 16 + 15 + 20 = 14 + 11 + 20 + 21; 66 = 66

Условие разрешимости транспортной задачи выполнено.

2. Экономико-математическая модель транспортной задачи.

Обозначим x_ij – количество груза, перевозимого из пункта А_i в пункт B_j:

Объем перевозок	В1	В2	В3	В4	Запасы
А1	6 х11	10 х12	7 х13	5 х14	а1 = 14
А2	10 х21	7 х22	6 х23	9 х24	а2 = 11
А3	13 х31	14 х32	5 х33	7 х34	а3 = 20
А4	5 х41	10 х42	6 х43	4 х44	а4 = 21
Потребности	b1 = 15	b2 = 16	b3 = 15	b4 = 20	-

Примечание. В правом верхнем углу каждой клетки приведены значения тарифа c_ij на перевозку единицы груза из i-го пункта отправления в j-й пункт назначения.

Математическая модель транспортной задачи имеет вид

при ограничениях:

.

Таким образом, целевая функция прямой транспортной задачи имеет вид

Ограничения транспортной задачи:

.

Математическая модель прямой задачи:

x

R=

Математическая модель двойственной задачи:

U – переменные для складов, поставщиков

V - переменные для магазинов, потребителей

U,V

Q=

3. Начальное решение транспортной задачи

Найдем исходное опорное решение по методу минимальной стоимости. Для этого заполним распределительную таблицу:

bj ai		1	2	3	4
		15/	16/	15/	20/
1	14/	6	10	7	5 -
2	11/	10	7	6	9 -
3	20/	13	14	5	7 -
4	21/	5	10	6	4