Общая постановка задачи. В общем виде задачу можно представить следующим образом: в т пунктах производства А1, А2, , Ат имеется однородный груз в количестве соответственно а1

Лекция 6

-5-

ТРАНСПОРТНАЯ ЗАДАЧА

В общем виде задачу можно представить следующим образом: в т пунктах производства А₁, А₂, …, А_т имеется однородный груз в количестве соответственно а₁, а₂, …, а_т. Этот груз необходимо доставить в п пунктов назначения В₁, В₂, …, В_п в количестве соответственно b₁, b₂, …, b_n. Стоимость перевозки единицы груза (тариф) из пункта А_i в пункт В_j равна с_ij.

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

Определение 1. Если , то задача называется закрытой. Если , то открытой.

Обозначим через х_ij количество груза, перевозимого из пункта А_i в пункт В_j. Рассмотрим закрытую транспортную задачу. Её условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Bj Ai	B1	B2	…	Bj	…	Bn
b1	b2	…	bj	…	bn
A1 a1	c11 x11	c12 x12	…	c1j x1j	…	c1n x1n
A2 a2	c21 x21	c22 x22	…	c2j x2j	…	c2n x2n
…	…	…	…	…	…	…
Ai ai	ci1 xi1	ci2 xi2	…	cij xij	…	cin xin
…	…	…	…	…	…	…
Am am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn

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

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

Оптимальным решением задачи является матрица

удовлетворяющая системе ограничений и доставляющая минимум целевой функции. Для решения транспортной задачи разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:

- нахождение исходного опорного решения;

- проверка этого решения на оптимальность;

- переход от одного опорного решения к другому.

Дата добавления: 2014-01-11