Размещено на http://www.allbest.ru/

МОСКОВСКИЙ ТЕХНИКУМ КОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Российский государственный торгово-экономический университет»

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

МТКПр РГТЭУ.330514.00181

МП 42-09

Листов 59

Консультант

Разработал

Н. А. Жилкина

С. А. Соколов

2012

Содержание

1 Введение

2 Постановка задачи

3 Численный метод

4 Схемы алгоритма программы

4.1 Схема алгоритма основной программы

4.2 Схема алгоритма метода newPlan

4.3 Схема алгоритма метода sumTransport

4.4 Схема алгоритма метода CiclePr

4.5 Схемы алгоритма метода searchCycle

4.6 Схемы алгоритма метода firstPlan

5 Ручной просчет

6 Инструкция по эксплуатации программы

7 Заключение

Литература

Приложение А. Листинг программы

Приложение Б. Результаты выполнения программы

1. Введение

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

Транспортная задача (задача Монжа -- Канторовича) -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа -- Канторовича.

2. Постановка задачи

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

Стоимости из iго пункта отправления в jй пункт назначения представлены в виде матрицы в таблице 2.1.

Таблица 2.1 - Матрица стоимостей

2	4	7	10	8
8	3	10	1	2
5	4	6	7	9
1	10	7	5	3
4	8	9	2	1

Общие данные представлены в виде таблицы 2.2.

Таблица 2.2 - Общие данные

	B1	B2	B3	B4	B5	ai
A1		2		4		7		10		8	37
A2		8		3		10		1		2	12
A3		5		4		6		7		9	33
A4		1		10		7		5		3	26
A5		4		8		9		2		1	42
bi	40	18	37	23	32

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

Программа должна быть написана на алгоритмическом языке ActionScript 3.0 и отлажена на IBM совместимом компьютере.

3. Численный метод

Метод наименьших стоимостей.

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

Пункт 1. Сначала во всей транспортной таблице выбирается клетка с наименьшей стоимостью. Переменной в этой клетке присваивается максимально допустимое значение, допускаемое ограничениями на заявки и запасы, т.е. .

Пункт 2. Если полностью реализован запас, т.е. , то вычеркивается i-тая строка. Если же полностью выполнена заявка, т.е. , то вычеркивается j-тый столбец. Если одновременно удовлетворяет заявка и исчерпывается запас, то обычно вычеркивается j-тый столбец. Затем корректируются значения запасов или заявок, уменьшая их величину на .

Пункт 3. Процесс заканчивается, если осталась одна невычеркнутая строка или один столбец. В противном случае, возвращаемся к пункту 1.

Пример:

Имеется m пунктов отправления , в которых сосредоточен однотипный груз в количестве . Имеется и n пунктов назначения . Каждый пункт подает заявку на груз в количестве . Сумма всех заказов равна сумме всех заявок.

Стоимость перевозки одного груза из i-го пункта отправления в j-ый пункт назначения задается . Требуется составить такой план перевозок, чтобы все запасы были исчерпаны и все заявки были удовлетворены, а общая стоимость всех перевозок должна быть минимальной.

Обозначим через количество единицы груза, отправляемого из i-го пункта отправления в j-ый пункт назначения.

Получим матрицу перевозок

Рисунок 3.1 - Матрица перевозок

А вершины называют перевозками.

>0

Перевозки удовлетворяют двум условиям:

1. Суммарное количество груза, вывозимого из каждого пункта отправления во все пункты назначения, равно запасу груза в каждом пункте отправления.

Рисунок 3.2 - Суммарное количество груза из каждого пункта отправления во все пункты назначения

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

Рисунок 3.3 -Суммарное количество груза, привозимого в каждый пункт назначения из всех пунктов отправления

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

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

Все уравнения этой системы можно решить количеством базисных переменных, выразив их через свободные. Количество свободных переменных равно (m-1)*(n-1).

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

Допустимый план называется оптимальным, если среди всех планов он приводит к минимальной стоимости.

При решении транспортной задачи повторяются решение симплексного метода. Но способ проверки видоизменен.

Основные шаги алгоритма решения транспортной задачи:

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

4. Схемы алгоритма программы

4.1 Схема алгоритма основной программы

4.2 Схема алгоритма метода newPlan

4.3 Схема алгоритма метода sumTransport

4.4 Схема алгоритма метода CiclePr

4.5 Схемы алгоритма метода searchCycle



4.6 Схемы алгоритма метода firstPlan

5. Ручной просчет

Даны сходные данные:

Таблица 5.1 - Опорный план

	B1	B2	B3	B4	B5	ai
A1		2		4		7		10		8	37
A2		8		3		10		1		2	12
A3		5		4		6		7		9	33
A4		1		10		7		5		3	26
A5		4		8		9		2		1	42
bi	40	18	37	23	32
	B1	B2	B3	B4	B5	ai
A1		2		4		7		10		8	37
A2		8		3		10	12	1		2	0
A3		5		4		6		7		9	33
A4	26	1		10		7		5		3	26
A5		4		8		9		2		1	42
bi	40	18	37	11	32
	B1	B2	B3	B4	B5	ai
