II.1.3. Решение транспортной задачи в QSB.

Для вызова программы транспортной задачи необходимо в главном меню QSB выбрать пункт «3-Transportation problem» и войти в меню транспортной задачи, представленное на Фиг. 1.

Welcome to your Transportation Problem (TRP) Decision Support system! Приглашаем Вас в Транспортную задачу системы поддержки решений! The options available for TPR are as follows. Для транспортной задачи возможны следующие режимы. If you are first-time user, you might benefit from option 1. Если Вы начинающий пользователь, то Вы должны выбрать режим 1.
Option Режим	Function Функция
	Overview of TPR Decision Support System Обзор транспортной задачи системы поддержки решений
	Enter new problem Введите новую задачу
	Read existing problem from disk(ette) Чтение существующей задачи с диска (дискеты)
	Display and/or print input data Просмотр и(или) печать исходных данных
	Solve problem Решение задачи
	Save problem on disk(ette) Сохранение задачи на диске (дискете)
	Modify problem Изменить задачу
	Display and/or print final solution Просмотр и(или) печать окончательного решения
	Return to the program menu Возврат в программное меню
	Exit from QSB Выход из QSB

Передвигая курсор вверх или вниз выберите режим и нажмите ENTER

Фиг. 1. Меню транспортной задачи.

Обзор транспортной задачи показан на Фиг. 2. Для просмотра обзора необходимо выбрать пункт 1 в меню транспортной задачи.

Overview of TPR Decision Support System Обзор транспортной задачи системы поддержки решений

The program solves transportation problems with up to 50 sources Эта программа решает транспортные задачи, имеющие до 50 поставщиков и до 50 потребителей. and 50 destinations. The capacities of the sources and the demands of Запасы поставщиков и потребности потребителей предполагаются целочисленными; коэффициенты the destinations are assumed to be integer; the cost/profit coefficients стоимости или прибыли предполагаются вещественными величинами. Транспортная задача имеет простой are assumed to be real valued. TRP provides an easy format to enter формат для ввода или изменения исходных данных. and/or modify the input data. Also, problems can be saved on or read Задача может быть записана или прочитана с диска (дискеты). from disk(ette). For small problems with up 4 sources and 5 destinations, you have Для небольших задач, имеющих до 4 поставщиков и 5 потребителей Вы имеете режим, показывающий the option of displaying every iteration of the Modified Distribution каждую итерацию модифицированного распределительного (МОДИ) метода. (MODI) method. However, your TRP can solve much larger problems. Однако, Ваша программа может решать задачи большего размера. You can also select either Vogel's Approximation Method (VAM) or the Вы также можете выбрать либо метод аппроксимации Фогеля или North-West Corner method (NWC) for the initial feasible solution. After метод Северо-западного угла для нахождения начального допустимого решения. После the problem has been solved, you can display and print the final получения результата, Вы можете просмотреть и напечатать окончательное решение. solution. The TRP Decision Support System allows you to define names of Транспортная задача системы поддержки решений позволяет описать имена поставщиков и потребителей sources and destinations with up to 6 characters. The default names are длиной до 6 знаков. Стандартные имена поставщиков и потребителей . and . Any time you want a copy of the Если Вы хотите напечатать содержимое экрана, то нажмите функциональную клавишу F8. output on the screen, press the function key F8.   Enjoy using your TRP Decision Support System! Успехов в работе с транспортной задачей системы поддержки решений!

Press any key to return to the function menu.

Нажмите любую клавишу для возврата в функциональное меню.

Фиг. 2. Обзор транспортной задачи

Если выбрать пункт 2 меню ТЗ, то на экран выводится запрос имени задачи, а затем - маска для ввода параметров задачи, показанная на Фиг. 3. Эта маска содержит некоторые пояснения о порядке ввода исходных данных. Добавление фиктивных поставщиков или потребителей для несбалансированных задач производится программой автоматически.

Если необходимо ввести нестандартные имена поставщиков или потребителей, то после ответа «N» на экран выводится маска для ввода этих имен, показанная на Фиг. 4.

