Решение транспортных задач венгерским методом

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

Министерство образования и науки Украины

Севастопольский национальный технический университет

Кафедра

Информационных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

на тему: «Решение транспортных задач венгерским методом»

по курсу «Методы исследования операций»

Выпонил: ст. гр. И-23 д

Костенко К.

Приняла: ст.пр. Заикина Е.Н.

Севастополь

2011

АННОТАЦИЯ

транспортная задача решение венгерский метод

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

СОДЕРЖАНИЕ

Введение

1 Краткий обзор решения транспортных задач

1.1 Постановка Т-задачи

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

1.2.1 Метод северо-западного угла

1.2.2 Метод минимальной стоимости

1.2.3 Метод штрафов

2 Содержательная постановка задачи

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

3 Разработка и описание алгоритма решения задачи

3.1 Предварительный этап

3.2 Поисковый этап

3.3 Этап построения цепочки и коррекции плана

3.4 Этап эквивалентных преобразований

4 Построение математической модели задачи

5 Получение оптимального решения

5.1 Решение варианта № 24 вручную

5.2 Решение задачи на ЭВМ

6 Анализ модели на чувствительность

Заключение

Библиографический список

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

Приложение Б. Текст программы

ВВЕДЕНИЕ

Целью настоящей курсовой работы является закрепление знаний, получаемых в процессе изучения дисциплины «Методы исследования операций», приобретение необходимых практических навыков комплексного применения теоретико-методологических принципов исследования операций и математического программирования к постановке, решению и анализу задач организационного управления.

Задача данной курсовой работы состоит в следующем:

изучить требуемый раздел дисциплины;

построить математическую модель оптимизационной задачи, соответственно содержательной постановке;

подобрать и разработать алгоритм решения поставленной задачи;

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

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

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

1 КРАТКИЙ ОБЗОР РЕШЕНИЯ ТРАНСТПОРТНЫХ ЗАДАЧ

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

1.1 Постановка Т-задачи

Пусть в пунктах А1, А2, …, Аm производят некоторый однородный продукт, причем объем производства в пункте Аi составляет ai единиц (i = 1, ..., m). Допустим, что данный продукт потребляют в пунктах B1, B2, …, Bn, а объем потребления в пункте Вj составляет bj единиц (j = 1, …, n).

Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пунт потребления. Транспортные издержки по перевозке из пункта Аi в пункт Вj единицы продукции равны cij (i = 1, ..., m, j = 1, …, n).

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

Существуют следующие методы решения транспортных задач: метод потенциалов и венгерский метод.

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

Метод потенциалов позволяет, исходя из некоторого опорного плана перевозок, построить за конечное число итераций решение Т-задачи.

Общая схема метода такова. В данном начальном опорном плане каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Аi и Вj, связанных основной коммуникацией, были равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения опорного плана Т-задачи.

Опорный план можно найти следующими методами:

метод северо-западного угла;

метод минимальной стоимости;

метод штрафов.

Рассмотрим подробнее каждый из этих методов.

1.2.1 Метод северо-западного угла

Строится нулевая матрица размером n*m. Начиная с северо-западного угла в естественном порядке осуществляется заполнение матрицы. Заполнение осуществляется по следующему правилу: для каждого элемента выбирается минимальное число из соответствующих ему значений вектора производства и потребления; это минимальное число вычитается из соответствующих данному элементу значений векторов производства и потребления. Так как при корректировке один из элементов, либо а, либо b, становится равным нулю, то соответствующая строка или столбец исключаются в дальнейшем из рассмотрения. Процесс заполнения продолжается до тех пор, пока все элементы векторов производства и потребления не станут равными нулю. Проверяется вырожденность полученного плана.

1.2.2 Метод минимальной стоимости

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

Замечания:

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

данный метод лучше северо-западного угла.

1.2.3 Метод штрафов

Штрафы для строки или столбца представлят положительную разницу между минимальном элементом строки(столбца) и следующим за ним по величине минимальным элементом строки или столбца. Расчитываются штрафы для всех строк и столбцов матрицы. Заполнение опорного плана начинается с минимального элемента строки или столбца с максимальным штрафом. Выбор элементов плана Х и коррекция векторов потребления и постановок осуществляется как рассмотрено выше.

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

Замечание:

отсутствует правило выбора альтернативы при равенстве штрафов

метод дает решение близкое к оптимуму.

Нахождение оптимального плана происходит по следующему алгоритму:

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

Сij=Ui-Vj;

U1=1;

2. Выполняется пересчет матрицы С по правилу:

С0=C-(Ui-Vj)

3. Проверка на оптимальность. Если все компоненты матрицы С0 не отрицательны, то мы достигли оптимального решения. В противном случае план можно улучшить.

4. Среди элементов матрицы С0 отыскивается минимальный отрицательный, который обозначается . Соответствующая ему коммуникация будет вводится в базис. Данную коммуникацию в плане Х обозначают 0+.

5. Для определения коммуникации, выводимой из базиса необходимо построить цепочку. Цепочка строится следующим образом. Начиная со строк матрицы Х вычеркиваются те из них, в которых один не нулевой элемент. Подобную операцию повторяют затем по столбцам, следом по строкам и т.д.

В результате проведенной процедуры не вычеркнутыми оказываются элементы, которые состовляют цепочку. Цепочка замкнута, содержит четное число элементов и строится, начиная от 0+, безразлично в каком направлении, по ходу ладьи в шахматах.

При этом элементы, стоящие на нечетных местах помечаются минусом, а на четных - плюсом.

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

Q=min{Q-}, который прибавляется или вычитается к элементам плана Х, согласно индексации. При этом коммуникация, значение которой равной нулю оказывается выведенной из базиса.

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

6. Коррекция значения целевой функции:

L = L - ||*Q

7. Подсчитывают матрицу С:

а) Отмечают в матрице нули, соответствующие базисным элементам плана Х.

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

в) Процесс вычеркивания продолжается до тех пор, пока есть что вычеркивать. После этого к элементам вычеркнутых строк прибавляют + ||, а из вычеркнутых столбцов вычитают модуль -||. Переходим в пункт 3.

