Транспортная задача и ее решение методом потенциалов, Постановка задачи и ее математическая модель - Транспортная задача и ее решение методом потенциалов

Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее рационального прикрепления пунктов отправления грузов (поставщиков) к пунктам их назначения (потребителям), чтобы общая стоимость транспортировки грузов была минимальной. Первая строгая постановка задачи была дана Хичкоком, а точный универсальный метод ее решения разработан советскими учеными Л. В. Конторовичем и М. К. Гавуриным.

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

Пусть в пунктах A1, A2, ..., Am производят некоторый однородный продукт в количествах a1, a2, ..., am соответственно. Этот продукт следует перевезти в пункты B1, B2, ..., Bn, потребляющие его соответственно в количествах b1, b2, ..., bn..

Пункты Ai () называются пунктами отправления или поставщиками, а пункты Bj () - пунктами назначения или потребителями. Рассмотрим сначала случай, когда суммарный объем производства равен суммарному объему потребления, т. е.

Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке из пункта Ai в пункт Bj единицы продукции равны cij (,). Значения cij будем называть тарифами. Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Переменные xij будем называть перевозками.

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

Условия T. З. удобно записывать в таблице следующего вида:

Таблица 1.1

Потребители

B1

B2

...

Bj

...

Bn

Постав-

Щики

Bj

Ai

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

В таблице 1.1 каждая клетка (i, j), соответствующая паре i-й поставщик - j-й потребитель, условно делится диагональю пополам и в правом верхнем углу записывается значение тарифа cij, а в левом нижнем - значение перевозки xij.

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

Xij ? 0, ;

Z = c11x11 + c12x12 + ... + c1nx1n + c21x21 + c22x22 + ... + c2nx2n + ... + cm1xm1 + cm2xm2 + ... + cmnxmn > min.

С помощью индексов суммирования эта модель запишется так:

Xij ? 0, ; (1.1)

(1.2)

> min. (1.3)

Условия (1.1) - условия неотрицательности перевозок (обратная транспортировка груза от потребителя к поставщикам запрещена).

Условия (1.2а) характеризируют полный вывоз продукта от поставщиков, а условия (1.2б) - полное удовлетворение запросов потребителей.

Суммарная стоимость Z транспортировки продукта согласно условию (1.3) должна быть минимальной.

Совокупность переменных xij, удовлетворяющих условиям (1.1) и (1.2), будем называть планом перевозок T. З. и записывать его в виде матрицы:

.

Совокупность тарифов сij будем записывать в виде матрицы, которую назовем матрицей тарифов:

.

Запишем систему ограничений T. З. в векторной форме. Обозначим столбец коэффициентов при xij через, а столбец сводных членов - через, тогда:

У вектора i-я и (m + j)-я компоненты равны единице, остальные компоненты равны нулю.

Система ограничений (1.2) T. З. в векторной форме будет иметь вид:

(1.4)

Похожие статьи




Транспортная задача и ее решение методом потенциалов, Постановка задачи и ее математическая модель - Транспортная задача и ее решение методом потенциалов

Предыдущая | Следующая