Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки Украины
Севастопольский национальный технический университет
Кафедра
Информационных систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
на тему: «Решение транспортных задач венгерским методом»
по курсу «Методы исследования операций»
Выпонил: ст. гр. И-23 д
Костенко К.
Приняла: ст.пр. Заикина Е.Н.
Севастополь
2011
АННОТАЦИЯ
транспортная задача решение венгерский метод
В данной пояснительной записке приводится постановка задачи, её экономическая интерпретация и математическая модель. Рассматривается общая методика постановки, построения алгоритмов и решения транспортных задач. Особое внимание уделяется решению транспортных задач венгерским методом. Здесь также представлен текст программы, реализующей решение транспортных задач венгерским методом, описание работы программы, результаты проведения вычислительного эксперимента и сравнительная характеристика полученных результатов. В заключительной части пояснительной записки проводится анализ математической модели на чувствительность к изменению экономических аспектов.
СОДЕРЖАНИЕ
Введение
Краткий обзор решения транспортных задач
.1 Постановка Т-задачи
.2 Метод потенциалов
.2.1 Метод северо-западного угла
.2.2 Метод минимальной стоимости
.2.3 Метод штрафов
2 Содержательная постановка задачи
2.1 Экономическая интерпретация поставленной задачи
Разработка и описание алгоритма решения задачи
.1 Предварительный этап
.2 Поисковый этап
.3 Этап построения цепочки и коррекции плана
.4 Этап эквивалентных преобразований
Построение математической модели задачи
Получение оптимального решения
.1 Решение варианта № 24 вручную
.2 Решение задачи на ЭВМ
Анализ модели на чувствительность
Заключение
Библиографический список
Приложение А. Описание интерфейса программы
Приложение Б. Текст программы
ВВЕДЕНИЕ
Целью настоящей курсовой работы является закрепление знаний, получаемых в процессе изучения дисциплины «Методы исследования операций», приобретение необходимых практических навыков комплексного применения теоретико-методологических принципов исследования операций и математического программирования к постановке, решению и анализу задач организационного управления.
Задача данной курсовой работы состоит в следующем:
изучить требуемый раздел дисциплины;
построить математическую модель оптимизационной задачи, соответственно содержательной постановке;
подобрать и разработать алгоритм решения поставленной задачи;
написать программу, соответствующую разработанному алгоритму, отладить ее, используя в качестве тестовых данных рассчитанный вручную вариант;
провести анализ модели на чувствительность компонентов оптимального решения к изменению элементов ограничений.
Тема курсовой работы - решение транспортных задач венгерским методом - является актуальной на сегодняшний день. Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины 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 Метод штрафов
Штрафы для строки или столбца представлят положительную разницу между минимальном элементом строки(столбца) и следующим за ним по величине минимальным элементом строки или столбца. Расчитываются штрафы для всех строк и столбцов матрицы. Заполнение опорного плана начинается с минимального элемента строки или столбца с максимальным штрафом. Выбор элементов плана Х и коррекция векторов потребления и постановок осуществляется как рассмотрено выше.
Строка или столбец матрицы С, которым соответствует нулевое значение потребности или поставки при дальнейшем вычислении не участвуют в формировании штрафов. Процесс продолжается до тех пор, пока не обнулятся все вектора.
Замечание:
отсутствует правило выбора альтернативы при равенстве штрафов
метод дает решение близкое к оптимуму.
Нахождение оптимального плана происходит по следующему алгоритму:
. Расчитываются потенциалы пунктов производства и потребления, решая последовательность уравнений
Сij=Ui-Vj;=1;
. Выполняется пересчет матрицы С по правилу:
С0=C-(Ui-Vj)
. Проверка на оптимальность. Если все компоненты матрицы С0 не отрицательны, то мы достигли оптимального решения. В противном случае план можно улучшить.
. Среди элементов матрицы С0 отыскивается минимальный отрицательный, который обозначается d. Соответствующая ему коммуникация будет вводится в базис. Данную коммуникацию в плане Х обозначают 0+.
. Для определения коммуникации, выводимой из базиса необходимо построить цепочку. Цепочка строится следующим образом. Начиная со строк матрицы Х вычеркиваются те из них, в которых один не нулевой элемент. Подобную операцию повторяют затем по столбцам, следом по строкам и т.д.
В результате проведенной процедуры не вычеркнутыми оказываются элементы, которые состовляют цепочку. Цепочка замкнута, содержит четное число элементов и строится, начиная от 0+, безразлично в каком направлении, по ходу ладьи в шахматах.
При этом элементы, стоящие на нечетных местах помечаются минусом, а на четных - плюсом.
Среди элементов, отмеченных знаком минус выбирается минимальный элемент Q.=min{Q-}, который прибавляется или вычитается к элементам плана Х, согласно индексации. При этом коммуникация, значение которой равной нулю оказывается выведенной из базиса.
Появление в результате вычитания более одного нуля черевато потерей опорности плана. Чтобы этого не произошло, все нули, кроме одного помечают символом 0 с эпсилом (все входящие только в цепочку) и соответствующие коммуникации считаются условно существующими.
. Коррекция значения целевой функции:= L - |d|*Q
. Подсчитывают матрицу С:
а) Отмечают в матрице нули, соответствующие базисным элементам плана Х.
б) Вычеркивается строка, соответствующая введенной коммуникации. Если в процесс вычеркивания строки оказались задетыми существенные или ранее отмеченные нули мытрицы С, то вычеркивают столбцы, на которых они находятся. Если в процесс вычеркивания столбца оказались задетыми ранее отмеченные нули матрицы С, то вычеркивают строки, на которых они находятся.
в) Процесс вычеркивания продолжается до тех пор, пока есть что вычеркивать. После этого к элементам вычеркнутых строк прибавляют + |d|, а из вычеркнутых столбцов вычитают модуль -|d|. Переходим в пункт 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 |
.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 РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
Венгерский метод базируется на следующих определениях: суммарная невязка плана, суммарная невязка по строкам и столбцам. Суммарной невязкой плана называется величина
Суммарная невязка по строкам:
di = i = 1..m
Суммарная невязка по столбцам:
dj = j = 1..n
Физически невязка представляет собой удвоенную величину единицы товара, которую надо распределить поставщикам и потребителям. Структурная схема алгоритма приведена на рисунке 4.1. Величина невязки определяет наихудшее из возможных случаев итераций, которое необходимо выполнить для достижения оптимального решения. Поэтому число итераций подчиняется следующему неравенству:
Существенным нулем называется нуль матрицы С, соответствующая коммуникация которого в плане Х больше 0.
.1 Предварительный этап
В каждом столбце матрицы С отыскивается минимальный элемент, который вычитается из всех элементов данного столбца. В итоге получаем матрицу С’.
Аналогичная операция проделывается по строкам матрицы С’. В пезультате получаем матрицу С0. Для нулей матрицы С0, перемещаясь по столбцам сверху вниз и меняя столбцы слева направо строим начальный план Х0 и определяем невязку этого плана. Если невязка равна нулю, то рассчитывается целевая функция плана, в противном случае переходят к итерационной части алгоритма.
Разметка выполняется в начале итерации и сохраняется до ее конца. В ходе эквивалентных преобразований матрицы С разметка переносится. Различают символом “+” столбцы, невязки которых нулевые и существенные нули. Прочие элементы разметки добавляются в ходе итерации. Столбцы (или строки), отмеченные символом “+”, называются выделенными и образуют выделенную часть матрицы С.
.2 Поисковый этап
Необходимо найти ноль матрицы С, находящий в невыделенной части матрицы и стоящий на строке с положительной невязкой. Если в процессе поиска обнаруживается, что таких нулей нет, то прибегают к эквивалентным преобразованиям матрицы. Если ноль найдется, то строят цепочку и корректируют план.
Поиск выполняют, двигаясь по невыделенным столбцам сверху вниз. Первый найденный ноль отмечают штрихом и анализируют его невязку по строке. Если невязка положительна, то это искомый ноль. В противном случае невязка по строке равна нулю, строчку выделяют знаком “+”. Просматривают выделенную строку по элементам выделенных столбцов, если на пересечении выделенной строки и выделенного столбца оказывается ноль, то его отмечают “*”, а знак выделения над столбцом снимают, после этого столбец считается невыделенным и в нем можно осуществить поиск. Поиск заканчивается, когда найден искомый ноль, либо когда все нули матрицы находятся либо в выделенных строках, либо в выделенных столбцах.
3.3 Этап построения цепочки и коррекции плана
Цепочка незамкнута, содержит нечетное число элементов и, в принципе, может состоять из одного нуля со штрихом.
Построение цепочки происходит в следующей последовательности: от найденного нуля со штрихом по столбцу к нулю со звездой, а от нуля со звездой по строке к нулю со штрихом. Далее выбирается корректирующий элемент по правилу: невязка строки начала, невязка строки конца и элементы плана Х, которые соответствуют нулю со “*”, входящих в цепочку. Q = min {di, dj, " Х*ij О цепочка}
Как только найден такой элемент, план корректируют. Из элементов, которые соответствуют нулям со звездочкой, вычитают Q, а к элементам соответствующим нулям со штрихом прибавляют Q.
.4 Этап эквивалентных преобразований
В невыделенной части матрицы С выбирается наименьший положительный элемент, который прибавляется к элементам выделенных столбцов и вычитается из элементов невыделенных строк.
Рисунок 3.1 - Структурная схема алгоритма венгерского метода
4 ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ
.1 Переменные
Исходя из условия задачи, требуется определить минимальные транспортные затраты на перевозку груза с некоего предприятия на оптовый склад. Поэтому в качестве переменной следует взять элемент плана Хij, который является количеством груза (в килограммах) транспортированного с некоего предприятия на оптовый склад.
.2 Целевая функция
Так как стоимость (Сij) перевозки одного килограмма груза известна, то общие затраты на его перевозку составляют: Сij*Хij. Обозначив суммарные затраты через L, можно дать следующую математическую формулировку целевой функции: определить такие значения Хij, при которых значение L было бы минимальным.
.3 Ограничения
При распределении груза по пунктам потребления следует учесть, что суммарное количество груза, хранящегося на предприятии, должно быть равно суммарному количеству груза, требуемого складами.
Все вышеперечисленное приводит к построению линейной модели вида:
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;
Рассчитаем суммарную невязку плана
т.к то переходим к первой итерации.
.1.2 Первая итерация
Этап разметки
Символами “+” выделяем столбы с нулевыми невязками. Символами “-” отметим существенные нули матрицы .
|
+ |
||||
|
2.7 |
2.5 |
|||
|
C0: |
7.3 |
0 |
||
|
5.618.9 |
||||
|
8.7 |
7.4 |
Этап поиска
В невыделенной части матрицы С0 найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку “+”. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.
|
(+) |
||||
|
2.7 |
2.5+ |
|||
|
C0: |
7.3 |
*0'+ |
||
|
'5.618.9+ |
||||
|
8.7 |
'7.4 |
Этап построения цепочки
Цепочка венгерского метода состоит из нечетного числа элементов, начинается нулем в строке с положительной невязкой, проходит по столбцу до нуля, отмеченного знаком *, и заканчивается нулем, находящемся в столбце с положительной невязкой. Полученная цепочка показана в таблице:
Этап коррекции плана Х
Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент . Находим его по минимуму из невязки строки начала цепочки, из невязки столбца конца цепочки и значения элемента Xij, соответствующего 0*. =min{1420, 520, 550}=520.
|
(+) |
||||
|
2.7 |
'2.5+ |
|||
|
C0: |
7.3 |
*0'+ |
||
|
'5.618.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:т.к. то переходим ко второй итерации.
.1.3 Вторая итерация
Этап разметки
Символами “+” выделяем столбы с нулевыми невязками. Символами “-” отметим существенные нули матрицы .
|
+ |
+ |
|||
|
2.7 |
2.5 |
|||
|
C0: |
7.3 |
0 |
||
|
'5.618.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.321.6 |
||||
|
6 |
7.4 |
Этап поиска
В невыделенной части матрицы С1найденные нули отмечаем штрихом. Анализируем невязку такого нуля по строке: a=0 . Если невязка нулевая, то отмечаем строку “+”. Просматриваем выделенную строку, если в ней стоит существенный ноль, находящийся в выделенном столбце, то такой ноль отмечаем *, а выделение с этого столбца снимаем: (+). Продолжаем данную процедуру до тех пор, пока не будет найден ноль в строке с положительной невязкой - в данном случае это ноль в строке 4. Теперь переходим к этапу построения цепочки.
|
(+)(+) |
||||
|
'*2.5+ |
||||
|
C1 |
4.6 |
'*+ |
||
|
'8.321.6+ |
||||
|
6 |
'7.4 |
Этап построения цепочки
Цепочка венгерского метода состоит из нечетного числа элементов, начинается нулем в строке с положительной невязкой, проходит по столбцу до нуля, отмеченного знаком *, и заканчивается нулем, находящемся в столбце с положительной невязкой. В данном случае полученная цепочка показана в таблице:
|
(+)(+) |
||||
|
'*2.5+ |
||||
|
C1 |
4.6 |
'*+ |
||
|
'8.321.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 < D Ј 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 евро.
Поэтому уточненный диапазон D будет находиться в пределах 0 < D < 2200.
) Найдем зависимость оптимального решения и оптимального значения целевой функции от изменений компонент вектора запаса груза. Условия и результаты вычислительного эксперимента приведены в таблице 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 |
|
DL, евро |
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с.
. Зайченко Ю.П. Исследование операций [Текст] / Ю.П. Зайченко - М.: Высш. школа, 1979. - 156с.
. Карлусов В.Ю. Методические указания к практическим занятиям по дисциплине «Исследование операций и методы оптимизации» для студентов специальности 7.080401 - «Компьютеризированные системы обработки информации и управления» [Текст] / В.Ю. Карлусов, Л.П. Старобинская - Севастополь: Изд-во СевГТУ, 1997. - 26с.
. Карлусов В.Ю. Методические указания к вы-полнению лабораторных и контрольных работ для студентов дневной и заочной форм обучения специальности 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"*Form1;MyFName="";Cn,Cm;**C;**C0;**CS;Pm;*P;Zn;*Z;Dn,Dm;**D;OPrz=0;OPtr=0;Xn,Xm;**X;Nn,Nm;**N;posl;pstr;*Sheet;*Grid;*GrX;* LabelC;* LabelX;Fn;*F;Gm;*G;*GridF;L;Lstr;Cep[50][7][8];nomer=0;NKor=0;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]="Запас";
}
//При вводе в ячейку таблицы__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;(1)
{(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; //вертикально
}
}
{
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;
}__fastcall TForm1::NOpenClick(TObject *Sender)
{
if(OpenDialog1->Execute())
{
MyFName=OpenDialog1->FileName;
Open(OpenDialog1->FileName);
}
}
//---------------------------------------------------------------------------__fastcall TForm1::NSaveAsClick(TObject *Sender)
{
SaveDialog1->FileName=MyFName;
if(SaveDialog1->Execute())
{
MyFName=SaveDialog1->FileName;
Save(SaveDialog1->FileName);
}
}
//---------------------------------------------------------------------------__fastcall TForm1::NSaveClick(TObject *Sender)
{
if(MyFName!="")
Save(MyFName);
else
if(SaveDialog1->Execute())
{
MyFName=SaveDialog1->FileName;
Save(SaveDialog1->FileName);
}
}
//---------------------------------------------------------------------------__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=";
}
//---------------------------------------------------------------------------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();
}
//------------------------------------------------------------------------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=";
}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;
GridB->Left=30;
GridB->Top=405
;
GridB->Height=25;
GridB->Width=256;
GridB->ColCount=Cm;
GridB->DefaultColWidth=35;
GridB->DefaultRowHeight=24;
GridB->FixedCols=0;
GridB->FixedRows=0;
GridB->RowCount=1;
GridB->ScrollBars=ssNone;
for(int i=0;i<Cm;i++)
GridB->Cells[i][0]=FormatFloat("",P[i]/100.0);
GridF=new TStringGrid(this);
GridF->Parent=Sheet;
GridF->Left=286;
GridF->Top=34;
GridF->Height=181;
GridF->Width=16;
GridF->ColCount=1;
GridF->DefaultColWidth=12;
GridF->DefaultRowHeight=24;
GridF->FixedCols=0;
GridF->FixedRows=0;
GridF->RowCount=Cn;
GridF->ScrollBars=ssNone;
for(int i=0;i<Cn;i++)
if(F[i]==1)
GridF->Cells[0][i]="+";
TStringGrid *GridG=new TStringGrid(this);
GridG->Parent=Sheet;
GridG->Left=30;
GridG->Top=13;
GridG->Height=16;
GridG->Width=256;
GridG->ColCount=Cm;
GridG->DefaultColWidth=35;
GridG->DefaultRowHeight=12;
GridG->FixedCols=0;
GridG->FixedRows=0;
GridG->RowCount=1;
GridG->ScrollBars=ssNone;
for(int i=0;i<Cm;i++)
if(G[i]==1)
GridG->Cells[i][0]="+";
}TForm1::Predv()
{
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;
Sheet->Caption="Предв. этап";
Grid->Parent=Sheet;
Grid->Left=30;
Grid->Top=39;
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++)
{
Grid->Cells[j][i]=FormatFloat("",CS[i][j]/100.0);
}
}
LabelC->Parent=Sheet;
LabelC->Left=3;
LabelC->Top=20;
LabelC->Caption="C'";
GrX->Parent=Sheet;
GrX->Left=30;
GrX->Top=239;
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++)
GrX->Cells[j][i]=FormatFloat("",C[i][j]/100.0);
LabelX->Parent=Sheet;
LabelX->Left=3;
LabelX->Top=223;
LabelX->Caption="C0";
}TForm1::Ecviv()
{
Sheet=new TTabSheet(this);
Grid=new TStringGrid(this);
LabelC=new TLabel(this);
Sheet->Parent=this;
Sheet->PageControl=PageControl;
NKor++;
Sheet->Caption="Экв. пр. №"+IntToStr(NIter+1)+"."+IntToStr(NKor);
Grid->Parent=Sheet;
Grid->Left=30;
Grid->Top=39;
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=3;
LabelC->Top=20;
LabelC->Caption="C"+IntToStr(NKor);
}__fastcall TForm1::CepochDrawCell(TObject *Sender, int ACol, int ARow, TRect &Rect,
TGridDrawState State)
{
TStringGrid* c=(TStringGrid*) Sender;
if (c->Name!="StoimPer")
{
UnicodeString Index;
Index=PageControl->ActivePage->Name;
Index.Delete(1,1);
nomer=Index.ToInt();
Graphics::TBitmap *pict = new Graphics::TBitmap();
switch (Cep[nomer][ARow][ACol])
{
case 12:
pict->LoadFromResourceID((unsigned int)HInstance,104);
break;
case 9:
pict->LoadFromResourceID((unsigned int)HInstance,102);
break;
case 7:
pict->LoadFromResourceID((unsigned int)HInstance,106);
break;
case 6:
pict->LoadFromResourceID((unsigned int)HInstance,105);
break;
case 5:
pict->LoadFromResourceID((unsigned int)HInstance,108);
break;
case 4:
pict->LoadFromResourceID((unsigned int)HInstance,109);
break;
case 3:
pict->LoadFromResourceID((unsigned int)HInstance,101);
break;
case 2:
pict->LoadFromResourceID((unsigned int)HInstance,107);
break;
case 1:
pict->LoadFromResourceID((unsigned int)HInstance,103);
break;
}
pict->Transparent = true;
c->Canvas->Draw(Rect.left,Rect.Top,pict);
pict->Free();
}
nomer=0;
}
//---------------------------------------------------------------------------
//!!__fastcall TForm1::Timer1Timer(TObject *Sender)
{(StoimPer->ColCount == 8)
Button1->Enabled = false;Button1->Enabled = true;(StoimPer->ColCount == 4)
Button2->Enabled = false;Button2->Enabled = true;(StoimPer->RowCount == 8)
Button3->Enabled = false;Button3->Enabled = true;(StoimPer->RowCount == 4)
Button4->Enabled = false;Button4->Enabled = true;
}
//---------------------------------------------------------------------------__fastcall TForm1::Button1Click(TObject *Sender)
{>ColCount++;>ColCount++;>ColCount++;
}
//---------------------------------------------------------------------------__fastcall TForm1::Button2Click(TObject *Sender)
{>ColCount--;>ColCount--;>ColCount--;
}
//---------------------------------------------------------------------------__fastcall TForm1::Button3Click(TObject *Sender)
{>RowCount++;>RowCount++;>RowCount++;
}
//---------------------------------------------------------------------------__fastcall TForm1::Button4Click(TObject *Sender)
{>RowCount--;>RowCount--;>RowCount--;
}
//---------------------------------------------------------------------------__fastcall TForm1::NAboutClick(TObject *Sender)
{(L"Костенко И-23 Венгерский метод.", mtConfirmation,
TMsgDlgButtons() << mbOK, 0);
}
//---------------------------------------------------------------------------