TRP Model Entry for hhh Ввод модели транспортной задачи для <имя задачи>   Please observe the following conventions when entering a problem: Пожалуйста, посмотрите следующие условия ввода задачи:
	Respond to the questions which seek general information about Необходимо ответить на вопросы, которые содержат общую информацию о задаче. the problem.
	Then enter the names of sources and destinations, unless using Затем введите имена поставщиков и потребителей, если они нестандартные. defaults.
	Then enter the supplies, demands and cost/profit coefficients. Затем введите запасы, потребности и коэффициенты стоимости/прибыли.
	After you enter your data, press the ENTER key. После ввода Ваших данных, нажмите клавишу ENTER.
	On the same screen page, you may correct errors by pressing the На той же странице экрана Вы можете исправлять ошибки путем использования клавиши BACKSPACE key to move the cursor to the correct position. BACKSPACE для подвода курсора к исправляемой позиции.
	When you are satisfied with the data on a page, press the Если Вы удовлетворены данными на текущей странице, нажмите клавишу SPACE BAR. «пробел».
	When entering a problem, press the Esc key to go to the previous При вводе задачи используйте клавишу Esc для перехода к предыдущей странице или page; press the «/» key to go to the next page. Клавишу «/» для перехода к следующей странице.
Do you want to maximize (1) or minimize (2) criterion? (Enter 1 or 2) < > Вы желаете минимизировать (1) или максимизировать (2) функцию цели? (Введите 1 или 2) How many sources are in your problem? (Enter number ) < > Сколько поставщиков в Вашей задаче? (Введите число до 50) How many destinations are in your problem?(Enter number ) < > Сколько потребителей в Вашей задаче? (Введите число до 50) Do you want to use the default names (Y/n)? < > Желаете ли Вы использовать стандартные имена ?

Фиг. 3. Ввод параметров транспортной задачи

Enter the Names of Sources and Destinations using at most 6 characters. Введите имена поставщиков и потребителей длиной не более 6 знаков. (To the default names, i.e., , press the ENTER key) (При использовании стандартных имен, то есть , нажмите ENTER)
Sources: Поставщики:
	1: < > 2: < > 3: < >
Destinations: Потребители:
	1: < > 2: < > 3: < > 4: < >

Фиг. 4. Ввод нестандартных имен поставщиков и потребителей

На Фиг.5. показана маска для ввода запасов поставщиков и потребностей потребителей, а на Фиг. 6. - коэффициентов стоимости (при минимизации) или прибыли (при максимизации) от перевозки единицы груза.

Sources: Поставщики:
	________ ________ ________
Destinations: Потребители:
	________ ________ ________ ________

Фиг. 5. Ввод запасов и потребностей

Enter the Cost/Profit Coefficient of the TRP Model Введите коэффициенты стоимости/прибыли модели транспортной задачи	Page 1 Страница 1
From Откуда	To Куда
	:________	:________	:________
	:________	:________	:________
	:________	:________	:________

Фиг. 6. Ввод стоимостей или прибылей

На Фиг. 7. показано меню для модификации транспортной задачи. После выбора соответствующего пункта этого меню программа выдает запросы, смысл которых не требует дополнительных пояснений. Эти запросы показаны на Фиг. 8-14.

Option Menu for Modifying gg Режимы меню для модификации <имя задачи>
Option: Режим:
	Modify the capacity of sources/destinations Изменить потребности или запасы
	Add one source Добавить одного поставщика
	Delete one source Удалить одного поставщика
	Add one destination Добавить одного потребителя
	Delete one destination Удалить одного потребителя
	Modify the cost/profit coefficients Изменить коэффициенты стоимости/прибыли
	Display and/or print input data Просмотр и/или печать исходных данных
	Return to the function menu Возврат в функциональное меню

Передвигая курсор вверх или вниз выберите режим и нажмите ENTER

Фиг. 7. Ввод стоимостей или прибылей

What is the new problem (model) name? Какое новое имя задачи (модели)?

Фиг. 8. Запрос нового имени задачи

Modify the Capacity of Sources/Destinations Модификация запасов и потребностей
Sources: Поставщики:
0	0	0	0	0
Destinations: Потребители:
0	0	0	0	0

Фиг. 9. Запрос новых запасов и потребностей

Add One Source Добавить одного поставщика

What is the source name (default is , type * to return)? Какое имя поставщика (стандартное , введите * для возврата)? How much is the capacity of Каков запас поставщика <имя поставщика>? What is the cost/profit coefficient from Каков коэффициент стоимости/прибыли из <имя поставщика> в <имя потребителя>? to .................................