2 СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

В пунктах Аi имеются запасы некоего продукта, который необходимо перевезти потребителям Вj.

Требуется отыскать такой план перевозок, при котором весь продукт из пунктов Аi будет вывезен, потребности потребителей полностью удовлетворены и суммарные транспортные затраты будут минимальны.

Потребности потребителей (в условных единицах), количество продукта (груза) в каждом пункте (в тех же условных единицах) и транспортные затраты на перевозки продукции (груза) из пункта Аi и Вj заданы в таблице 1.1.

Таблица 2.1 - Исходные данные к расчету транспортной задачи венгерским методом

Вариант	Аi	B1	B2	B3	Запасы
24	A1	12	14	7.2	3100
	A2	15	12.4	3.1	550
	A3	7.7	18	22	1200
	А4	23	19	17.1	1850
	Потребности	2100	4080	520

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

В Украине известна фабрика производства шоколада «Рошен». Эта фабрика имеет 4 завода, расположенных в разных частях Украины, - в Киеве, Запорожье, Харькове и Виннице. Объем производства каждого завода составляет 3100, 550, 1200 и 1850 килограмм черного шоколада в месяц. Реализация продукции производится в трех крупых городах Украины - Донецке, Одессе и Львове. Объемы потребления в каждом городе различны и составляют 2100, 4080 и 520 килограмм черного шоколада в месяц соотвественно. Известна стоимость доставки продукции из каждого завода фирмы "Рошен" в названные города. Данные представлены в виде таблицы (таблица 1.2).

Таблица 2.2 - Таблица стоимости перевозки продукции

	Стоимость перевозок, евро./кг шоколада	Объем производства, кг
	12	14	7.2	3100
	15	12.4	3.1	550
	7.7	18	22	1200
	23	19	17.1	1850
Потребности, кг	2100	4080	520

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

3 РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

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

Суммарная невязка по строкам:

i = i = 1..m

Суммарная невязка по столбцам:

j = j = 1..n

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

Существенным нулем называется нуль матрицы С, соответствующая коммуникация которого в плане Х больше 0.

3.1 Предварительный этап

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

Аналогичная операция проделывается по строкам матрицы С'. В пезультате получаем матрицу С0. Для нулей матрицы С0, перемещаясь по столбцам сверху вниз и меняя столбцы слева направо строим начальный план Х0 и определяем невязку этого плана. Если невязка равна нулю, то рассчитывается целевая функция плана, в противном случае переходят к итерационной части алгоритма.

Разметка выполняется в начале итерации и сохраняется до ее конца. В ходе эквивалентных преобразований матрицы С разметка переносится. Различают символом “+” столбцы, невязки которых нулевые и существенные нули. Прочие элементы разметки добавляются в ходе итерации. Столбцы (или строки), отмеченные символом “+”, называются выделенными и образуют выделенную часть матрицы С.

3.2 Поисковый этап

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

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

3.3 Этап построения цепочки и коррекции плана

Цепочка незамкнута, содержит нечетное число элементов и, в принципе, может состоять из одного нуля со штрихом.

Построение цепочки происходит в следующей последовательности: от найденного нуля со штрихом по столбцу к нулю со звездой, а от нуля со звездой по строке к нулю со штрихом. Далее выбирается корректирующий элемент по правилу: невязка строки начала, невязка строки конца и элементы плана Х, которые соответствуют нулю со “*”, входящих в цепочку. = min {i, j, Х*ij цепочка}

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

3.4 Этап эквивалентных преобразований

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



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

Рисунок 3.1 - Структурная схема алгоритма венгерского метода

4 ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ

4.1 Переменные

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

4.2 Целевая функция

Так как стоимость (Сij) перевозки одного килограмма груза известна, то общие затраты на его перевозку составляют: Сij*Хij. Обозначив суммарные затраты через L, можно дать следующую математическую формулировку целевой функции: определить такие значения Хij, при которых значение L было бы минимальным.

4.3 Ограничения

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

Все вышеперечисленное приводит к построению линейной модели вида:

5 ПОЛУЧЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ

5.1 Решение варианта № 24 вручную

Условие представлено в таблице 5.1.

Таблица 5.1 - Исходные данные к расчету варианта № 24

				Ai
С:	12	14	7.2	3100
	15	12.4	3.1	550
	7.7	18	22	1200
	23	19	17.1	1850
Bj	2100	4080	520	6700

Проверка условия баланса:

Так как условие баланса выполняется, то в матрицу С нечего не добавляется.

5.1.1 Предварительный этап

Находим в каждом столбце матрицы С минимальный элемент, вычетаем его из всех элементов столбца. Получаем матрицу С'.

В каждой строке матрицы С' отыскиваем минимальный элемент, который вычитается из всех элементов строки. В результате получем матрицу С0. Матрица С0 имеет вид:

С0:	2.7	0	2.5
	7.3	0	0
	0	5.6	18.9
	8.7	0	7.4

В соответствии с матрицей С0 строим план Х0:

				Ai
Х0:		3100		0
		550		0
	1200			0
		430		1420
Bj	900	0	520

Построив начальный план Х0, рассчитаем невязки по столбцам и по строкам.

· по столбцам:

b1=2100-1200=900;

b2=4800-980-430=0;

b3=520-0=520;

· по строкам:

а1=3100-3100=0;

а2=550-550=0;

а3=1200-1200=0;

а4=1850-430=1420;

Рассчитаем суммарную невязку плана

т.к то переходим к первой итерации.

5.1.2 Первая итерация

Этап разметки

Символами “+” выделяем столбы с нулевыми невязками. Символами “-” отметим существенные нули матрицы .

		+
	2.7		2.5
C0:	7.3		0
		5.6	18.9
	8.7		7.4

Этап поиска

В невыделенной части матрицы С0 найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку “+”. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.

		(+)
	2.7		2.5	+
C0:	7.3	*	0'	+
	'	5.6	18.9	+
	8.7	'	7.4

Этап построения цепочки

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

