Лабораторная работа №2. Транспортная задача. Некоторый однородный продукт, сосредоточенный у m поставщиков Ai в количестве ai (i = 1,2, ,m) единиц

Некоторый однородный продукт, сосредоточенный у m поставщиков A_i в количестве a_i (i = 1,2,…, m) единиц, необходимо доставить n потребителям B_j в количестве b_j (j = 1,2,…, n) единиц. Стоимость перевозки единицы груза от i –го поставщика j -му потребителю равна c_ij. Необходимо составить план перевозок, позволяющий при минимальных затратах вывезти все грузы и полностью удовлетворить потребности.

Обозначим через x_ij количество единиц груза, запланированных к перевозке от i –го поставщика к j -му потребителю. Стоимость перевозки этого груза составит c_ijx_ij. Стоимость перевозки всех грузов составит

(1)

Условия задачи требуют учета ограничений:

–все грузы должны быть перевезены, т.е.

i =1,2,…, m, (2)

–все потребности должны быть удовлетворены, т.е.

j =1,2,…, n, (3)

–и, очевидно,

x_ij ³ 0 для всех i =1,2,…, m и j =1,2,…, n. (4)

Математическая модель транспортной задачи может быть сформулирована следующим образом: найти минимальное значение линейной функции (1) при ограничениях (2) – (4).

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

, (5)

называется закрытой моделью. Если условие (5) не выполняется, то модель называется открытой.

Для открытой модели может быть два случая – суммарные запасы превышают суммарные потребности или суммарные потребности превышают суммарные запасы. Открытая модель решается приведением к закрытой модели. Когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, в противоположном случае вводится фиктивный поставщик A_m+1, для которых b_n+1 и a_m+1 равны разности между суммарными поставками и потребностями. Поскольку груз в обоих случаях не перевозится, то стоимость перевозки единицы груза как до фиктивного потребителя, так и от фиктивного поставщика равна нулю.

Математическая модель транспортной задачи имеет n+m уравнений с n´m неизвестными.

Матрицу X=(x_ij)_m,n, удовлетворяющую условиям (2) – (4), называют планом перевозок транспортной задачи. План X^*, при котором целевая функция (1) обращается в минимум, называется оптимальным.