Фиг. 10. Запрос для нового поставщика

Delete One Source Удалить одного поставщика

Which source(type number, type 0* to return)? Какой поставщик (введите номер или 0 для возврата)? Are you sure to delete source Вы уверены, что хотите удалить поставщика <имя поставщика> ?

Фиг. 11. Запрос для удаления поставщика

Add One Destination Добавить одного потребителя

What is the destination name (default is , type * to return)? Какое имя потребителя (стандартное , введите * для возврата)? How much is the demand of Какова потребность <имя поставщика>? What is the cost/profit coefficient from Каков коэффициент стоимости/прибыли из <имя поставщика> в <имя потребителя>? to .................................

Фиг. 12. Запрос для добавления поставщика

Delete One Destination Удалить одного потребителя

Which destination(type number, type 0* to return)? Какой потребитель (введите номер или 0 для возврата)? Are you sure to delete destination Вы уверены, что хотите удалить потребителя <имя потребителя> ?

Фиг. 13. Запрос для удаления потребителя

Modify the Cost/Profit Coefficients Модифицировать коэффициенты стоимости/прибыли

Which source(type number, type 0* to return)? Какой поставщик (введите номер или 0 для возврата)? Which destination(type number, type 0* to return)? Какой потребитель (введите номер или 0 для возврата)? Original coefficient on Существующий коэффициент для What is the new coefficient? Какой новый коэффициент? Which source(type number, type 0* to return)? Какой поставщик (введите номер или 0 для возврата)?................................................

Фиг. 14. Запрос для изменения коэффициентов

На Фиг. 15. показано меню выбора режимов решения транспортной задачи.

Option Menu for Solving hhh Меню режимов решения задачи <имя задачи> When solving a problem, you can display every iteration of the MODI method При решении задачи Вы можете просмотреть каждую итерацию метода МОДИ, if your problem scale is and , where is the number если размерность Вашей задачи соответствует требованию и , где - количество of sources, is the number of destinations. Also you can use the North-West поставщиков, - количество потребителей. Вы можете также использовать метод Северо-западного Corner Method (NWC) or Vogel¢s Approximation Method (VAM) to find the initial solution. угла (СЗУ) или метод аппроксимации Фогеля (ФАМ) для нахождения начального решения.
Option Режим
	Solve and display the initial tableau Решить и показать начальную таблицу
	Solve and display each iteration Решить и показать все итерации
	Solve and display the final tableau Решить и показать конечную таблицу
	Solve without displaying any iteration Решить без показа итераций
	Use VAM for the initial solution Использовать ФАМ для начального решения
	Return to the functional menu Вернуться в функциональное меню

Передвигая курсор вверх или вниз, выберите режим и нажмите клавишу ENTER

Фиг. 15. Меню режимов решения задачи.

Initial solution by NMC

Начальное решение методом Северо-западного угла

По\Пт				Dummy Фиктивный потребитель	Supplies Запасы	Потенциалы По
			5.00		3.00		1.00
	7.000	3.000			10.00
			2.00		6.00		3.00
		5.000			5.000
			1.00		4.00		8.00
			5.000	3.000	8.000
Demands Потребности	7.000	8.000	5.000	3.000
Потенциалы Пт

Minimum Value of OBJ =114

Минимальная величина целевой функции =114

Press any key to continue Or «G»--No stop.

Нажмите любую клавишу для продолжения или «G» для выхода на результат.

Фиг. 16. Начальное опорное решение по методу Северо-западного угла.

На Фиг. 16. показано начальное опорное решение по методу СЗУ, а на Фиг. 17. - по методу Фогеля. Фиктивные потребители и (поставщики) имеют имя «Dummy».

Initial solution by NMC

Начальное решение методом Северо-западного угла

По\Пт				Dummy Фиктивный потребитель	Supplies Запасы	Потенциалы По
		5.00		3.00		1.00
		2.000	5.000	3.000	10.00	2.00
		2.00		6.00		3.00
	5.000				5.000	5.00
		1.00		4.00		8.00
	2.000	6.000			8.000	6.00
