Транспортная задача

Шаг 3:

а) Если невычеркнутой остается в  точности одна строка или столбец, то закончить вычисления.

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

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

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

Последний метод приводит к лучшему  начальному решению, чем два других метода. Однако он сложен для реализации на ЭВМ, так как включает в себя множественные проверки, а также метод наименьшего расстояния. Несмотря на то, что метод наименьших расстояний дает лучшее начальное решение, чем метод «северо-западного» угла, он также сложен из-за большего числа различных проверок и постоянного определения минимума. Первый же рассмотренный метод наиболее прост, так базисное решение получается путем последовательного перехода по столбцам и строкам. Кроме этого стоит учитывать, что алгоритм выбора начального базисного решения не влияет на алгоритм поиска оптимального решения, то есть в любом случае дальнейшее решение задачи происходит по одной и той же схеме. Исходя из этого, при программной реализации задачи для поиска начального решения был выбран метод «северо-западного» угла. Даже если при этом потребуется большее количество итераций для поиска оптимума, более выгодно использовать этот метод, так как даже не самые современные ЭВМ могут мгновенно найти решение даже при большом объеме исходных данных, при этом структура программы будет заметно проще.

 

3.2 Нахождение  вводимой переменной. Метод потенциалов

В методе потенциалов строке i и столбцу j ставятся в соответствие числа U_i и V_j.  Для каждой базисной переменной Х_ij текущего решения потенциалы U_i и V_j   должны удовлетворять условию:

U_i + V_j. =С_ij .                                                   (14)

Оценки для небазисных переменных определяются исходя из формулы:

.                                                  (15)

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

3.3  Поиск выводимой переменной. Построение циклов

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

Не существенно, в каком  направлении происходит обход цикла. Для каждого базисного переменного  и соответствующей небазисной переменной можно построить только один цикл. После построения цикла вводимой небазисной переменной ставится в соответствие знака «+», далее базисным переменным, находящимся в узлах цикла ставятся поочередно знаки «-» и «+». Выводимой переменной считается базисная переменная, имеющая минимальное значение на местах со знаком «-». Далее к базисным переменным, находящимся на местах со знаком «+» прибавляется это значение, из переменных со знаком «-» – вычитается. Вводимой переменной присваивается найденное минимальное значение. После этого происходит переход к предыдущему шагу алгоритма.

 

4 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

 

 

Основные вычислительные процедуры  представлены в приложении 2.

procedure balancing() – проверяет, сбалансирована ли задача. Если нет, то происходит балансировка путем добавления соответственно строки либо столбца.

procedure north_west(ci,ri:byte):real – функция, используемая для нахождения начального базисного решения по методу северо-западного угла.

Входные параметры: ci и ri – номер строки и столбца элемента транспортной таблицы. Функция возвращает значение указанного элемента.

procedure maxnotbas(var max:real;var xi,yi:integer) – процедура нахождения максимальной небазисной переменной. Выходными данными являются сам элемент и его координаты (строка и столбец) в таблице решения.

procedure create_matr(x,x1,y,y1:integer) – процедура, составления матрицы с циклом. Входными данными являются координаты (номера строк и столбцов) двух соседних узлов цикла.

procedure search_uv(q:string) – процедура поиска узлов цикла. Входным параметром является строка, содержащая направление поиска.

procedure TForm1.BitBtn1Click(Sender: TObject) – основная вычислительная процедура, использующая при своей работе выше описанные процедуры и функции. В ней осуществляется проверка вводимой пользователем информации, балансировка задачи, а также реализованы все шаги алгоритма решения транспортной задачи.

 

 

 

 

 

 

5 Экспериментальная проверка и разработка рекомендаций по практическому использованию результатов.

 

 

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

Таблица 1 – Исходные данные

Номер маршрута	Потребность в продукции				Вместимость транспортного средства
	400	500	350	1000
	Пункты назначения
	A	B	C	D
