Решение транспортной задачи методом потенциалов

- 17 -

Содержание

• Введение 2
• 1.Постановка задачи 3
• 1.1.Назначение и функции программы 3
• 1.2.Математическая модель задачи. 3
• 1.3.Информационная база задачи. 9
• 1.3.1.Входная информация 9
• 1.3.2.Выходная информация 10
• 1.3.3 Контрольный пример 10
• 2.Описание программы 12
• 3.Описание применения 16
• Введение
• Данный курсовой проект представляет собой программу для решения транспортной задачи методом потенциалов. Программа предоставляет пользователю возможность пошагового нахождения оптимального решения, с сохранением отчета в файл. Все промежуточные результаты выводятся на экран, пользователь может следить за ходом решения.
• Транспортная задача заключается в нахождении такого плана поставок, при котором его цена минимальна.
• Условия задачи задаются в виде таблицы:

поставщик	потребитель	Запас груза
	В1	В2	…	Вn
А1	C11 X11	C12 X12	…	C1n X1n	a1
А2	C21 X21	C22 X22	…	C2n X2n	a2
…	…	…	…	…	…
Аm	Cm1 Xm1	Cm2 Xm2	…	Cmn Xmn	am
Потребность в грузе	b1	b2	…	bn

• Матрица (c_ij)_m*n называется матрицей тарифов. Планом транспортной задачи называется матрица х=(x_ij)_m*n, где каждое число обозначает количество единиц груза, которое надо доставить из i-го пункта отправления в j-й пункт назначения.
• 1. Постановка задачи
• 1.1 Назначение и функции программы

Данная программа предназначена для нахождения оптимального решения транспортной задачи, методом потенциалов. При нахождении решения все промежуточные действия( построение контура, вычисление потенциалов, построение нового опорного плана и т.д.) представлены в наглядной форме. Таким образом, эта программа может быть полезна не только для непосредственного получения результата, численного значения максимального потока в данной сети, но и для проверки правильности подсчета без использования ЭВМ.

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

Транспортная задача ставится следующим образом: имеется m пунктов отправления А₁, А₂ , ..., А_{m ,} в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а₁, а₂, ... , а_m единиц. Имеется n пунктов назначения В₁ , В₂ , ... , В_n подавшие заявки соответственно на b₁ , b₂ , ... , b_n единиц груза. Известны стоимости С_i,j перевозки единицы груза от каждого пункта отправления А_i до каждого пункта назначения В_j . Все числа С_i,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Задача о перевозках, в которой сумма запасов ровна сумме заявок:

а_i = b_j ( где i=1,...,m ; j=1,...,n ) (4)

это классическая транспортная задача, иначе называемая, транспортной задачей с правильным балансом. Встречаются такие варианты транспортной задачи где условие (4) нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом.

Баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок

а_i > b_j ( где i=1,...,m ; j=1,...,n );

2. Сумма поданных заявок превышает наличные запасы

а_i < b_j ( где i=1,...,m ; j=1,...,n );

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

Транспортная задача с избытком запасов.

В пунктах A₁, A₂, ... , A_m имеются запасы груза a₁, a₂, ... , a_m; пункты B₁, B₂, ... , B_n подали заявки b₁, b₂, ... , b_n, причём

а_i > b_j ( где i=1..m ; j=1..n ).

Сверх имеющихся n пунктов назначения В₁, B₂, ... , B_n, введём ещё один, фиктивный, пункт назначения B_n+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

b_n+1 = а_i - b_j ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b_n+1 будем считать равным нулю. Введением фиктивного пункта назначения B _n+1 с его заявкой b _n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок .

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A_m+1 с запасом a_m+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо-западного угла”, метод минимального элемента и метод Фогеля. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломанной линией, которая в каждой клетке совершает поворот на 90.

Существует несколько вариантов цикла:

1.) 2.) 3.)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит , чётное число звеньев (стрелок). Условимся отмечать знаком "+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком "-" те вершины , в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть "означенным”. Перенести какое-то количество единиц груза по означенному циклу -- это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце -- заявке этого столбца. Таким образом при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком "+”, а в отрицательных со знаком "-". Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

Метод потенциалов.

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

Пусть имеется транспортная задача с балансовыми условиями

x_i,j = a_i ( i=1..m ; j=1..n );

x_i,j =b_j ( j=1..n ; 1..m ),

причём a_i = b_j .