Demands Потребности	7.000	8.000	5.000	3.000
Потенциалы Пт	2.00	8.00	5.00	3.00

Minimum Value of OBJ =47

Минимальная величина целевой функции =47

Press any key to continue Or «G»--No stop.

Нажмите любую клавишу для продолжения или «G» для выхода на результат.

Фиг. 17. Начальное опорное решение по методу Фогеля.

Iteration 1

Итерация 1

По\Пт				Dummy Фиктивный потребитель	Supplies Запасы	Потенциалы По
		5.00		3.00		1.00
	7.000	3.000			10.00
		2.00		6.00		3.00
		5.000			5.000	3.00
		1.00		4.00		8.00
	**		5.000	3.000	8.000	8.00
Demands Потребности	7.000	8.000	5.000	3.000
Потенциалы Пт	5.00	3.00		-8.00

Current Minimum Value of OBJ =114 with e(3, 1)= -12

Текущий минимум целевой функции =114 с оценкой Х(3, 1)= -12

Press any key to continue Or «G»--No stop.

Нажмите любую клавишу для продолжения или «G» для выхода на результат.

Фиг. 18. Текущее решение транспортной задачи.

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

Final tableau (Total iteration =4).

Конечная таблица (Общее число итераций =4).

По\Пт				Dummy Фиктивный потребитель	Supplies Запасы	Потенциалы По
		5.00		3.00		1.00
		7.000	3.000		10.00
		2.00		6.00		3.00
			2.000	3.000	5.000	2.00
		1.00		4.00		8.00
	7.000	1.000			8.000	1.00
Demands Потребности	7.000	8.000	5.000	3.000
Потенциалы Пт		3.00	1.00	-2.00

Minimum Value of OBJ =41 with multiple optimal.

Минимальная величина целевой функции =41 с множеством решений.

The optimal solution has been found. Press any key to continue.

Начальное решение получено. Нажмите любую клавишу для продолжения.

Фиг. 19. Конечное решение транспортной задачи.

На Фиг. 19. показано конечное (оптимальное) решение транспортной задачи. Множественность оптимальных решений обусловлена наличием нулевых относительных оценок некоторых небазисных переменных - при их изменении целевая функция не будет менять своей величины. На Фиг. 20. показано меню просмотра или печати полученного решения.

Option Menu for Displaying and/or Printing the Final Solution to hhh Меню режимов для просмотра и/или печати окончательного решения для <имя> You have the following options available for displaying Вы имеете следующие режимы, которые можно использовать для просмотра или печати окончательного решения or printing the final solution. If you want to print the Если Вы хотите напечатать решение, solution, make sure that the printer is ready. Убедитесь, что пример находится в состоянии готовности.
Option Режим
	Display the final solution only Только просмотр окончательного решения
	Display and print the final solution Просмотр и печать окончательного решения
	Return to the function menu Возврат в функциональное меню

Передвигая курсор вверх или вниз, выберите режим и нажмите клавишу ENTER

Фиг. 20. Меню просмотра или печати результатов.

На Фиг. 21. показана таблица окончательных результатов решения задачи.

Summary Of Results for hhh Окончательные результаты для <имя задачи>	Page: 1 Страница: 1
From	To	Shipment	Unit cost	From	To	Shipment	Unit cost
		0.0	5.000			2.0	3.000
		7.0	3.000		Dum-my	3.0
		3.0	1.000			7.0	1.000
	Dum-my	0.0				1.0	4.000
		0.0	2.000			0.0	8.000
		0.0	6.000		Dum-my	0.0
Minimum value of OBJ =41 (multiple sols.) Iterations = 4 Минимальная величина целевой функции = 41 (множеств. решен.) Кол-во итераций = 4.

Press any key to continue.

Нажмите любую клавишу для продолжения.

Фиг. 21. Окончательные результаты решения задачи.

[1] Количество линейно независимых строк или столбцов матрицы. Напомним, что существует и другое определение ранга матрицы (тоже и линейного оператора) - это порядок ее базисного минора.

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

[3] Ломаная линия с вершинами в отмеченных (базисных) клетках плана перевозок.

[4] Нумерация элементов цепочки начинается с элемента, соответствующего максимальному по абсолютной величине отрицательному элементу оценочной матрицы.

---

Дата добавления: 2015-10-29