A1		2		4		7		10		8	37
A2		8		3		10	12	1		2	0
A3		5		4		6		7		9	33
A4	26	1		10		7		5		3	0
A5		4		8		9		2	32	1	10
bi	14	18	37	11	0
	B1	B2	B3	B4	B5	ai
A1	14	2		4		7		10		8	23
A2		8		3		10	12	1		2	0
A3		5		4		6		7		9	33
A4	26	1		10		7		5		3	0
A5		4		8		9	10	2	32	1	0
bi	0	18	37	1	0
	B1	B2	B3	B4	B5	ai
A1	14	2	18	4		7		10		8	5
A2		8		3		10	12	1		2	0
A3		5		4		6		7		9	33
A4	26	1		10		7		5		3	0
A5		4		8		9	10	2	32	1	0
bi	0	0	37	1	0
	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7		10		8	5
A2		8		3		10	12	1		2	0
A3		5		4	33	6		7		9	0
A4	26	1		10		7		5		3	0
A5		4		8		9	10	2	32	1	0
bi	0	0	4	1	0
	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7	1	10		8	1
A2		8		3		10	12	1		2	0
A3		5		4	33	6		7		9	0
A4	26	1		10		7		5		3	0
A5		4		8		9	10	2	32	1	0
bi	0	0	0	1	0
	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7	1	10		8	0
A2		8		3		10	12	1		2	0
A3		5		4	33	6		7		9	0
A4	26	1		10		7		5		3	0
A5		4		8		9	10	2	32	1	0
bi	0	0	0	0	0
	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7	1	10		8	37
A2		8		3		10	12	1		2	12
A3		5		4	33	6		7		9	33
A4	26	1		10		7		5		3	12
A5		4		8		9	10	2	32	1	42
bi	40	18	37	23	32

Стоимость плана

14*2+18*4+4*7+1*10+12*1+33*6+26*1+10*2+32*1=426

Для каждой свободной клетки построим цикл и определим его стоимость

Y21 = 15 >0 Y53 = 10 >0

Y31 = 4 >0 Y34 = -2 <0

Y51 = 10 >0 Y44 = -4 <0

Y22 = 8 >0 Y15 = -1 <0

Y52 = 12 >0 Y25 = 2 >0

Y23 = 12 >0 Y43 = 1 >0

Y32 = 1 >0 Y45 = -1 <0

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7	1	10	+	8	37
A2		8		3		10	12	1		2	12
A3		5		4	33	6		7		9	33
A4	26	1		10		7		5		3	12
A5		4		8		9	10	2	32	1	42
bi	40	18	37	23	32
Стоимость плана = 426-1=425

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	4	7		10	1	8	37
A2		8		3		10	12	1		2	12
A3		5		4	33	6	+	7		9	33
A4	26	1		10		7		5		3	12
A5		4		8		9	11	2	31	1	42
bi	40	18	37	23	32
Стоимость плана = 425- 1=424

Построим цикл для {1;5}

	B1	B2	B3	B4	B5	ai
A1	14	2	18	4	5	7		10		8	37
A2		8		3		10	12	1		2	12
A3		5		4	32	6	1	7		9	33
A4	26	1		10		7	+	5		3	12
A5		4		8		9	10	2	32	1	42
bi	40	18	37	23	32
Стоимость плана = 424-1=423

Построим цикл для {4;5}

	B1	B2	B3	B4	B5	ai
A1	15	2	18	4	4	7		10		8	37
A2		8		3		10	12	1		2	12
A3		5		4	33	6		7		9	33
A4	25	1		10		7	1	5	+	3	12
A5		4		8		9	10	2	32	1	42
bi	40	18	37	23	32
Стоимость плана = 424-1=422

	B1	B2	B3	B4	B5	ai
A1	15	2	18	4	4	7		10		8	37
A2		8		3		10	12	1		2	12
A3		5		4	33	6		7		9	33
A4	25	1		10		7		5	1	3	12
A5		4		8		9	11	2	31	1	42
bi	40	18	37	23	32

T.к. для всех клеток цены циклов положительны, то дальнейшее улучшение плана невозможно, что означает, что мы нашли оптимальный план.

План оптимален.

Таблица 5.7 - Оптимальный план

	B1	B2	B3	B4	B5	ai
A1		4		8		9	19	2	23	1	42
A2		8		3		10	12	1		2	12
A3		5	9	4	18	6	6	7		9	33
A4	26	1		10		7		5		3	26
A5	6	2	31	4		7		10		8	37
bi	32	40	18	37	23

Листинг программы приведен в приложении А, а результаты её выполнения - в приложении Б.

6. Инструкция по эксплуатации программы

Минимальные системные требования:

ОС: Windows 8/7/Vista/XP/2000/ME/98/95

8мб HDD памяти. Клавиатура.

Для начала работы с программой необходимо запустить файл transport.exe.

Программу можно использовать в полноэкранном режиме, для этого необходимо зайти в меню «Просмотр» и выбрать пункт «Полный экран» или нажать комбинацию клавиш Ctrl+F, режим окна можно вернуть с помощью клавиши Esc.(Рисунок 6.1)