Этап коррекции плана Х

Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент . Находим его по минимуму из невязки строки начала цепочки, из невязки столбца конца цепочки и значения элемента Xij, соответствующего 0*. =min{1420, 520, 550}=520.

		(+)
	2.7	'	2.5	+
C0:	7.3	*	0'	+
	'	5.6	18.9	+
	8.7	'	7.4

Прибавляем =520 к элементам Xij, которым в цепочке соответствовали элементы Сij=0', и отнимаем =520 от элементов Xij, которым в цепочке соответсвовали элементы Cij=0*:

				Ai
Х1:		3100		0
		30	520	0
	1200			0
		950		900
Bj	900	0	0

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

· по столбцам:

b1=2100-1200=900;

b2=4800-3100-30-950=0;

b3=520-520=0;

· по строкам:

а1=3100-3100=0;

а2=550-30-520=0;

а3=1200-1200=0;

а4=1850-1850=0;

Рассчитаем суммарную невязку плана Х1:т.к. то переходим ко второй итерации.

5.1.3 Вторая итерация

Этап разметки

Символами “+” выделяем столбы с нулевыми невязками. Символами “-” отметим существенные нули матрицы .

		+	+
	2.7		2.5
C0:	7.3		0
	'	5.6	18.9	+
	8.7		7.4

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

Этап эквивалентных преобразований

На данном этапе находится минимальный положительный элемент в невыделенной части матрицы С0 h=min{2.7, 7.3, 8.7}=2.7; h прибавляется к выделенным столбцам и вычитается из невыделенных строк. Получили матрицу С1:

	0	0	2.5
C1	4.6	0	0
	0	8.3	21.6
	6	0	7.4

Этап разметки

Символами “+” выделяем столбы с нулевыми невязками. Символами “-” отметим существенные нули матрицы .

		+	+
			2.5
C1	4.6
		8.3	21.6
	6		7.4

Этап поиска

В невыделенной части матрицы С1найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку “+”. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.

		(+)	(+)
	'	*	2.5	+
C1	4.6	'	*	+
	'	8.3	21.6	+
	6	'	7.4

Этап построения цепочки

Цепочка венгерского метода состоит из нечетного числа элементов, начинается нулем в строке с положительной невязкой, проходит по столбцу до нуля, отмеченного знаком *, и заканчивается нулем, находящемся в столбце с положительной невязкой. В данном случае полученная цепочка показана в таблице:

		(+)	(+)
	'	*	2.5	+
C1	4.6	'	*	+
	'	8.3	21.6	+
	6	'	7.4

Этап коррекции плана Х

Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент . Находим его по минимуму из невязки строки начала цепочки, из невязки столбца конца цепочки и значения элемента Xij, соответствующего 0*. =min{900, 900, 3100}=900;

Прибавляем =900 к элементам Xij, которым в цепочке соответствовали элементы Сij=0', и отнимаем =900 от элементов Xij, которым в цепочке соответсвовали элементы Cij=0*:

				Ai
Х1:	900	2200		0
		30	520	0
	1200			0
		1850		0
Bj	0	0	0

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

· по столбцам:

b1=2100-1200-900=0;

b2=4800-2200-30-1850=0;

b3=520-520=0;

· по строкам:

а1=3100-900-2200=0;

а2=550-30-530=0;

а3=1200-1200=0;

а4=1850-950=900;

После коррекции плана суммарная невязка Переходим к расчёту целевой функции:

L=900*12+2200*14+30*12.4+520*3.1+1200*7.7+1850*19=87974.

5.2 Решение задачи на ЭВМ

Для проведения вычислительного эксперимента была разработана программа в среде Builder С++, которая выполняет расчет транспортной задачи венгерским методом. Ввод (загрузка) данных отображен на рисунке 5.1.

Рисунок 5.1 - Ввод данных в таблицу

После нажатия кнопки “Решить” появляются вкладки с итерациями. Каждая вкладка описывает 1 шаг. Сверху находится матрица С, снизу матрица Х. Результаты програмных подсчётов на ЭВМ показаны на рисунках 5.2 - 5.6.



Рисунок 5.2 - Реализация предварительного этапа на ЭВМ

Рисунок 5.3 - Реализация первой иттерации на ЭВМ

Рисунок 5.4 - Реализация этапа эквивалентных преобразований на ЭВМ

Рисунок 5.5 - Реализация этапо повторного поиска на ЭВМ



Рисунок 5.6- Реализация этапа коррекции плана на ЭВМ и получения оптимального плана

6 АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

Проведем анализ модели на чувствительность в соответствии с постановкой задачи.

Условие задачи:

				Ai
С:	12	14	7.2	3100
	15	12.4	3.1	550
	7.7	18	22	1200
	23	19	17.1	1850
Bj	2100	4080	520	6700

Оптимальный план Хopt, соответствующий данной задаче имеет вид:

				Ai
Хopt:	900	2200		0
		30	520	0
	1200			0
		1850		0
Bj	0	0	0

Значение целевой функции составляет L = 87974 [евро].

Соответствующая структура коммуникаций имеет вид:

Выполним анализ модели.

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

Целевую функцию L можно представить в виде суммы

где Li - значения минимальных транспортных издержек, вычисленные по строкам матрицы Хopt.

L1 = 900*12 + 2200*14 =41600 [у.е].

L2 = 30*12.4 + 520*3.1=1984 [у.е].

L3 = 1200*7.7= 9240 [у.е].

L4 = 1850*19= 35150 [у.е].

Поэтому наиболее выгодно уменьшить объем производимого продукта в пункте А1, так как L1 вносит наибольший вклад в целевую функцию, а увеличивать его выгоднее всего в пункте А2, так как перевозка из данного пункта стоит дешевле, чем из других пунктов.

Установим ориентировочные, а затем уточненные пределы изменения запаса груза. Так как ориентировочный диапазон устанавливается из диапазона 0 < max Ai (i=1,4), и А1=3100, А2=550, А3=1200 А4=1850, то max Ai(i=1..4)=A1=3100. Для нашей задачи 0<<3100.

Решение транспортной задачи будем определять для следующиих векторов объема производства:

А = (3000, 650, 1200, 1850),