1	1,5	2,5	1,0	2,0	700
2	2,0	3,0	2,0	1,5	650
3	1,0	1,5	2,5	3,0	800

Проведем пошаговые  итерации решения задачи.

1. Сначала нужно проверить сбалансирована ли задача:

400+500+350+1000>700+650+800

Вышеприведенное неравенство  говорит о том, что данная задача не сбалансирована (т.е. для выполнения всех заказов не хватает транспортных средств), откуда следует, что необходимо ввести еще один фиктивный маршрут, т.е. дополнительное транспортное средство с нулевыми затратами на перевозку как показано в таблице 2:

Таблица 2 – Преобразованная исходная таблица

Номер маршрута	Потребность в продукции				Вместимость транспортного средства
	400	500	350	1000
	Пункты назначения
	A	B	C	D
1	1,5	2,5	1,0	2,0	700
2	2,0	3,0	2,0	1,5	650
3	1,0	1,5	2,5	3,0	800
4	0	0	0	0	100

Для проверки правильности балансировки повторим первый шаг толь уже с преобразованной таблицей.

400+500+350+1000=700+650+800+100

Убедившись в том, что  задача сбалансирована, переходим к  следующему шагу.

2. Необходимо найти начальное  допустимое решение. Согласно  описанным выше обстоятельствам это преобразование выполним методом северо-западного угла. В результате получим таблицу 3:

Таблица 3 – Начальное  базисное решение

400-400=0	500-300-200=0	350-350=0	1000-100-800-100=0
400	300			700-400-300=0
	200	350	100	650-200-350-100=0
			800	800-800=0
			100	100-100=0

Выполнив это  действие, мы получили набор базисных переменных: X₁₁, X₁₂, X₂₂, X₂₃, X₂₄, X₃₄, X_44.

И соответственно небазисных переменных:  X₁₃, X₁₄, X₂₁, X₃₁, X₃₂, X₃₃, X₄₁, X₄₂, X₄₃.

3. Далее необходимо  найти вводимую в базис переменную. В случае, когда все небазисные переменные удовлетворяют условию оптимальности, вычисления прекращаются. Если же это не так, то переходим к следующему шагу. Максимальной оценкой для небазисной переменной является X₃₂=3. В виду ее положительности, т.е. неоптимальности решения переходим к шагу 4.

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

Таблица 4 – Построение цикла

400	300
	200-	350	100+
	X+32		800-
			100

В качестве выводимой переменной примем X₂₂, так как она является минимальной среди помеченных знаком «–». Далее от переменных помеченных знаком «–» отнимем значение выводимой переменной, а к переменным, помеченных знаком «+» добавим его следует добавить. В результате получим таблицу 5.

Таблица 5 – Новое базисное решение

400	300
		350	300
	200		600
			100

Опять стоит повторить  шаг 3. Данное решение также не является оптимальным, т.к. X₁₃=3,5>0 и, следовательно, построить цикл, который возвратится в эту переменную – невозможно. Исходя из этого, введем нулевую базисную переменную, и не будем осуществлять вывода. Т.о. получим новое базисное решение представленное в таблице 6.

Таблица 6 – Новое базисное решение

400	300	0
		350	300
	200		600
			100

Полученное новое базисное решение опять не является оптимальным, поэтому введем переменную X₃₁=0,5>0. Для того чтобы найти выводимую переменную необходимо построить цикл приведенный в таблице 7.

Таблица 7 – Построение цикла.

400-	300	0+
		350-	300+
X+ 31	200		600-
			100

Получим новое базисное решение (таблица 8).

Таблица 8 –  Новое базисное решение.

50	300	350
			650
350	200		250
			100

Полученное новое базисное решение снова не является оптимальным, поэтому введем переменную X₁₄=2>0. И опять же для нахождения выводимой переменной необходимо построить цикл приведенный в таблице 9.

Таблица 9 – Построение цикла.

50-	300	350	X+ 14
			650
350+	200		250-
			100