Рисунок 6.1 - Контекстное меню «Просмотр»

В главном меню программы необходимо выбрать пункт «Составить план». (Рисунок 6.2)

Рисунок 6.2 - Меню программы

Далее необходимо указать количество заявок и количество запасов. (Внимание! Максимальное количество запасов и заявок - 6) (Рисунок 6.3)

Рисунок 6.3 - Подготовка построения плана

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

Рисунок 6.4 - Таблица решения

Справа от таблицы расположено меню работы. С его помощью можно вернуться в меню, просмотреть подсказку о цветовой схеме таблицы и продолжить работу программы нажав кнопку «Далее». (Рисунок 6.5)

Рисунок 6.5 - Вызов подсказки

Продолжив работу, программа построит первый план. Также в верхнем правом углу покажется стоимость первого плана, а в правом нижнем углу количество единиц груза. (Рисунок 6.6)

Рисунок 6.6 - Первый план решения

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

Рисунок 6.7 - Выбранный цикл решения транспортной задачи

Если план является оптимальным, программа выдаст соответствующее сообщение и распечатает конечную стоимость плана и итоговую таблицу решения. (Рисунок 6.8)

Рисунок 6.8 - Завершение работы программы

Заключение

С помощью данной программы вы сможете без труда производить вычисления по транспортной задаче. Интерфейс программы удобен и приятен.

Литература

1 К.Л. Самаров Транспортная задача. Учебное пособие для студента.

2 Колин Мук ActionScript 3.0 для Flash. Подробное руководство.

Приложение А

Листинг программы

/*

_____________________________________________________________

Курсовой проект

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

_____________________________________________________________

Язык: ActionScript 3.0

Кодировка: ASCII (win.1251)

Среда: Adobe Flash CS6.0

Разработали:

А. В. Андронов

С. А. Соколов

А.Ю. Бадаев

А.В. Никитин

Е.А. Туровский

Дата: 1 ноября 2012г

_____________________________________________________________

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

_____________________________________________________________

Используемые глобальные константы:

STAGE_HEIGHT - высота сцены;

STAGE_WIDTH - ширина сцены.

_____________________________________________________________Используемые глобальные переменные класса:

task - класс управления задачей;

mm - главное меню;

a - информация о программе.

_____________________________________________________________

Используемые методы класса:

init - инициализация программы;

nTask - создание нового плана;

clearMenu - удаление главного меню;

clearTask - удаление плана;

showMenu - создание главного меню;

about - информация о программе.

_____________________________________________________________

*/

package src

