Часть II. Транспортная задача. Методы решения

Транспортная задача. Методы решения

Общая постановка транспортной задачи

Транспортная задача – это классическая задача линейного программирования о нахождении рационального с точки зрения затрат плана перевозок однородного продукта от изготовителя (поставщика) к потребителю.

Общая формулировка транспортной задачи:

Имеется n пунктов – изготовителей однородной продукции (i = 1,2,…,n) и m пунктов – потребителей этой продукции (j=1,2,…,m).

Пусть при одной и той же единице измерения объема продукции объем производства в каждом из пунктов-изготовителей равен a ₁, а ₂,… а _n соответственно, а объем той же продукции, требующийся потребителю - b₁, b₂, … b_m. Стоимость доставки единицы продукции от i –го изготовителя к j –му потребителю известна, ее обозначим через с_ij. Объем поставляемой продукции от i–го изготовителя к j–у потребителю является неизвестной величиной, ее обозначим через х_{i j}.

Требуется определить, какое количество продукции (х_{i j}) и в адрес каких потребите-лей должен отправить каждый из пунктов-изготовителей, чтобы общая сумма затрат на перевозки была минимальной, при этом вся производственная продукция была бы реализована, а заявленная потребность пунктов-потребителей полностью удовлетворена.