А = (2900, 750, 1200, 1850),

А = (2800, 850, 1200, 1850),

А = (1000, 2650, 1200, 1850),

А = (990, 2660, 1200, 1850),

А = (960, 2690, 1200, 1850),

А = (930, 2720, 1200, 1850),

А = (900, 2750, 1200, 1850).

Результаты вычислений показали, что, начиная с вектора А = (900, 2750, 1200, 1850), структура оптимального решения будет изменяться. Она определяется следующим планом Х'opt:

				Ai
Х'opt:	900			0
		2230	520	0
	1200			0
		1850		0
Bj	0	0	0

Этому плану соответствует граф коммуникаций:

Оптимальное решение транспортных издержек составит L' = 84454 евро.

Поэтому уточненный диапазон будет находиться в пределах 0 < < 2200.

3) Найдем зависимость оптимального решения и оптимального значения целевой функции от изменений компонент вектора запаса груза. Условия и результаты вычислительного эксперимента приведены в таблице 6.1.

Таблица 6.1 - Условия и результаты вычислительного эксперимента

	0	1	2	3	4	5	6	7	8	9	10	11
a1	3100	2900	2700	2500	2300	2100	1900	1700	1500	1300	1100	900
a2	550	750	950	1150	1350	1550	1750	1950	2150	2350	2550	2750
a3	1200	1200	1200	1200	1200	1200	1200	1200	1200	1200	1200	1200
a4	1850	1850	1850	1850	1850	1850	1850	1850	1850	1850	1850	1850
L, евро	0	320	640	960	1280	1600	1920	2240	2560	2880	3200	3520
L, евро	87974	87654	87334	87014	86694	86374	86054	85734	85414	85094	84774	84454

Рисунок 6.1 - График зависимости затрат на перевозки от изменения объемов производства

Таким образом, с уменьшением объема производимого продукта в пункте А1 (Киеве) на 2200кг и увеличением на такую же величину объема производимого продукта в пункте А2 (Запорожье), транспортные расходы на перевозку черного шоколада удается сократить еще на 3520 евро. При этом общая стоимость транспортных расходов составит 84454 евро в месяц.

ЗАКЛЮЧЕНИЕ

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

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

Алгоритм венгреского метода был реализован программно в среде C++ Builder. С помощью разработанной программы был проведен анализ модели на чувствительность. В ходе этого анализа выяснилось, что затраты на перевозку товара, которые оптимально составили 87974 евро в месяц, можно уменьшить на 3520 евро, если в самом затратном пункте производства уменьшить объем выпускаемого продукта на 2200 кг, а в наименее затратном настолько же увеличить. При этом общая стоимость транспортных расходов составит 84454 евро в месяц.

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

Библиографический список

1. Балашевич В.А. Основы математического программирования [Текст] / В.А. Балашевич. -- Минск.: Высш школа, 1985. -- 174с.

2. Зайченко Ю.П. Исследование операций [Текст] / Ю.П. Зайченко -- М.: Высш. школа, 1979. -- 156с.

3. Карлусов В.Ю. Методические указания к практическим занятиям по дисциплине «Исследование операций и методы оптимизации» для студентов специальности 7.080401 - «Компьютеризированные системы обработки информации и управления» [Текст] / В.Ю. Карлусов, Л.П. Старобинская -- Севастополь: Изд-во СевГТУ, 1997. -- 26с.

4. Карлусов В.Ю. Методические указания к вы-полнению лабораторных и контрольных работ для студентов дневной и заочной форм обучения специальности 7.080401 - «Информационные управляющие системы и технологии» [Текст] / В.Ю. Карлусов, Л.П. Старобинская -- Севастополь: Изд-во СевГТУ, 1998. -- 61с.

ПРИЛОЖЕНИЕ А

Описание интерфейса программы

Интерфейс программы очень простой и удобный для пользования. На рисунках 1 и 2 преведенны элементы интерфейса до решения поставленной задачи и после соотвественно.

Рисунок 1 - Интерфейс программы до выполнения

Весь интерфейс состоит из 9 кнопок. Стрелочки предназначены для увеличения размерности исходной матрицы. Кнопки “Файл->Cохранить” и “ Файл->Oткрыть” сохраняют и загружают таблицы соответственно. Кнопка “Файл->Новый” очищает матрицы стоимостей, потребления и запаса.

Рисунок 2 - Интерфейс программы после выполнения

После нажатия кнопки “Решить” появляются вкладки в которых отображается каждый этап (шаг) решения транспортной задачи.

Приложение Б

Текст программы

//---------------------------------------------------------------------------

#include <vcl.h>

#include <string>

#include <math.h>

#include <fstream.h>

#pragma hdrstop

#include "Main.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "Spin"

#pragma link "IWImageList"

#pragma link "cspin"

#pragma resource "*.dfm"

TForm1 *Form1;

UnicodeString MyFName="";

int Cn,Cm;

int **C;

int **C0;

int **CS;

int Pm;

int *P;

int Zn;

int *Z;

int Dn,Dm;

int **D;

int OPrz=0;

int OPtr=0;

int Xn,Xm;

int **X;

int Nn,Nm;

int **N;

int posl;

int pstr;

TTabSheet *Sheet;

TStringGrid *Grid;

TStringGrid *GrX;

TLabel* LabelC;

TLabel* LabelX;

int Fn;

int *F;

int Gm;

int *G;

TStringGrid *GridF;

int L;

UnicodeString Lstr;

int Cep[50][7][8];

int nomer=0;

int NKor=0;

int NIter=0;

//Конструктор формы

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//Вывод подсказки//При создании формы

void __fastcall TForm1::FormCreate(TObject *Sender)

{

StoimPer->Cells[0][0]="Ai";

for (int j=1; j<StoimPer->ColCount; j++)

{

StoimPer->Cells[j][0]="B"+IntToStr(j);

}

for (int i=1;i<StoimPer->RowCount; i++)

{

StoimPer->Cells[0][i]="A"+IntToStr(i);

}

Potr->Cells[0][0]="Потр";

Zapas->Cells[0][0]="Запас";

}