{

import flash.display.MovieClip;

import flash.events.Event;

import src.transport.*;

import flash.events.MouseEvent;

public class Main extends MovieClip

{

public static var STAGE_HEIGHT:int=580,STAGE_WIDTH:int=789;

private var task:Task;

private var mm:MainMenu;

private var a:About;

/*

_____________________________________________________________

Метод enterSize - ввод количества заявок и запасов.

_____________________________________________________________

*/ public function Main()

{

addEventListener(Event.ADDED_TO_STAGE, init);

}

/*

_____________________________________________________________

Метод init - инициализация программы.

_____________________________________________________________

Формальный параметр:

e - событие.

_____________________________________________________________

*/ private function init(e:Event):void

{

removeEventListener(Event.ADDED_TO_STAGE, init);

STAGE_HEIGHT = stage.height;

STAGE_WIDTH = stage.width;

showMenu(new TEvent(TEvent.FIRST_TRANSPORT));

}

/*

_____________________________________________________________

Метод nTask - создание нового плана.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function nTask(e:MouseEvent):void

{

if (a)

{

removeChild(a);

a = null;

}

if (task)

{

clearTask();

}

else

{

task=new Task();

task.enterSize();

addChild(task);

task.addEventListener(TEvent.END_TRANSPORT,showMenu);

task.addEventListener(TEvent.NEW_TRANSPORT,clearMenu);

}

}//end

/*

_____________________________________________________________

Метод clearMenu - удаление главного меню.

_____________________________________________________________

Формальный параметр:

e - событие.

_____________________________________________________________

*/ private function clearMenu(e:TEvent):void

{

mm.new_task.removeEventListener(MouseEvent.CLICK,nTask);

mm.about.removeEventListener(MouseEvent.CLICK,about);

removeChild(mm);

mm = null;

}

/*

_____________________________________________________________

Метод clearTask - удаление плана.

_____________________________________________________________

*/ private function clearTask():void

{

task.removeEventListener(TEvent.END_TRANSPORT,showMenu);

task.removeEventListener(TEvent.NEW_TRANSPORT,clearMenu);

removeChild(task);

task = null;

}//end

/*

_____________________________________________________________

Метод showMenu - создание главного меню.

_____________________________________________________________

Формальный параметр:

e - событие.

_____________________________________________________________

*/ private function showMenu(e:TEvent):void

{

if (e.type == TEvent.END_TRANSPORT)

{

clearTask();

}

mm=new MainMenu();

mm.x = STAGE_WIDTH - mm.width;

mm.y = STAGE_HEIGHT/2-mm.height/2;

addChild(mm);

mm.new_task.addEventListener(MouseEvent.CLICK,nTask);

mm.about.addEventListener(MouseEvent.CLICK,about);

}//end

/*

_____________________________________________________________

Метод about - информация о программе.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function about(e:MouseEvent):void

{

if (a)

{

removeChild(a);

a = null;

}

else

{

a=new About();

a.x = STAGE_WIDTH / 2 - a.width / 2;

a.y = STAGE_HEIGHT / 2 - a.height / 2;

addChild(a);

}

}//end

}//end class

}//end package

/*

_____________________________________________________________

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

_____________________________________________________________

Используемые глобальные переменные класса:

m - класс матрицы перевозок;

store, stock - вектора заявок и запасов соответственно;

dataConStore,

dataConStock - контейнеры объектов запасов и заявок;

kolZayavok,

kolZapasov - количество заявок и запасов;

control - класс элементов управления;

hint - класс подсказки;

sizeForm - класс формы ввода подсказки.

_____________________________________________________________

Используемые методы класса:

H - вывод информации;

enterSize - ввод размера матрицы перевозок;

checkedSize - проверка ввода размера матрицы перевозок;

enterData - создание и вывод на экран матрицы, кнопок;

showHint - вывод подсказки;

goMenu - выход в главное меню программы;

firstPlan - постраение первого плана;

nextPlan - постраение следующего плана;

sumElementsVector - суммирует элементы вектора запасов или заявок;

showSS - создание и вывод на экран векторов запасов и заявок;

addZaya - добавление в вектор заявок элемента;

addZap - добавление в вектор запасов элемента;

closeEnter - ограничение доступа ввода запасов и заявок;

correctness - проверка корректности ввода значений запасов и заявок.

_____________________________________________________________

*/

package src

{

import flash.display.MovieClip;

import src.transport.data.*;

import src.transport.*;

import flash.events.MouseEvent;

import flash.display.Sprite;

public class Task extends MovieClip

{

private var m:Mat;

private var store:Array,stock:Array;

private var dataConStore:Sprite,dataConStock:Sprite;

private var kolZayavok:int,kolZapasov:int;

private var control:BandControl;

private var hint:Hint;

private var sizeForm:FormSize;

/*

_____________________________________________________________

Конструктор класса.

_____________________________________________________________

*/ public function Task()

{

hint= new Hint();

hint.x = Main.STAGE_WIDTH / 2 - hint.width / 2;

hint.y = Main.STAGE_HEIGHT / 2 - hint.height / 2;

}//end

/*

_____________________________________________________________

Метод H - выводит информацию на экран.

_____________________________________________________________

Формальный параметр:

s - строка информации.

_____________________________________________________________

*/ private function H(s:String):void

{

hint.hint = s;

addChild(hint);

}//end

/*

_____________________________________________________________

Метод enterSize - ввод количества заявок и запасов.

_____________________________________________________________

*/ public function enterSize():void

{

sizeForm=new FormSize();

sizeForm.y = Main.STAGE_HEIGHT / 2 - sizeForm.height / 2;

addChild(sizeForm);

sizeForm.ok.addEventListener(MouseEvent.CLICK,checkedSize);

}//end

/*

_____________________________________________________________

Метод checkedSize - проверка правильности заполнения полей

размеров.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function checkedSize(e:MouseEvent):void

{

if (sizeForm.check)

{

sizeForm.ok.removeEventListener(MouseEvent.CLICK,enterData);

removeChild(sizeForm);

kolZayavok = int(sizeForm.kolzaya.text);

kolZapasov = int(sizeForm.kolzap.text);

sizeForm = null;

enterData();

}

else

{

H('\n\nНе правильный ввод!\n Все поля должны быть заполнены!');

}

}//end

/*

_____________________________________________________________

Метод enterData - создание и вывод на экран матрицы, кнопок.

_____________________________________________________________

*/ private function enterData():void

{

control= new BandControl();

control.y = 0;

addChild(control);

control.btnNext.addEventListener(MouseEvent.CLICK,firstPlan);

control.menu.addEventListener(MouseEvent.CLICK,goMenu);

control.hint_btn.addEventListener(MouseEvent.CLICK,showHint);

m=new Mat();

m.y = 40;

m.x = 40;

m.showMat(kolZayavok,kolZapasov);

addChild(m);

showSS();

H('Заполните поля цены, поля заявок и поля запасов.\nИ нажмите кнопку "Далее" для продолжения...');

}//end

/*

_____________________________________________________________

Метод showHint - вывод подсказки.

_____________________________________________________________

*/ private function showHint(e:MouseEvent):void

{

hint.gotoAndStop(2);

hint.visible = true;

addChild(hint);

}//end

/*

_____________________________________________________________

Метод goMenu - выход в главное меню программы.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function goMenu(e:MouseEvent):void

{

control.btnNext.removeEventListener(MouseEvent.CLICK,firstPlan);

control.menu.removeEventListener(MouseEvent.CLICK,goMenu);

control.hint_btn.removeEventListener(MouseEvent.CLICK,showHint);

dispatchEvent(new TEvent(TEvent.END_TRANSPORT));

}//end

/*

_____________________________________________________________

Метод firstPlan - постраение первого плана.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

Переменные используемые в методе:

sZaya, sZap - сумма элементов вектора заявок, сумма элементов

вектора запасов.

_____________________________________________________________

*/ private function firstPlan(e:MouseEvent):void

{

var sZaya:int = sumElementsVector(store,kolZayavok);

var sZap:int = sumElementsVector(stock,kolZapasov);

if (stock.every(correctness) && store.every(correctness))

{

if (sZaya<sZap)

{

addZaya(sZap-sZaya);

}

else if (sZaya>sZap)

{

addZap(sZaya-sZap);

}else

{

control.btnNext.removeEventListener(MouseEvent.CLICK,firstPlan);

control.stoimost_plana_txt.text = m.firstPlan(stock,store,kolZayavok,kolZapasov).toString();

control.btnNext.addEventListener(MouseEvent.CLICK,nextPlan);

control.cargo_units_txt.text = sZaya.toString();

H('Первый план поcтроен.\n Нажмите "Далее" для продолжения...');

store.forEach(closeEnter);

stock.forEach(closeEnter);

}

}

else

{

H('Значения полей запасов и заявок \nне должны быть равными нулю или оставаться пустыми\nпроверте правильность');

}

}//end

/*

_____________________________________________________________

Метод nextPlan - постраение следующего плана.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function nextPlan(e:MouseEvent):void

{

hint.visible = false;

if (m.newPlan(kolZayavok,kolZapasov))

{

H('\n\nПлан оптимален, задача решена.\nСтоимость плана:'+control.stoimost_plana_txt.text);

control.btnNext.removeEventListener(MouseEvent.CLICK,nextPlan);

}

else

{

control.stoimost_plana_txt.text = m.sumTransport(kolZayavok,kolZapasov).toString();

}

}//end

/*

_____________________________________________________________

Метод sumElementsVector - суммирует элементы вектора запасов или заявок.

_____________________________________________________________

Формальные параметры:

v - вектор;

m - количество элементов.

_____________________________________________________________

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

sum - сумма элементов.

_____________________________________________________________

*/ public function sumElementsVector(v:Array,m:int):int

{

var sum:int = 0;

for (var i:int=0; i<m; i++)

{

sum += int(v[i].stock);

}

return sum;

}//end

/*

_____________________________________________________________

Метод showSS - создание и вывод на экран векторов запасов и заявок

_____________________________________________________________

Переменные используемые в методе:

i - счетчик цикла;

yy,xx - координаты расположения объектов.

_____________________________________________________________

*/ private function showSS():void

{

var yy:int = 0;

var i:int;

store = new Array();

dataConStore= new Sprite();

dataConStore.x = m.x + m.width + 10,dataConStore.y = m.y;

for (i=0; i<kolZayavok; i++)

{

store.push(new SStore());

store[i].y = yy;

dataConStore.addChild(store[i]);

yy += store[i].height + 5;

}

addChild(dataConStore);

stock= new Array();

dataConStock= new Sprite();

dataConStock.x = m.x;

dataConStock.y = m.y + m.height + 10;

var xx:int = 0;

for (i=0; i<kolZapasov; i++)

{

stock.push(new SStore());

stock[i].x = xx;

dataConStock.addChild(stock[i]);

xx += stock[i].width + 5;

}

addChild(dataConStock);

}//end

/*

_____________________________________________________________

Метод addZaya - добавление в вектор заявок элемента.

_____________________________________________________________

Формальный параметр:

arg - значение добавляемого элемента.

_____________________________________________________________

*/ private function addZaya(arg:int):void

{

kolZayavok = m.addStr(kolZapasov);

store.push(new SStore());

store[kolZayavok - 1].y = dataConStore.height + 5;

dataConStore.addChild(store[kolZayavok-1]);

store[kolZayavok - 1].stock = arg.toString();

dataConStock.y = m.y + m.height + 10;

}//end

/*

_____________________________________________________________

Метод addZap - добавление в вектор запасов элемента.

_____________________________________________________________

Формальный параметр:

arg - значение добавляемого элемента.

_____________________________________________________________

*/ private function addZap(arg:int):void

{

kolZapasov = m.addSto(kolZapasov);

stock.push(new SStore());

stock[kolZapasov - 1].x = dataConStock.width + 5;

dataConStock.addChild(stock[kolZapasov -1]);

stock[kolZapasov - 1].stock = arg.toString();

dataConStore.x = m.x + m.width + 10;

}//end

/*

_____________________________________________________________

Метод closeEnter - ограничение доступа ввода запасов и заявок.

_____________________________________________________________

Формальные параметры:

element - элемент для ограничения доступа;

index - индекс элемента в массиве;

arr - массив элементов.

_____________________________________________________________

*/ private function closeEnter(element:*, index:Number, arr:Array):void

{

element.closeStock();

}//end

/*

_____________________________________________________________

Метод correctness - проверка корректности ввода значений запасов и заявок.

_____________________________________________________________

Формальные параметры:

element - элемент для ограничения доступа;

index - индекс элемента в массиве;

arr - массив элементов.

_____________________________________________________________

*/ private function correctness(element:*, index:Number, arr:Array):Boolean

{

return element.stock>0;

}//end

}//end class

}//end package

/*

_____________________________________________________________

Класс работы с матрицой перевозок.

_____________________________________________________________

Используемые глобальные переменные класса:

element - матрица перевозок;

cicle - вектор цикла.

_____________________________________________________________

Используемые методы класса:

showMat - создание и вывод на экран матрицы перевозок;

sumTransport - подсчет стоимости плана;

firstPlan - построение первого плана;

getValue - вспомогательный метод копирования значений запасов и

заявок;

addStr - добавление строки в матрицу;

addSto - добавление столбца в матрицу;

newPlan - построение нового плана;

ciclePr - улучшение плана перевозок;

clearCicleShow - визуальная очистка плана;

endCycle - проверка завершения цикла;

searchCycle - поиск цикла;

newObjectWay - добавление в вектор элемента цикла;

priceCicle - определение цены цикла.

_____________________________________________________________

*/

package src.transport

{

import flash.display.MovieClip;

import src.transport.data.*;

public class Mat extends MovieClip

{

private var element:Array;

private var cicle:Array;

/*

_____________________________________________________________

Конструктор класса.

_____________________________________________________________

*/ public function Mat()

{

}

/*

_____________________________________________________________

Метод showMat - создание и вывод на экран матрицы перевозок.

_____________________________________________________________

Формальные параметры:

n - количество строк;

m - количество столбцов.

_____________________________________________________________

Переменные используемые в методе:

yy,xx - координаты расположения элементов.

_____________________________________________________________

*/ public function showMat(n:int,m:int):void

{

var xx:int = 0,yy:int = 0;

element = new Array(n);

for (var i:int=0; i<n; i++)

{

element[i] = new Array(m);

for (var j:int=0; j<m; j++)

{

element[i][j]= new Element();

element[i][j].x = xx;

element[i][j].y = yy;

addChild(element[i][j]);

xx += element[i][j].width + 5;

}

xx = 0;

yy += element[i][j - 1].height + 5;

}

}//end

/*

_____________________________________________________________

Метод sumTransport - подсчет стоимости плана.

_____________________________________________________________

Формальные параметры:

n - количество строк;

m - количество столбцов.

_____________________________________________________________

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

sum - сумма элементов.

_____________________________________________________________

*/ public function sumTransport(n:int,m:int):int

{

var sum:int = 0;

for (var i:int=0; i<n; i++)

{

for (var j:int=0; j<m; j++)

{

sum += element[i][j].stoimost * element[i][j].perevozka;

}

}

return sum;

}//end

/*

_____________________________________________________________

Метод firstPlan - построение первого плана.

_____________________________________________________________

Формальные параметры:

n - количество строк;

m - количество столбцов;

_a - вектор запасов;

_b - вектор заявок;

_____________________________________________________________

Переменные используемые в методе:

i, j, k - счетчики.

a - вектор запасов;

b - вектор заявок;

min - минимальная стоимость;

I, J - индексы элемента;

sum - стоимость первого плана;

p - количество груза.

_____________________________________________________________

*/ public function firstPlan(_a:Array,_b:Array,n:int,m:int):int

{

var i:int,j:int;

var a:Array = _a.map(getValue);

var b:Array = _b.map(getValue);

var min:int,k:int,J:int,I:int,sum:int = 0,p:int = 0;

for (k=0; k<(n+m-1); k++)

{

min = 1000;

for (i=0; i<n; i++)

{

if (b[i] > 0)

{

for (j=0; j<m; j++)

{

if (min>element[i][j].stoimost&&(a[j]>0))

{

min = element[i][j].stoimost;

I = i;

J = j;

}

}

}

}

if (! element[I][J].bazis)

{

p=(a[J]<b[I])?a[J]:b[I];

a[J] -= p;

b[I] -= p;

element[I][J].perevozka = p;

element[I][J].bazis = true;

sum += min * p;

}

else

{

i = 0;

while (i<n)

{

for (j=0; j<m; j++)

{

if (! element[i][j].bazis)

{

element[i][j].bazis = true;

i = n;

break;

}

}

i++;

}

}

}

return sum;

}//end

/*

_____________________________________________________________

Метод getValue - вспомогательный метод копирования значений

запасов и заявок.

_____________________________________________________________

Формальные параметры:

element - элемент для ограничения доступа;

index - индекс элемента в массиве;

arr - массив элементов.

_____________________________________________________________

*/ private function getValue(element:*, index:int, arr:Array):int

{

return element.stock;

}//end

/*

_____________________________________________________________

Метод addStr - добавление строки в матрицу.

_____________________________________________________________

Формальный параметр:

zap - длина вектора запасов.

_____________________________________________________________

*/ public function addStr(zap:int):int

{

var i:int = element.length,xx:int = 0;

var yy:int = element[i - 1][0].y + element[i - 1][0].width - 5;

element[i]=new Array();

for (var j:int=0; j<zap; j++)

{

element[i][j]=new Element();

element[i][j].y = yy;

element[i][j].x = xx;

addChild(element[i][j]);

xx += element[i][j].width + 5;

}

return element.length;

}//end

/*

_____________________________________________________________

Метод addSto - добавление столбца в матрицу.

_____________________________________________________________

Формальный параметр:

zap - длина вектора заявок.

_____________________________________________________________

*/ public function addSto(zap:int):int

{

var xx:int = element[0][zap - 1].x + element[0][zap - 1].width + 5;

var yy:int = 0;

for (var j:int=0; j<element.length; j++)

{

element[j][zap]=new Element();

element[j][zap].y = yy;

element[j][zap].x = xx;

addChild(element[j][zap]);

yy += element[j][zap].height + 5;

}

return element[j-1].length;

}//end

/*

_____________________________________________________________

Метод newPlan - построение нового плана.

_____________________________________________________________

Формальные параметры:

n - количество строк;

m - количество столбцов.

_____________________________________________________________

Переменные используемые в методе:

i, j - счетчики.

_____________________________________________________________

*/ public function newPlan(n:int,m:int):Boolean

{

var i:int,j:int;

if (cicle)

{

clearCicleShow();

}

for (i=0; i<n; i++)

{

for (j=0; j<m; j++)

{

if (! element[i][j].bazis)

{

cicle= new Array();

newObjectWay(0,i,j);

if (searchCycle(1,1,i,j,n,m)||searchCycle(1,3,i,j,n,m)

||searchCycle(1,2,i,j,n,m)||searchCycle(1,4,i,j,n,m))

{

if (priceCicle())

{

ciclePr();

return false;

}

}

}

}

}

return true;

}//end

/*

_____________________________________________________________

Метод ciclePr - улучшение плана перевозок.

_____________________________________________________________

Переменные используемые в методе:

i - счетчик;

min - минимальный груз;

ki, kj - индексы;

zn - знак операции.

_____________________________________________________________

*/ private function ciclePr():void

{

var min:int = cicle[1].perev,ki:int = cicle[1].i,kj:int = cicle[1].j,i:int = 1;

while (i<cicle.length)

{

if (min>cicle[i].perev)

{

min = cicle[i].perev;

ki = cicle[i].i;

kj = cicle[i].j;

}

i += 2;

}

var zn:int = 1;

element[cicle[0].i][cicle[0].j].bazis = true;

element[ki][kj].bazis = false;

for (i=0; i<cicle.length; i++)

{

element[cicle[i].i][cicle[i].j].perevozka += min * zn;

element[cicle[i].i][cicle[i].j].gotoAndStop(3);

zn *= -zn;

}

element[cicle[0].i][cicle[0].j].gotoAndStop(4);

element[ki][kj].gotoAndStop(5);

}//end

/*

_____________________________________________________________

Метод clearCicleShow - визуальная очистка плана.

_____________________________________________________________

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

i - счетчик.

_____________________________________________________________

*/ private function clearCicleShow():void

{

for (var i:int=0; i<cicle.length; i++)

{

if (element[cicle[i].i][cicle[i].j].bazis)

{

element[cicle[i].i][cicle[i].j].gotoAndStop(2);

}

else

{

element[cicle[i].i][cicle[i].j].gotoAndStop(1);

}

}

}//end

/*

_____________________________________________________________

Метод endCycle - проверка завершения цикла.

_____________________________________________________________

Формальные параметры:

i, j - индексы.

_____________________________________________________________

*/ private function endCycle(i:int,j:int):Boolean

{

return ((cicle[0].i==i)&&(cicle[0].j==j));

}//end

/*

_____________________________________________________________

Метод searchCycle - поиск цикла.

_____________________________________________________________

Формальные параметры:

_n - количество строк;

_m - количество столбцов;

_i, _j - индексы;

p - направление движения;

k - индекс вектора цикла.

_____________________________________________________________

Переменные используемые в методе:

i, j - счетчики;

f - существование цикла;

b - вспомогательная переменная.

_____________________________________________________________

*/ private function searchCycle(k:int,p:int,_i:int,_j:int,_n:int,_m:int):Boolean

{

var j:int,i:int,b:Boolean = false,f:Boolean = false;

if (k>21)

{

return false;

}

switch (p)

{

case 1 :

for (i = _i; i<_n; i++)

{

if ((k>2)&&endCycle(i,_j))

{

return true;

}

if (element[i][_j].bazis && b)

{

if (f=(searchCycle(k+1,2,i,_j,_n,_m)||searchCycle(k+1,4,i,_j,_n,_m)))

{

newObjectWay(k,i,_j);

}

else

{

f = searchCycle(k,1,i,_j,_n,_m);

}

return f;

}

b = true;

}

break;

case 2 :

for (j = _j; j<_m; j++)

{

if ((k>2)&&endCycle(_i,j))

{

return true;

}

if (element[_i][j].bazis && b)

{

if (f=(searchCycle(k+1,3,_i,j,_n,_m)||searchCycle(k+1,1,_i,j,_n,_m)))

{

newObjectWay(k,_i,j);

}

else

{

f = searchCycle(k,2,_i,j,_n,_m);

}

return f;

}

b = true;

}

break;

case 3 :

for (i = _i; i>=0; i--)

{

if ((k>2)&&endCycle(i,_j))

{

return true;

}

if (element[i][_j].bazis && b)

{

if (f=(searchCycle(k+1,4,i,_j,_n,_m)||searchCycle(k+1,2,i,_j,_n,_m)))

{

newObjectWay(k,i,_j);

}

else

{

f = searchCycle(k,3,i,_j,_n,_m);

}

return f;

}

b = true;

}

break;

case 4 :

for (j = _j; j>=0; j--)

{

if ((k>2)&&endCycle(_i,j))

{

return true;

}

if (element[_i][j].bazis && b)

{

if (f=(searchCycle(k+1,1,_i,j,_n,_m)||searchCycle(k+1,3,_i,j,_n,_m)))

{

newObjectWay(k,_i,j);

}

else

{

f = searchCycle(k,4,_i,j,_n,_m);

}

return f;

}

b = true;

}

break;

}

return false;

}//end

/*

_____________________________________________________________

Метод newObjectWay - добавление в вектор элемента цикла.

_____________________________________________________________

Формальные параметры:

i, j - индексы элемента матрицы;

k - индекс вектора цикла.

_____________________________________________________________

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

obj - элемент вектора цикла.

_____________________________________________________________

*/ private function newObjectWay(k:int,i:int,j:int):void

{

var obj:Object= new Object();

obj.i = i;

obj.j = j;

obj.price = element[i][j].stoimost;

obj.perev = element[i][j].perevozka;

cicle[k] = obj;

}//end

/*

_____________________________________________________________

Метод priceCicle - определение цены цикла.

_____________________________________________________________

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

sum - цена цикла.

_____________________________________________________________

*/ private function priceCicle():Boolean

{

if ((cicle.length%2)!=0)

{

return false;

}

var sum:int = 0,i:int = 0;

while (i<cicle.length)

{

sum += cicle[i].price - cicle[i + 1].price;

i += 2;

}

return sum<0;

}//end

}//end class

}//end package

/*

_____________________________________________________________

Класс формы ввода размера матрицы.

_____________________________________________________________

Используемые глобальные переменные класса:

kolzaya - количество заявок;

kolzap - количество запасов.

_____________________________________________________________

Используемый метод класса:

get check - метод возвращающий корректность ввода.

_____________________________________________________________

*/

package src.transport

{

import flash.display.MovieClip;

public class FormSize extends MovieClip

{

/*

_____________________________________________________________

Конструктор класса.

_____________________________________________________________

*/ public function FormSize()

{

this.kolzaya.restrict = '1-6';

this.kolzaya.maxChars = 1;

this.kolzap.restrict = '1-6';

this.kolzap.maxChars = 1;

}

/*

_____________________________________________________________

Метод get check - метод возвращающий корректность ввода.

_____________________________________________________________

*/ public function get check():Boolean

{

return kolzaya.text&&kolzap.text;

}

}

}

/*

_____________________________________________________________

Класс вывода информации.

_____________________________________________________________

Используемые глобальные переменные класса:

ok - кнопка;

field - текстовое поле.

_____________________________________________________________

Используемые методы класса:

set hint - установка текста информации;

hideHint - скрытие подсказки.

_____________________________________________________________

*/

package src

{

import flash.display.MovieClip;

import flash.events.MouseEvent;

public class Hint extends MovieClip

{

/*

_____________________________________________________________

Конструктор класса.

_____________________________________________________________

*/ public function Hint()

{

visible = false;

ok.addEventListener(MouseEvent.CLICK,hideHint);

stop();

}

/*

_____________________________________________________________

Метод set hint - установка текста информации.

_____________________________________________________________

Формальный параметр:

val - текст информации.

_____________________________________________________________

*/ public function set hint(val:String):void

{

gotoAndStop(1);

this.field.text = val;

visible = true;

}

/*

_____________________________________________________________

Метод hideHint - скрытие подсказки.

_____________________________________________________________

Формальный параметр:

e - событие мышки.

_____________________________________________________________

*/ private function hideHint(e:MouseEvent):void

{

visible = false;

}

}

}

/*

_____________________________________________________________

Класс событий приложения.

_____________________________________________________________

Используемые глобальные константы:

END_TRANSPORT - событие выхода в меню;

FIRST_TRANSPORT - событие первой инициализации меню;

NEW_TRANSPORT - событие создания меню.

_____________________________________________________________

*/package src

{

import flash.events.Event;

public class TEvent extends Event

{

public static const END_TRANSPORT:String = 'endTransport';

public static const FIRST_TRANSPORT:String = 'firstTransport';

public static const NEW_TRANSPORT:String = 'newTransport';

/*

_____________________________________________________________

Конструктор класса.

_____________________________________________________________

*/ public function TEvent(type:String, bubbles:Boolean=false, cancelable:Boolean=false)