Вербальная постановка задачи

Планируются перевозки одного вида материально-техни- ческих средств (МТС) от нескольких поставщиков нескольким потребителям. Известны запасы материально-технических средств поставщиков и потребности в МТС потребителей. Из- вестна или может быть вычислена стоимость перевозки едини- цы МТС из каждого исходного пункта (каждого поставщика) в каждый пункт назначения (каждому потребителю). Величина транспортных расходов на любом маршруте прямо пропорци- ональна объему перевозимых МТС. Потребности каждого пот- ребителя могут удовлетворяться за счет нескольких постав- щиков. Цель планирования состоит в определении количества МТС, которые следует перевезти от каждого поставщика каж- дому потребителю, с тем чтобы общие транспортные расходы были минимальными (рис. 10.1).

Неотрицательные переменные xij можно записать в виде матрицы:

 

 

(10.1)

 

 

которую можно обозначить ||Xij ||.

Совокупность неизвестных Xij (10.1), удовлетворяющая ог- раничениям первой и второй групп в (10.2), называется планом перевозок. План, для которого достигается минимум первого выражения в (10.2), называется оптимальным. Величины же Xij называются перевозками.

Поставщики              Потребители

 

a1                                                                                   b1

 

 

ai                                                                                    bi

 

am                                                                                 bn

Рис. 10.1. Организация перевозок МТС:

m — количество поставщиков; n — количество потребителей; ai — запасы МТС i-го поставщика; bj — потребности в МТС

j-го потребителя; cij  — стоимость перевозок;

xij — количество перевозимых МТС

 

В нашем случае математическая постановка транспор- тной задачи линейного программирования в общем виде будет выглядеть следующим образом:

x ^*:

 

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

(10.2)

 

 

x ij ≥ 0 для всех i и j

Первая группа ограничений указывает, что суммарный объем перевозимых МТС от некоторого поставщика не мо- жет превышать сосредоточенных в нем запасов МТС. Вторая группа ограничений требует, чтобы суммарные перевозки

МТС некоторому потребителю полностью удовлетворяли бы его спрос.

Если в задаче (10.2) все неравенства выполняются как ра- венства, т. е. суммарный объем запасов МТС равен суммар- ному спросу, то транспортную модель называют сбалансиро- ванной транспортной моделью. Именно для сбалансированной транспортной модели разработаны эффективные методы ре- шения.

Если суммарный спрос меньше суммарных запасов, т. е.:

то переход к сбалансированной модели осуществляют путем введения в рассмотрение фиктивного потребителя с номером n+1 с заявкой:

При этом стоимость перевозки МТС фиктивному потреби- телю принимается равной нулю (c i, n +1 = 0, ∀ i).

Если  суммарные  запасы  меньше  суммарного  спроса,  т.  е.:

то вводят фиктивного поставщика с номером m + 1 и запасом

при нулевой стоимости перевозок МТС от этого поставщика (c m +1, j = 0, ∀ j).

Следует заметить, что в оптимизационной задаче (10.2)

маршруты перевозок должны быть маршрутами “минималь- ной стоимости”.

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

Поставщики	Потребители
	1		…	n
1		c11	…		c1n
	x11			x1n
…	…		…	…
m		cm1	…		cmn
	xm1			xmn
Потребности	b1		…	bn

 

Приведем наглядный пример: необходимо со склада города (гор.) и области (обл.) перевезти потребное число МТС потреби- телям (потр.). Тогда транспортная таблица будет иметь следу- ющий вид (табл. 10.1):

Таблица 10.1

Поставщик	Потребитель						ВП*
	1		2		3
Склад города		3		5		6	40
Склад области		10		9		12	60
Потребности	25		45		30

*ВП — возможности поставщиков. Стоимость перевозки будет иметь вид:

Сij = νij · Lij,

где Lij — расстояние между i и j пунктами;

νij — стоимость перевозки 1 условной единицы груза на 1 единицу расстояния.

Если νij = 1 условной единице, то Сij = Lij.

 

Решение транспортной задачи

Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут таки-

ми же, как и при решении задачи линейного программирования симплекс-методом, а именно:

I этап. Нахождение начального допустимого решения.

II этап. Выделение из небазисных переменных вводимой в базис переменной (метод потенциалов). Если все небазисные переменные удовлетворяют условию оптимальности, то сле- дует закончить вычисления; в противном случае — перейти к III этапу.

III этап. Выбор выводимой из базиса переменной (исполь- зуя условия допустимости) из числа переменных текущего ба- зиса; затем нахождение нового базисного решения и возвраще- ние ко II этапу.

Рассмотрим подробнее каждый этап решения транспорт- ной задачи, учитывая ее специфику.