Стоимость перевозки единицы груза из A_i в B_j равна C _i,j ; таблица стоимостей задана. Требуется найти план перевозок (x_i,j ), который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления A_i вносит за перевозку единицы груза (всё ровно куда) какую-то сумму _i ; в свою очередь каждый из пунктов назначения B_j также вносит за перевозку груза (куда угодно) сумму _j . Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим _i + _j = _i,j ( i=1..m ;j=1..n) и будем называть величину _i,j "псевдостоимостью” перевозки единицы груза из A_i в B_j . Заметим, что платежи _i и _j не обязательно должны быть положительными; не исключено, что "перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (_i и _j ) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (_i и _j ) и псевдостоимости _i,j с истинными стоимостями перевозок C _i,j. Теперь мы установим между ними связь. Предположим, что план (x_i,j) невырожденный (число базисных клеток в таблице перевозок ровно (m + n -1). Для всех этих клеток x_i,j >0. Определим платежи (_i и _j ) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

_i,j = _i + _j = с_i,j , при x_i,j >0.

Что касается свободных клеток (где x_i,j = 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана (x_i,j > 0)

_i + _j = _i,j= с_i,j ,

а для всех свободных клеток ( x_i,j =0)

_i + _j = _i,j с_i,j ,

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

_i,j= с_i,j (для всех базисных клеток ) (1)

_i,j с_i,j ( для всех свободных клеток ) (2)

называется потенциальным планом, а соответствующие ему платежи ( _i и _j ) -- потенциалами пунктов A_i и B_j ( i=1,...,m ; j=1,...,n ). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно -- построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: Какова бы ни была система платежей (_i и _j ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке : _i,j= с_i,j - _i,j.

Таким образом при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем.

В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный методом Фогеля). В этом плане m + n - 1 базисных клеток, где m -- число строк, n -- число столбцов транспортной таблицы. Для этого плана можно определить платежи (_i и _j ), так, чтобы в каждой базисной клетке выполнялось условие :

_i + _j = с_i,j (3)

Уравнений (3) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (3) можно найти остальные платежи _i , _j , а по ним вычислить псевдостоимости: _i,j= _i + _j для каждой свободной клетки.

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

1.3 Информационная база задачи

1.3.1 Входная информация

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

Данные вводятся с клавиатуры:

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

Данные вводятся из файла.

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

Данные хранятся в текстовом файле.

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

1.3.2 Выходная информация

Конечным результатом вычислений является стоимость оптимального плана, сам план поставок.

Промежуточные вычисления выводятся в три таблицы: две матрицы потенциалов, массив перевозок( в котором также отображаются тарифы, полученный план, разность _i,j.

Так же промежуточные вычисления заносятся в файл Word'а, содержащийся в папке с программой и имеющий название test.doc.

1.3.3 Контрольные примеры

Решить транспортную задачу, которая содержится в ниже приведенной таблице:

	25	30	40	15
30	4,5	3,0	2,7	1,5
40	4,2 ]	2,3	4,0	6,2
30	1,6	5,4	3,6	4,4

Решение (взято из отчета выдаваемого программой ):

	25	30	40	15
30	4,5 [3,8]	3,0 [2]	2,7 15	1,5 15	0
40	4,2 [2,2]	2,3 30	4,0 10	6,2 [3,4]	1,3
30	1,6 15	5,4 [3,5]	3,6 15	4,4 [2]	0,9
10	0 10	0 [-0,3]	0 [-2]	0 [-0,8]	-0,7
	0,7	1	2,7	1,5

	25	30	40	15
30	4,5 [3,8]	3 [2]	2,7 15	1,5 15	0
40	4,2 [2,2]	2,3 30	4 10	6,2 [3,4]	1,3
30	1,6 15 (+)	5,4 [3,5]	3,6 15 (-)	4,4 [2]	0,9
10	0 10 (-)	0 [-0,3]	0 (+) [-2]	0 [-0,8]	-0,7
	0,7	1	2,7	1,5

	25	30	40	15
30	4,5 [3,8]	3 [2]	2,7 15	1,5 15	0
40	4,2 [2,2]	2,3 30	4 10	6,2 [3,4]	1,3
30	1,6 25	5,4 [3,5]	3,6 5	4,4 [2]	0,9
10	0 [2]	0 [1,7]	0 10	0 [1,2]	-0,7
	0,7	1	2,7	1,5

	25	30	40	15
30	4,5 [3,8]	3 [2]	2,7 15	1,5 15	0
40	4,2 [2,2]	2,3 30	4 10	6,2 [3,4]	1,3
30	1,6 25	5,4 [3,5]	3,6 5	4,4 [2]	0,9
10	0 [2]	0 [1,7]	0 10	0 [1,2]	-0,7
	0,7	1	2,7	1,5

2. Описание программы

Mas_s - массив содержащий разности потенциалов.

mas_tarif - массив содержащий тарифы перевозок.

mi,mj - номер строки, столбца наиболее потенциальной ячейки.

K - число элементов в контуре.

Stoim - стоимость плана.

ch_sklad,ch_zapros - число поставщиков, число потребителей.

mas_sklad,mas_zapros - массивы, содержащие потребности потребителей, запасы поставщиков.

mas_postavok - план распределения ресурсов.

mas_potz,mas_pots - массивы потенциалов по потребителям, по поставщикам.

A - массив записей, содержащий контур.

procedure rec(n:zap);

Рекурсивная процедура. Строит контур, заносит в массив а адреса всех ячеек плана, больших или равных 0, через которые этот контур проходит. В качестве параметра передается переменная, типа запись, содержащая координаты ячейка, и 4 флага направления(вверх, вправо, вниз, влево). Если флаг направления в 0, значит в этом направлении контур еще не строился.

procedure sij;

Заполняет массив mas_s разностями тарифов и суммой соответствующих потенциалов.

procedure sortmin(_mas_sklad, _mas_zapros: tip1);

Строит опорный план методом минимального элемента. В качестве параметров передаются массив ресурсов поставщиков и массив потребностей потребителей.

procedure sortFog(mas_sklad,mas_zapros:tip1);

Строит опорный план методом Фогеля. В качестве параметров передаются массив ресурсов поставщиков и массив потребностей потребителей.

function naopt:boolean;

Функция проверяет является ли полученный план оптимальным. Если является, то возвращает TRUE, иначе - возвращает false и заносит в переменные mi, mj адрес наиболее потенциальной ячейки плана.

procedure newpl;

На основе контура содержащегося в массиве а строит новый план поставок. Для этого находит в нечетных ячейках массива а ( в которых содержатся адреса ячеек плана, имеющих условный "-" для контура) наименьшее значение, которое затем отнимается от ячеек плана, адреса которых содержатся в нечетных ячейках массива а, и прибавляется к ячейкам, адреса которых содержатся в четных ячейках массива а.

procedure sortygol(_mas_sklad,_mas_zapros:tip1);

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

procedure prov;

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

procedure namn;

Проверяет выполняется ли условие: число заполненных ячеек плана= число поставщиков + число потребителей-1. Если условие не выполняется, то дозаполняет ячейки плана(не образующие контура с ранее заполненными ячейками) нулевыми значениями.

procedure del(f:integer);

Удаляет из массива а элемент,номер которого передается в качестве параметра.

procedure obnyl;

Заполняет все ячейки массива поставок "-1".

procedure ras_pot(var u,v:tip1);

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

procedure ePotrChange(Sender: TObject);

При изменении числа потребителей меняет размерность таблиц.

procedure ePostChange(Sender: TObject);

При изменении числа поставщиков меняет размерность таблиц.

procedure ChangePP(x1,x2:integer);

Изменят размер окна в соответствии с полученными параметрами: числом потребителей, числом поставщиков.

procedure Button2Click(Sender: TObject);

function IsRightKey(var x:char):boolean;

Контроль вводимой информации( только цифры, ",", "-", клавиша Becespace). Возвращает TRUE, если полученный в качестве параметра символ является одним из перечисленных.

procedure sgPlanKeyPress(Sender: TObject; var Key: Char);

Контроль вводимой информации.

procedure Button3Click(Sender: TObject);

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

procedure Button4Click(Sender: TObject);

Строит либо новый план либо новый контур.

procedure stoim;

Рассчитывает стоимость плана.

procedure Button1Click(Sender: TObject);

Закрывает программу.

procedure Button5Click(Sender: TObject);

Сохраняет исходные данные в файл.

procedure Button6Click(Sender: TObject);

Загружает исходные данные из файла.

procedure Button7Click(Sender: TObject);

Вкючает-выключает необходимость выводить в таблицу тарифом разности потенциалов.

procedure wplan;

Выводит в таблицу тарифов контур и при необходимости разность потенциалов.

procedure otch;

procedure FormCreate(Sender: TObject);

3. Описание применения

Данная программа предназначена для решения транспортной задачи методом потенциалов.

При запуске программы на экране появляется следующее окно:

Пользователь может либо вручную ввести необходимые данные либо загрузить сохраненные ранее( кнопка "Load"). После загрузки данных пользователь может внести свои изменения в них.

Пользователю предоставляется возможность сохранить исходные данные в файл( кнопка "Save").

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

Для начала выполнения расчетов необходимо нажать кнопку "Запуск". После чего в таблице тарифов появиться опорный план, а окна и справа от таблицы появятся поля, содержащие потенциалы при данном плане.

Становиться доступной кнопка "Sij on/off". При нажатии на нее пользователь может включить или выключить отображение разностей потенциалов.

Нажимая кнопку "Далее" пользователь может по шагам пройти процесс нахождения оптимального плана. С каждым нажатием в таблице тарифов будет отображаться либо контур, либо новый план. Будет отображаться стоимость плана.

При достижении планом оптимальности пользователь получит об этом сообщение.

После чего пользователь может просмотреть отчет по данной задаче( содержащий начальное условие, все шаги по улучшению плана, оптимальное решение), нажав на кнопку "Отчет". При преждевременном выходе пользователя из программы, отчет будет содержать лишь сведения о проделанных шагах.

Также пользователь может начать решение новой задачи, нажав на кнопку "Новый".