//При вводе в ячейку таблицы

void __fastcall TForm1::TabKeyPress(TObject *Sender, wchar_t &Key)

{

Set <char, 0, 255> Dig;

TStringGrid* Tab=(TStringGrid *)Sender;

Dig<<'0'<<'1'<<'2'<<'3'<<'4'<<'5'<<'6'<<'7'<<'8'<<'9'<<'\b'<<','<<'.'<<VK_RETURN;

if(!Dig.Contains(Key)){

Key=0;

Beep();

}

}

//При нажатии клавиши "Решить"

void __fastcall TForm1::ReshutClick(TObject *Sender)

{

nomer=0;

//Создание матрицы C

Cn=StoimPer->RowCount-1;

Cm=StoimPer->ColCount-1;

for(int i=0;i<50;i++)

for(int j=0;j<Cn;j++)

for(int z=0;z<Cm;z++)

Cep[i][j][z]=0;

C=new int*[Cn];

C0=new int*[Cn];

CS=new int*[Cn];

for (int i=0; i<Cn; i++){

C[i]=new int[Cm];

C0[i]=new int[Cm];

CS[i]=new int[Cm];

}

for(int i=1;i<StoimPer->RowCount;i++)

for(int j=1;j<StoimPer->ColCount;j++)

{

if(StoimPer->Cells[j][i]==""){

MessageDlg(L"Введите данные в таблицу стоимости перевозки.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

else{

C[i-1][j-1]=(int)(StoimPer->Cells[j][i].ToDouble()*100);

C0[i-1][j-1]=(int)(StoimPer->Cells[j][i].ToDouble()*100);

}

}

//Создание матрицы потребностей

Pm=Potr->ColCount-1;

P=new int[Pm];

for(int i=1;i<Potr->ColCount;i++)

{

if(Potr->Cells[i][0]=="")

{

MessageDlg(L"Введите данные в таблицу потребления.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

else

P[i-1]=(int)(Potr->Cells[i][0].ToDouble()*100);

}

//Создание матрицы запасов

Zn=Zapas->RowCount-1;

Z=new int[Zn];

for(int i=1;i<Zapas->RowCount;i++)

{

if(Zapas->Cells[0][i]=="")

{

MessageDlg(L"Введите данные в таблицу запасов.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

else

Z[i-1]=(int)(Zapas->Cells[0][i].ToDouble()*100);

}

for(int i=0;i<Ogran->RowCount;i++)

for(int j=0;j<Ogran->ColCount;j++)

Ogran->Cells[j][i]="10000";

Dn=Ogran->RowCount;

Dm=Ogran->ColCount;

D=new int*[Dn];

for (int i=0; i<Dn; i++)

D[i]=new int[Dm];

for(int i=0;i<Dn;i++)

for(int j=0;j<Dm;j++)

D[i][j]=(int)(Ogran->Cells[j][i].ToDouble()*100);

//Инициализыция невязок

OPrz=0;

OPtr=0;

for(int i=0;i<Zn;i++)

OPrz+=Z[i];

for(int i=0;i<Pm;i++)

OPtr+=P[i];

if(OPrz!=OPtr){

MessageDlg(L"Задача не удавлетворяет условию баланса.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

if(PageControl->PageCount>2){

NIter=0;

for(int i=PageControl->PageCount-1;i>=2;i--)

PageControl->Pages[i]->~TTabSheet();

}

//Создание С штрих

for(int j=0;j<Cm;j++)

{

int min=C[0][j];

for(int i=1;i<Cn;i++){

if(C[i][j]<min)

min=C[i][j];

}

for(int i=0;i<Cn;i++){

C[i][j]-=min;

CS[i][j]=C[i][j];

}

}

//Создание C0

for(int i=0;i<Cn;i++){

int min=C[i][0];

for(int j=1;j<Cm;j++)

if(C[i][j]<min)

min=C[i][j];

if (min!=0)

for(int j=0;j<Cm;j++)

C[i][j]-=min;

}

Predv();

//Создание матрицы опорного плана

Xn=Cn;

Xm=Cm;

X=new int*[Xn];

for (int i=0; i<Xn; i++)

X[i]=new int[Xm];

for (int j=0; j<Cm; j++){

for (int i=0; i<Cn; i++){

if(C[i][j]==0){

//Если ограничение меньше

if(D[i][j]<=P[j] && D[i][j]<=Z[i]){

X[i][j]=D[i][j];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

else{

if(P[j]<Z[i]){

X[i][j]=P[j];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

else{

X[i][j]=Z[i];

P[j]-=X[i][j];

Z[i]-=X[i][j];

}

}

}

else

X[i][j]=0;

}

}

//проверка опитимальности

OPrz=0;

OPtr=0;

for(int i=0;i<Zn;i++)

OPrz+=Z[i];

for(int i=0;i<Pm;i++)

OPtr+=P[i];

if((OPrz+OPtr)==0){

//Заполнения таблицы издержек

Izderg->RowCount=Cn;

Izderg->ColCount=Cm;

for(int i=0;i<Cn;i++)

for(int j=0;j<Cm;j++)

Izderg->Cells[j][i]=FormatFloat("",C[i][j]/100.0);

//Заполнения таблицы опорного плана

Plan->RowCount=Xn;

Plan->ColCount=Xm;

for(int i=0;i<Xn;i++)

for(int j=0;j<Xm;j++){

if(X[i][j]==0)

Plan->Cells[j][i]="";

else

Plan->Cells[j][i]=FormatFloat("",X[i][j]/100.0);

}

L=0;

Lstr="L=";

for(int i=0;i<Cn;i++)

for(int j=0;j<Cm;j++)

if(X[i][j]>0)

{

L+=X[i][j]*C0[i][j];

Lstr+=FormatFloat("",C0[i][j]/100.0)+"*"+FormatFloat("",X[i][j]/100.0)+"+";

}

Lstr.Delete(Lstr.Length(),1);

Lstr+="="+FormatFloat("",L/10000.0);

Edit2->Text=Lstr;

MessageDlg(L"План оптимизирован.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

return;

}

//создание матрицы нулей

Nn=Cn;

Nm=Cm;

N=new int*[Nn];

for (int i=0; i<Nn; i++)

N[i]=new int[Nm];

//Начало итерации-----------------------------------------------------------

while((OPrz+OPtr)!=0)

{

posl=-1;

pstr=-1;

int v=0;

int *Q=new int[Cn*Cm];

//определение нулей

for(int i=0;i<Cn;i++)

for(int j=0;j<Cm;j++)

{

if(C[i][j]==0)

{

if(X[i][j]==D[i][j])

N[i][j]=2; //полный ноль

else{

if(X[i][j]==0)

N[i][j]=0; //обычный ноль

else

N[i][j]=1; //неполный ноль

}

}

else

N[i][j]=-1; //не ноль

}

//массив для выделения строк

Fn=Zn;

F=new int[Fn];

for(int i=0;i<Fn;i++)

F[i]=0;

//выделение столбцов

Gm=Pm;

G=new int[Gm];

for(int i=0;i<Gm;i++)

{

if(P[i]==0) //Потребление равно нулю

G[i]=1; //Выделение

else

G[i]=0; //нет

}

bool kor=false; //необходимость коррекции

bool np; //необходимостть нового поиска

while(kor==false)

{

np=false;

for(int j=0;j<Nm;j++)

{

if(G[j]==1) //если выделен столбец

continue;

else

{

for(int i=0;i<Nn;i++)

{

if(F[i]==1) //если выделена строка

continue;

if(N[i][j]==0 || N[i][j]==1) //если неполный ноль

{

N[i][j]=3; //обозначение штрихом

if(Z[i]==0) //если запас равен нулю

{

F[i]=1; //выделение строки

for(int k=0;k<Cm;k++) //проход по строке

{

if(G[k]==0) //если строка невыделена

continue;

if(N[i][k]==1 || N[i][k]==2) //если сущ. ноль

{

N[i][k]=4; //обозначение звездочкой

G[k]=0; //снятие выделения

np=true; //необходимость поиска заново

}

}

}

else

{

kor=true; //необходимость коррекции плана

Q[v]=Z[i]; //запоминание невязки по строке

v++; //увеличение количества

Q[v]=D[i][j]-X[i][j]; //резервы насыщения

v++;

posl=j; //запоминание места

pstr=i; //первого элемента

}

}

if(np==true || kor==true)

break;

}

}

if(np==true || kor==true)

break;

}

//эквивалентне преобразования

if(np==false && kor==false)

{

bool go=false;

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

if(F[i]==1 && G[j]==1)

{

if(C[i][j]<0)

{

go=true;

break;

}

}

else

{

if(C[i][j]>0)

{

go=true;

break;

}

}

}

}

if(go==true)

break;

}

if(go==false)

{

MessageDlg(L"Задача неразрешима.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

Edit2->Text="L=0";

return;

}

bool first=true;

int min=0;

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

//если один раз выделена ячейка

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

//если дважды выделена

if(F[i]==1 && G[j]==1)

{

//если первый раз

if(first==true)

{

if(C[i][j]<0)

{

min=abs(C[i][j]);

first=false;

}

}

else

{

if(C[i][j]<0)

{

if(abs(C[i][j])<min)

min=abs(C[i][j]);

}

}

}

//если невыделена

if(F[i]==0 && G[j]==0)

{

if(first==true)

{

if(C[i][j]>0)

{

min=C[i][j];

first=false;

}

}

else

{

if(C[i][j]>0)

{

if(C[i][j]<min)

min=C[i][j];

}

}

}

}

}

}

//вычитание элемента

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

//если один раз выделена

if((F[i]==1 && G[j]==0) || (F[i]==0 && G[j]==1))

continue;

else

{

//если дважды

if(G[j]==1 && F[i]==1)

C[i][j]+=min;

else

C[i][j]-=min;

}

}

}

//новая разметка

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

if(C[i][j]==0)

{

if(X[i][j]==D[i][j])

N[i][j]=2;

else

{

if(X[i][j]==0)

N[i][j]=0;

else

N[i][j]=1;

}

}

else

N[i][j]=-1;

}

}

delete []F;

F=NULL;

Ecviv();

//массив для выделения строк

Fn=Zn;

F=new int[Fn];

for(int i=0;i<Fn;i++)

F[i]=0;

}

}

NKor=0;

//составление цепочки

int* Str=new int[Cn*Cm];

int* Stol=new int[Cn*Cm];

int str=0;

int stol=0;

Str[str]=pstr;

Stol[stol]=posl;

Cep[nomer][pstr][posl]=1; //стрела вправо

str++;

stol++;

Stol[stol]=posl; //для начала цепочки

stol++;

int stroka=-1;

while(1)

{

for(int i=0;i<Cn;i++)

{

if(N[i][Stol[stol-1]]==4) //если сущ. 0*

{

stroka=i;

Str[str]=i;

if(Str[str]<Str[str-1]) //если новый 0* выше 0'

{

if (Stol[stol-2]<Stol[stol-1])//если старый 0* левее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=2; //слева вверх

for(int i=Str[str]+1;i<Str[str-1];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else

{

if (Stol[stol-2]>Stol[stol-1]) //если старый 0* правее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=5; //справа наверх

for(int i=Str[str]+1;i<Str[str-1];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else //если начало цепочки

{

for(int i=Str[str]+1;i<=Str[str-1];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

}

}

else //если новый 0* ниже 0'

{

if (Stol[stol-2]<Stol[stol-1])//если старый 0* левее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=6; //слева вниз

for(int i=Str[str-1]+1;i<Str[str];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else

{

if (Stol[stol-2]>Stol[stol-1]) //если старый 0* правее 0'

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=7; //справа вниз

for(int i=Str[str-1]+1;i<Str[str];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

Cep[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

else //если начало цепочки

{

for(int i=Str[str-1];i<Str[str];i++)

{

if(Cep[nomer][i][Stol[stol-1]]==3)

[nomer][i][Stol[stol-1]]=12; //крест

else

Cep[nomer][i][Stol[stol-1]]=4; //вертикально

}

}

}

}

str++;

Q[v]=X[i][Stol[stol-1]];

v++;

break;

}

}

if(stroka==-1)

{

Q[v]=P[Stol[stol-1]];

v++;

break;

}

for(int j=0;j<Cm;j++)

{

if(N[Str[str-1]][j]==3) //если сущ. 0'

{

Stol[stol]=j;

if(Stol[stol]<Stol[stol-1]) //если новый 0' левее 0*

{

if (Str[str-2]<Str[str-1]) //если старый 0' выше 0*

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=2; //сверху влево

for(int i=Stol[stol]+1;i<Stol[stol-1];i++)

{

if(Cep[nomer][Str[str-1]][i]==4)

Cep[nomer][Str[str-1]][i]=12; //крест

else

Cep[nomer][Str[str-1]][i]=3; //горизонталь

}

Cep[nomer][Str[str-1]][Stol[stol]]=9; //стрела влево

}

else //если старый 0' ниже 0*

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=6; //снизу влево

for(int i=Stol[stol]+1;i<Stol[stol-1];i++)

{

if(Cep[nomer][Str[str-1]][i]==4)

Cep[nomer][Str[str-1]][i]=12; //крест

else

Cep[nomer][Str[str-1]][i]=3; //горизонталь

}

Cep[nomer][Str[str-1]][Stol[stol]]=9;

}

}

else //если новый 0' правее 0*

{

if (Str[str-2]<Str[str-1]) //если старый 0' выше 0*

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=5; //слева вниз

for(int i=Stol[stol-1]+1;i<Stol[stol];i++)

{

if(Cep[nomer][Str[str-1]][i]==4)

Cep[nomer][Str[str-1]][i]=12; //крест

else

Cep[nomer][Str[str-1]][i]=3; //горизонталь

}

Cep[nomer][Str[str-1]][Stol[stol]]=1;

}

else //если старый 0' ниже 0*

{

Cep[nomer][Str[str-1]][Stol[stol-1]]=7; //снизу вправо

for(int i=Stol[stol-1]+1;i<Stol[stol];i++)

{

if(Cep[nomer][Str[str-1]][i]==4)

Cep[nomer][Str[str-1]][i]=12; //крест

else

Cep[nomer][Str[str-1]][i]=3; //горизонталь

}

Cep[nomer][Str[str-1]][Stol[stol]]=1;

}

}

stol++;

Q[v]=D[Str[str-1]][j]-X[Str[str-1]][j];

v++;

break;

}

}

stroka=-1;

}

nomer++;

//Создание новой вкладки

NewTab();

int min=Q[0];

for(int i=1;i<v;i++)

{

if(Q[i]<min)

min=Q[i];

}

str--;

stol--;

X[Str[str]][Stol[stol]]+=min;

P[Stol[stol]]-=min;

while(1)

{

if(str==0)

{

Z[Str[str]]-=min;

break;

}

stol--;

X[Str[str]][Stol[stol]]-=min;

str--;

X[Str[str]][Stol[stol]]+=min;

}

OPrz=0;

OPtr=0;

for(int i=0;i<Zn;i++)

OPrz+=Z[i];

for(int i=0;i<Pm;i++)

OPtr+=P[i];

delete []G;

G=NULL;

delete []F;

F=NULL;

delete []Q;

Q=NULL;

delete []Str;

Str=NULL;

delete []Stol;

Stol=NULL;

}

//!!!

MessageDlg(L"Задача оптимизированa.", mtConfirmation,

TMsgDlgButtons() << mbOK, 0);

//Заполнения таблицы издержек

Izderg->RowCount=Cn;

Izderg->ColCount=Cm;

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

switch (N[i][j])

{

case 4:

Izderg->Cells[j][i]="0*";

break;

case 3:

Izderg->Cells[j][i]="0'";

break;

case 2:

Izderg->Cells[j][i]=L'\u022a';

break;

case 1:

Izderg->Cells[j][i]=L'\u0230';

break;

case 0:

Izderg->Cells[j][i]="0";

case -1:

Izderg->Cells[j][i]=FormatFloat("",C[i][j]/100.0);

break;

}

}

}

//Заполнения таблицы опорного плана

Plan->RowCount=Xn;

Plan->ColCount=Xm;

for(int i=0;i<Xn;i++)

{

for(int j=0;j<Xm;j++)

{

if(X[i][j]==0)

Plan->Cells[j][i]="";

else

Plan->Cells[j][i]=FormatFloat("",X[i][j]/100.0);

}

}

L=0;

Lstr="L=";

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

if(X[i][j]>0)

{

L+=X[i][j]*C0[i][j];

Lstr+=FormatFloat("",C0[i][j]/100.0)+"*"+FormatFloat("",X[i][j]/100.0)+"+";

}

}

}

Lstr.Delete(Lstr.Length(),1);

Lstr+="="+FormatFloat("",L/10000.0);

Edit2->Text=Lstr;

//Освобождение памяти

delete []C;

C=NULL;

delete []P;

P=NULL;

delete []Z;

Z=NULL;

delete []D;

D=NULL;

delete []X;

X=NULL;

delete []N;

N=NULL;

}

void __fastcall TForm1::NOpenClick(TObject *Sender)

{

if(OpenDialog1->Execute())

{

MyFName=OpenDialog1->FileName;

Open(OpenDialog1->FileName);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::NSaveAsClick(TObject *Sender)

{

SaveDialog1->FileName=MyFName;

if(SaveDialog1->Execute())

{

MyFName=SaveDialog1->FileName;

Save(SaveDialog1->FileName);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::NSaveClick(TObject *Sender)

{

if(MyFName!="")

Save(MyFName);

else

if(SaveDialog1->Execute())

{

MyFName=SaveDialog1->FileName;

Save(SaveDialog1->FileName);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::NNewClick(TObject *Sender)

{

Zapas->RowCount=8;

for(int i=1;i<Zapas->RowCount;i++)

{

Zapas->Cells[0][i]="";

}

StoimPer->ColCount=8;

StoimPer->RowCount=8;

for(int i=1;i<StoimPer->RowCount;i++)

{

for(int j=1;j<StoimPer->ColCount;j++)

{

StoimPer->Cells[j][i]="";

}

}

Ogran->ColCount=8;

Ogran->RowCount=8;

Potr->ColCount=8;

for(int j=1;j<Potr->ColCount;j++)

{

Potr->Cells[j][0]="";

}

Edit2->Text="L=";

}

//---------------------------------------------------------------------------

void TForm1::Save(UnicodeString adr)

{

ofstream f(adr.t_str() ,ios::out);

for(int i=1;i<Zapas->RowCount;i++)

{

if(Zapas->Cells[0][i]=="")

{

f<<"0 ";

}

else

{

f<<Zapas->Cells[0][i].ToDouble()<<" ";

}

}

f<<"\n\n";

for(int i=1;i<StoimPer->RowCount;i++)

{

for(int j=1;j<StoimPer->ColCount;j++)

{

if(StoimPer->Cells[j][i]=="")

{

f<<"0 ";

}

else

{

f<<StoimPer->Cells[j][i].ToDouble()<<" ";

}

}

f<<"\n";

}

f<<"\n";

for(int i=0;i<Ogran->RowCount;i++)

{

for(int j=0;j<Ogran->ColCount;j++)

{

if(Ogran->Cells[j][i]=="")

{

f<<"0 ";

}

else

{

f<<Ogran->Cells[j][i].ToDouble()<<" ";

}

}

f<<"\n";

}

f<<"\n";

for(int i=1;i<Potr->ColCount;i++)

{

if(Potr->Cells[i][0]=="")

{

f<<"0 ";

}

else

{

f<<Potr->Cells[i][0].ToDouble()<<" ";

}

}

f.close();

}

//------------------------------------------------------------------------

void TForm1::Open(UnicodeString adr)

{

int k;

double d;

ifstream f(adr.t_str() ,ios::in|ios::nocreate);

f>>k;

//UDStrok->Position=k;

f>>k;

//UDStolb->Position=k;

//Zapas->RowCount=UDStrok->Position+1;

for(int i=1;i<Zapas->RowCount;i++)

{

f>>d;

Zapas->Cells[0][i]=FormatFloat("",d);

}

//StoimPer->RowCount=UDStrok->Position+1;

//StoimPer->ColCount=UDStolb->Position+1;

for(int i=1;i<StoimPer->RowCount;i++)

{

for(int j=1;j<StoimPer->ColCount;j++)

{

f>>d;

StoimPer->Cells[j][i]=FormatFloat("",d);

}

}

//Ogran->RowCount=UDStrok->Position;

//Ogran->ColCount=UDStolb->Position;

for(int i=0;i<Ogran->RowCount;i++)

{

for(int j=0;j<Ogran->ColCount;j++)

{

f>>d;

Ogran->Cells[j][i]=FormatFloat("",d);

}

}

//Potr->ColCount=UDStolb->Position+1;

for(int i=1;i<Potr->ColCount;i++)

{

f>>d;

Potr->Cells[i][0]=FormatFloat("",d);

}

f.close();

Edit2->Text="L=";

}

void TForm1::NewTab()

{

Sheet=new TTabSheet(this);

Grid=new TStringGrid(this);

GrX=new TStringGrid(this);

LabelC=new TLabel(this);

LabelX=new TLabel(this);

Sheet->Parent=this;

Sheet->PageControl=PageControl;

NIter++;

Sheet->Caption="Итер. №"+IntToStr(NIter);

Sheet->Name="S"+IntToStr(NIter-1);

Grid->Parent=Sheet;

Grid->OnDrawCell=StoimPer->OnDrawCell;

Grid->Left=29;

Grid->Top=34;

Grid->Height=181;

Grid->Width=256;

Grid->DefaultColWidth=35;

Grid->DefaultRowHeight=24;

Grid->FixedCols=0;

Grid->FixedRows=0;

Grid->ScrollBars=ssNone;

Grid->RowCount=Cn;

Grid->ColCount=Cm;

for(int i=0;i<Cn;i++)

{

for(int j=0;j<Cm;j++)

{

switch (N[i][j])

{

case 4:

Grid->Cells[j][i]="0*";

break;

case 3:

Grid->Cells[j][i]="0'";

break;

case 2:

Grid->Cells[j][i]=L'\u022a';

break;

case 1:

Grid->Cells[j][i]=L'\u0230';

break;

case 0:

Grid->Cells[j][i]="0";

case -1:

Grid->Cells[j][i]=FormatFloat("",C[i][j]/100.0);

break;

}

}

}

LabelC->Parent=Sheet;

LabelC->Left=17;

LabelC->Top=18;

LabelC->Caption="C"+IntToStr(NIter);

GrX->Parent=Sheet;

GrX->Left=29;

GrX->Top=221;

GrX->Height=181;

GrX->Width=256;

GrX->DefaultColWidth=35;

GrX->DefaultRowHeight=24;

GrX->FixedCols=0;

GrX->FixedRows=0;

GrX->ScrollBars=ssNone;

GrX->RowCount=Cn;

GrX->ColCount=Cm;

for(int i=0;i<Cn;i++)

for(int j=0;j<Cm;j++)

if(X[i][j]!=0)

GrX->Cells[j][i]=FormatFloat("",X[i][j]/100.0);

LabelX->Parent=Sheet;

LabelX->Left=17;

LabelX->Top=200;

LabelX->Caption="X"+IntToStr(NIter);

TStringGrid *GridP=new TStringGrid(this);

GridP->Parent=Sheet;

GridP->Left=286;

GridP->Top=221;

GridP->Height=181;

GridP->Width=39;

GridP->ColCount=1;

GridP->DefaultColWidth=35;

GridP->DefaultRowHeight=24;

GridP->FixedCols=0;

GridP->FixedRows=0;

GridP->RowCount=Cn;

GridP->ScrollBars=ssNone;

for(int i=0;i<Cn;i++)

GridP->Cells[0][i]=FormatFloat("",Z[i]/100.0);

TStringGrid* GridB=new TStringGrid(this);

GridB->Parent=Sheet;