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

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

Содержание

Введение

1. Транспортная задача: постановка и математическая модель

2. Нахождение первоначального распределения

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

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

2.3 Метод аппроксимации Фогеля

3. Решение открытой транспортной задачи

4. Тестирование программы

Заключение

Список литературы

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

Введение

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

Остановимся на некоторых характерных особенностях транспортных задач. Прежде всего -- проблема оптимальности. Что значит транспорт работает хорошо? Один из основных показателей работы транспорта -- грузооборот -- измеряется в тонно-километрах. Получается, если транспортная организация «выполнила» много тонно-километров, то она работала хорошо. А ведь оптимальная система перевозок, несомненно, приносящая пользу государству, ведет к сокращению этого показателя и тем самым ухудшает показатели работы организации. Можно, конечно, измерять качество работы по затратам при существующих тарифах и пытаться, планируя перевозки, минимизировать эти затраты. Но тогда сразу же возникает вопрос о правильном, научно обоснованном исчислении тарифов.

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

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

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

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

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

Изучить суть и общую математическую постановку транспортной задачи.

Изучить и сравнить методы нахождения первоначального распределения.

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

1. Транспортная задача: постановка и математическая модель

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

Пусть имеются пункты производства A1, А2, ..,, Аn с объемами производства в единицу времени, равными соответственно а1, а2, ..., аn, и пункты потребления B1, В2, ..., Вm с объемами потребления, равными b1, Ь2, ..., bm соответственно. Будем предполагать, что производство и потребление сбалансированы -- сумма объемов производства равна сумме объемов потребления, т. е.

Предполагаются известными величины Сij -- затраты по перевозке единицы продукта из i-го пункта производства в j-й пункт потребления. Они могут быть выражены в стоимостной (денежной) форме или в натуре (например, в тонно-километрах). Требуется найти такой план перевозок, при котором были бы удовлетворены потребности в пунктах B1, В2, ..., Вm и при этом суммарные затраты на перевозку были бы минимальны.

Обозначая через хij количество продукта, перевозимое из i-гo пункта производства в j-й пункт потребления, приходим к следующей математической формулировке задачи.

Найти минимум

(суммарные затраты на транспортировку) при условиях

, j 1, …,n (1)

(в каждый пункт потребления завозится требуемое количество продукта);

, i 1, …, m (2)

(из каждого пункта производства полностью вывозится произведенный продукт);

xij>0, i = 1,2,..., m; j = 1,2,..., n (3)

(перевозимый объем продукта не может быть отрицательным).

Всякий набор величин xij (j 1, …,n; i 1, …, m), удовлетворяющих условиям (1 - 3), называется допустимым планом перевозок. План, для которого суммарные затраты достигают минимума, называется оптимальным. Поскольку транспортная задача является частным случаем задачи линейного программирования, для нее справедлив приведенный ранее критерий оптимальности плана. Используя терминологию и особенности транспортной задачи, этот критерий можно сформулировать таким образом: допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту производства и потребления можно сопоставить величину, характеризующую уровень оценки продукции в нем так, что множество этих потенциалов удовлетворяет следующим условиям:

(1) разность оценок пунктов потребления и производства, между которыми запланированы перевозки, равна затратам по транспортировке единицы продукта между этими пунктами;

(2) аналогичные разности для всех остальных пар пунктов не превосходят затрат по транспортировке.

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Таблица №1

Поставщик	Потребитель	Запасы
	В1	…	Bj	…	Bn	А1
A1	C11 X11	…	C1j X1j	…	C1n X1n	a1
…	…	…	…	…	…	…
Ai	Ci1 Xi1	…	Cij Xij	…	Cin Xin	ai
…	…	…	…	…	…	…
Am	Cm1 Xm1	…	Cmj Xmj	…	Cmn Xmn	am
Потребности	b1	…	bj	…	bn

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы -- пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем -- значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xij=0), называют свободными, а ненулевые -- занятыми (xij >0).

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

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

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

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

2. Нахождение первоначального распределения

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

Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

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

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

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей -- bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi(0) = аi, bj(0) = bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xij=min{ аi(q), bj(q).)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

аi(q+1) = аi(q)- xij , bj(q+1).= bj(q).- xij

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1) =0 или , bj(q+1).= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1).= 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей (1), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m + n -1, поэтому всегда останутся свободными (нулевыми) m*n - (m + n -1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)= bj(q).). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

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

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

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

Сущность метода состоит в следующем. Просматриваются тарифы транспортной таблицы, и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m + n - 1 загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 - « нуль-загрузка», условно считая такую клетку занятой, однако число 0 записывается в такие клетки, которые не образуют циклов с ранее занятыми клетками.

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

2.3 Метод аппроксимации Фогеля

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

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

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

3. Решение открытой транспортной задачи

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

(где i=1,...,m; j=1,...,n) (4)

Это классическая транспортная задача, иначе называемая, закрытой транспортной задачей. Встречаются такие варианты транспортной задачи, где условие (4) нарушено. В этих случаях говорят об открытой транспортной задаче.

Баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (где i=1,...,m ; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы (где i=1,...,m; j=1,...,n);

Условимся первый случай называть “Транспортной задачей с избытком запасов“, а второй -- “Транспортной задачей с избытком заявок”.

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

В пунктах A1, A2, ... , Am имеются запасы груза a1, a2, ... , am; пункты B1, B2, ... , Bn подали заявки b1, b2, ... , bn, причём

аi > bj ( где i=1..m ; j=1..n ).

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

Поставленная задача может быть решена, например, обычным симплекс-методом. Однако задачу можно решить проще, если искусственным приёмом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

(где i=1,...,m; j=1,...,n) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равным нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную закрытую транспортную задачу.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной закрытой транспортной задаче, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

транспортный линейный программирование фогель

4. Тестирование программы

Имеется m пунктов отправления А1, А2 , ..., Аm , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... , аm единиц. Имеется n пунктов назначения В1 , В2 , ... , Вn подавшие заявки соответственно на b1 , b2 , ... , bn единиц груза. Известны стоимости Сi,j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы.

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

Данная программа предназначена для нахождения оптимального плана транспортной задачи. При этом рассматриваются три различных метода нахождения опорного плана поставок:

Метод Северо-Западного угла.

Метод минимальных затрат.

Метод аппроксимаций Фогеля.

Рассмотрим решение стандартной задачи.

При запуске программы на экране появляется следующее окно:



Пользователь может либо вручную ввести необходимые данные либо загрузить сохраненные ранее (кнопка «Загрузить»). После загрузки данных пользователь может внести свои изменения в них.

Пользователю предоставляется возможность сохранить исходные данные в файл (кнопка «Сохранить»).

В случае если пользователю необходимо изменить исходные данные, то можно очистить все поля (кнопка «Очистить»).

После введения данных пользователь должен выбрать метод построения опорного плана и нажать на кнопку «Решить» под нужным методом.

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



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

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

Заключение

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

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

Таким образом, важность решения данной задачи для экономики несомненна.

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

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

Программа имеет удобный и интуитивно понятный интерфейс.

Список литературы

1. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышэйшая школа, 2001г.

2. Акулич И.Л. «Математическое программирование в примерах и задачах», Высшая школа, 1984г.

3. Ермаков В.И. “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.

4. Канторович Л.В., Горстко А.Б. «Математическое оптимальное программирование в экономике», Знание, 1968г.

5. Канторович Л.В., Горстко А.Б. «Оптимальные решения в экономике», Наука, 1972г.

6. Конюховский П.В. «Математические методы исследования операций в экономике», Питер, 2000г.

7. Кузнецов А.В., Новикова Г.И., Холод И.И. - «Сборник задач по математическому программированию». Минск, Высшая школа, 1985г.

8. Справочная система Delphi 7.

9. Ресурсы сети Internet.

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, TransportProblem;

type

TForm1 = class(TForm)

GroupBox1: TGroupBox;

Label1: TLabel;

Label2: TLabel;

Edit1: TEdit;

Edit2: TEdit;

StringGrid1: TStringGrid;

Button3: TButton;

Button4: TButton;

Button5: TButton;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

Button2: TButton;

Button6: TButton;

Button1: TButton;

Button7: TButton;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Button8: TButton;

procedure EditChange(Sender: TObject);

procedure EditExit(Sender: TObject);

procedure KeyPressed(Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure StringGrid1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Button3Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure Button2Click(Sender: TObject);

procedure Button6Click(Sender: TObject);

procedure StringGrid1KeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure Button1Click(Sender: TObject);

procedure Button7Click(Sender: TObject);

procedure Load;

procedure SetProblem;

end;

var

Form1: TForm1;

TempC, TempP: TArray;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.Load;

var

F: TextFile;

i, j: Integer;

S: String;

begin

AssignFile(F, OpenDialog1.FileName);

{$I-}

Reset(F);

{$I+}

if IOResult <> 0 then begin

MessageDlg('Ошибка чтения файла', mtError, [mbOk], 0);

Exit;

end;

Readln(F, S);

Edit1.Text:= S;

Edit1.OnExit(Edit1);

Readln(F, S);

Edit2.Text:= S;

Edit2.OnExit(Edit2);

for i:= 0 to StringGrid1.RowCount - 1 do begin

for j:= 0 to StringGrid1.ColCount - 1 do begin

Readln(F, S);

StringGrid1.Cells[j, i]:= S;

end;

end;

end;

procedure TForm1.EditChange(Sender: TObject);

begin

if (Sender as TEdit).Text = '' then

Exit;

try

case StrToInt((Sender as TEdit).Text[Length((Sender as TEdit).Text)]) of

0..9: Exit;

end;

except

(Sender as TEdit).Text:= Copy((Sender as TEdit).Text, 1, Length((Sender as TEdit).Text) - 1);

MessageDlg('Разрешается вводить только цифры', mtError, [mbOk], 0);

Exit;

end;

end;

procedure TForm1.EditExit(Sender: TObject);

begin

if (Sender as TEdit).Text = '' then

Exit;

if (Sender as TEdit).Tag = 0 then

StringGrid1.RowCount:= StrToInt((Sender as TEdit).Text) + 1

else

StringGrid1.ColCount:= StrToInt((Sender as TEdit).Text) + 1;

end;

procedure TForm1.KeyPressed(Sender: TObject; var Key: Word;

Shift: TShiftState);

begin

if Key = 13 then

EditExit(Sender);

end;

procedure TForm1.StringGrid1MouseDown(Sender: TObject;

Button: TMouseButton; Shift: TShiftState; X, Y: Integer);

var

Col, Row: Integer;

begin

StringGrid1.MouseToCell(X, Y, Col, Row);

if (Col = 0) and (Row = 0) then

Exit;

if Col = 0 then begin

StringGrid1.Cells[0, Row]:= InputBox('Мощность', 'Введите мощность', '');

Exit

end;

if Row = 0 then

StringGrid1.Cells[Col, 0]:= InputBox('Мощность', 'Введите мощность', '');

end;

procedure TForm1.SetProblem;

var

i, j: Integer;

begin

SetLength(Customers, StringGrid1.ColCount - 1);

for i:= 1 to StringGrid1.ColCount - 1 do

Customers[i - 1]:= StrToInt(StringGrid1.Cells[i, 0]);

SetLength(Postavshiki, StringGrid1.RowCount - 1);

for j:= 1 to StringGrid1.RowCount - 1 do

Postavshiki[j - 1]:= StrToInt(StringGrid1.Cells[0, j]);

SetLength(Matr, Length(Postavshiki), Length(Customers));

for i:= 1 to StringGrid1.RowCount - 1 do begin

for j:= 1 to StringGrid1.ColCount - 1 do begin

Matr[i - 1, j - 1]:= StrToInt(StringGrid1.Cells[j, i]);

end;

end;

end;

procedure TForm1.Button5Click(Sender: TObject);

var

F: TextFile;

i, j: Integer;

begin

if SaveDialog1.Execute then begin

AssignFile(F, SaveDialog1.FileName);

Rewrite(F);

Writeln(F, Edit1.Text);

Writeln(F, Edit2.Text);

for i:= 0 to StringGrid1.RowCount - 1 do begin

for j:= 0 to StringGrid1.ColCount - 1 do begin

Writeln(F, StringGrid1.Cells[j, i]);

end;

end;

CloseFile(F);

end;

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

if OpenDialog1.Execute then begin

Load;

end;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

Application.Terminate;

end;

procedure TForm1.Button2Click(Sender: TObject);

var

i: Integer;

begin

for i:=0 to StringGrid1.ColCount - 1 do

StringGrid1.Cols[i].Clear;

end;

procedure TForm1.Button6Click(Sender: TObject);

begin

Form1.Close;

end;

procedure TForm1.StringGrid1KeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

begin

if Key <> 13 then

Exit;

if StringGrid1.Col < StringGrid1.ColCount - 1 then

StringGrid1.Col:= StringGrid1.Col + 1

else

if StringGrid1.Row < StringGrid1.RowCount - 1 then begin

StringGrid1.Row:= StringGrid1.Row + 1;

StringGrid1.Col:= 1;

end;

end;

procedure TForm1.Button3Click(Sender: TObject);

var

i: Integer;

//TempC, TempP: TArray;

begin

SetProblem;

SetLength(TempC, Length(Customers));

SetLength(TempP, Length(Postavshiki));

for i:= 0 to Length(TempC) do

TempC[i]:= Customers[i];

for i:= 0 to Length(TempP) do

TempP[i]:= Postavshiki[i];

Solve(NorthWestCorner);

//Solve(MinCost);

//Solve(Fogel);

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i: Integer;

//TempC, TempP: TArray;

begin

SetProblem;

SetLength(TempC, Length(Customers));

SetLength(TempP, Length(Postavshiki));

for i:= 0 to Length(TempC) do

TempC[i]:= Customers[i];

for i:= 0 to Length(TempP) do

TempP[i]:= Postavshiki[i];

//Solve(NorthWestCorner);

Solve(MinCost);

//Solve(Fogel);

end;

procedure TForm1.Button7Click(Sender: TObject);

var

i: Integer;

//TempC, TempP: TArray;

begin

SetProblem;

SetLength(TempC, Length(Customers));

SetLength(TempP, Length(Postavshiki));

for i:= 0 to Length(TempC) do

TempC[i]:= Customers[i];

for i:= 0 to Length(TempP) do

TempP[i]:= Postavshiki[i];

//Solve(NorthWestCorner);

//Solve(MinCost);

Solve(Fogel);

end;

end

unit TransportProblem;

interface

uses

Math, Dialogs, Windows, SysUtils, ComCtrls;

type

TArray = array of Integer;

TMatr = array of array of Integer;

var

z: Integer;

Matr: TMatr;

Postavshiki, Customers: TArray;

Plan: TMatr;

procedure Solve(NorthWestCorner: TMatr);

function NorthWestCorner: TMatr;

function MinCost: TMatr;

function Fogel: TMatr;

implementation

uses Types, Unit1, Unit2;

function Fun(AMatr, APlan: TMatr): integer;

var

i, j, F: Integer;

begin

F:=0;

for i:= 0 to Length(APlan) - 1 do

for j:= 0 to Length(APlan[0]) - 1 do

if APlan[i, j] <> -1 then

F:= F + APlan[i, j] * AMatr[i, j];

Fun:=F;

end;

function NorthWestCorner: TMatr;

var

i, j, k, m: Integer;

begin

SetLength(Result, Length(Postavshiki), Length(Customers));

for i:= 0 to Length(Matr) - 1 do begin

for j:= 0 to Length(Matr[0]) - 1 do begin

if Result[i, j] = 0 then begin

m:= Min(Customers[j], Postavshiki[i]);

Result[i, j]:= m;

Customers[j]:= Customers[j] - m;

Postavshiki[i]:= Postavshiki[i] - m;

if Customers[j] = 0 then begin

for k:= i + 1 to Length(Postavshiki) - 1 do begin

Result[k, j]:= -1;

end;

end;

if Postavshiki[i] = 0 then begin

for k:= j + 1 to Length(Customers) - 1 do begin

Result[i, k]:= -1;

end;

end;

end;

end;

end;

end;

function MinCost: TMatr;

function AllEmpty: Boolean;

var

i: Integer;

begin

for i:= 0 to Length(Customers) - 1 do

if Customers[i] <> 0 then begin

Result:= False;

Exit;

end;

for i:= 0 to Length(Postavshiki) - 1 do

if Postavshiki[i] <> 0 then begin

Result:= False;

Exit;

end;

Result:= True;

end;

var

i, j,

MinI, MinJ,

m: Integer;

begin

SetLength(Result, Length(Postavshiki), Length(Customers));

for i:= 0 to Length(Result) - 1 do

for j:= 0 to Length(Result[0]) - 1 do

Result[i, j]:= -1;

while not AllEmpty do begin

MinI:= -1;

MinJ:= -1;

for i:= 0 to Length(Matr) - 1 do begin

for j:= 0 to Length(Matr[0]) - 1 do begin

if (Postavshiki[i] = 0) or (Customers[j] = 0) then

Continue;

if MinI = -1 then begin

MinI:= i;

MinJ:= j;

end;

if Matr[MinI, MinJ] > Matr[i, j] then begin

MinI:= i;

MinJ:= j;

end;

end;

end;

m:= Min(Customers[MinJ], Postavshiki[MinI]);

Result[MinI, MinJ]:= m;

Customers[MinJ]:= Customers[MinJ] - m;

Postavshiki[MinI]:= Postavshiki[MinI] - m;

end;

end;

function Fogel: TMatr;

function AllEmpty: Boolean;

var

i: Integer;

begin

for i:= 0 to Length(Customers) - 1 do

if Customers[i] <> 0 then begin

Result:= False;

Exit;

end;

for i:= 0 to Length(Postavshiki) - 1 do

if Postavshiki[i] <> 0 then begin

Result:= False;

Exit;

end;

Result:= True;

end;

const

MAX = High(Integer);

MIX = Low(Integer);

var

i, j,

fMin, sMin, SubRowMax, SubColMax, m ,imax, jmax: Integer;

SubRow, SubCol: TMatr;

begin

SetLength(Result, Length(Postavshiki), Length(Customers));

for i:= 0 to Length(Result) - 1 do

for j:= 0 to Length(Result[0]) - 1 do

Result[i, j]:= -1;

while not AllEmpty do begin

// Цикл по строкам

for i:= 0 to Length(Matr) - 1 do begin

fMin:=MAX;

for j:= 0 to Length(Matr[0]) - 1 do begin

if (Postavshiki[i] = 0) or (Customers[j] = 0) then

Continue;

SetLength(SubRow, Length(Postavshiki), 2);

if Matr[i,j] < fMin then begin

fMin:=Matr[i,j];

SubRow[i,1]:=j;

end;

end;

sMin:=MAX;

for j:= 0 to Length(Matr[0]) - 1 do begin

if (Postavshiki[i] = 0) or (Customers[j] = 0) then

Continue;

if j <> SubRow[i,1] then begin

if Matr[i,j] < sMin then

sMin:=Matr[i,j];

end;

end; // Вычисляем разность между 2мя наименьшими тарифами

SubRow[i,0]:=sMin-fMin;

end;

// цикл по столбцам

for j:= 0 to Length(Matr[0]) - 1 do begin

fMin:=MAX;

for i:= 0 to Length(Matr) - 1 do begin

if (Postavshiki[i] = 0) or (Customers[j] = 0) then

Continue;

SetLength(SubCol, Length(Customers), 2);

if Matr[i,j] < fMin then begin

fMin:=Matr[i,j];

SubCol[j,1]:=i;

end;

end;

sMin:=MAX;

for i:= 0 to Length(Matr) - 1 do begin

if (Postavshiki[i] = 0) or (Customers[j] = 0) then

Continue;

if i <> SubCol[j,1] then begin

if Matr[i,j] < sMin then

sMin:=Matr[i,j];

end;

end; // Вычисляем разность между 2мя наименьшими тарифами

SubCol[j,0]:=sMin-fMin;

end;

// отыскиваем максимальное значение в получившемся столбце

SubRowMax:=MIX;

for i:= 0 to Length(Matr) - 1 do begin

if SubRow[i,0] > SubRowMax then begin

SubRowMax:=SubRow[i,0];

imax:=i;

end;

end;

// отыскиваем максимальное значение в получившемся строке

SubColMax:=MIX;

for j:= 0 to Length(Matr[0]) - 1 do begin

if SubCol[j,0] > SubColMax then begin

SubColMax:=SubCol[j,0];

jmax:=j;

end;

end;

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

if SubRowMax > SubColMax then begin

m:= Min(Customers[SubRow[imax,1]], Postavshiki[imax]);

Result[imax, SubRow[imax,1]]:= m;

Customers[SubRow[imax,1]]:= Customers[SubRow[imax,1]] - m;

Postavshiki[imax]:= Postavshiki[imax] - m;

end

else begin

m:= Min(Customers[jmax], Postavshiki[SubCol[jmax,1]]);

Result[SubCol[jmax,1], jmax]:= m;

Customers[jmax]:= Customers[jmax] - m;

Postavshiki[SubCol[jmax,1]]:= Postavshiki[SubCol[jmax,1]] - m;

end;

end;

end;

function RightPlan(APlan: TMatr): Boolean;

var

i, j, c: Integer;

begin

if Length(APlan) = 0 then begin

Result:= False;

Exit;

end;

c:= 0;

for i:= 0 to Length(APlan) - 1 do

for j:= 0 to Length(APlan[0]) - 1 do

if APlan[i, j] <> -1 then

inc(c);

Result:= Length(APlan) + Length(APlan[0]) - 1 = c;

end;

function PotencialMethod(AMatr, APlan: TMatr): TMatr;

function NewPlan(AMatr, APlan: TMatr; var OptPlan: Boolean): TMatr;

type

TPoints = array of TPoint;

function FindCicl(APlan: TMatr; AI, AJ: Integer): TPoints;

var

i, j, k, c, m: Integer;

Plan: TMatr;

begin

SetLength(Plan, Length(APlan), Length(APlan[0]));

for i:= 0 to Length(APlan) - 1 do begin

for j:= 0 to Length(APlan[0]) - 1 do begin

Plan[i, j]:= APlan[i, j];

end;

end;

SetLength(Result, 1);

Result[0].X:= AI;

Result[0].Y:= AJ;

Plan[AI, AJ]:= 0;

repeat

m:= 0;

for i:= 0 to Length(Plan) - 1 do begin

for j:= 0 to Length(Plan[0]) - 1 do begin

if Plan[i, j] = -1 then

Continue;

c:= 0;

for k:= 0 to Length(Plan) - 1 do

if Plan[k, j] <> -1 then

inc(c);

if c < 2 then begin

inc(m);

Plan[i, j]:= -1;

Continue;

end;

c:= 0;

for k:= 0 to Length(Plan[0]) - 1 do

if Plan[i, k] <> -1 then

inc(c);

if c < 2 then begin

inc(m);

Plan[i, j]:= -1;

end;

end;

end;

until m = 0;

repeat

if Length(Result) mod 2 = 0 then begin

for k:= 0 to Length(Plan[0]) - 1 do begin

if (Plan[Result[Length(Result) - 1].X, k] <> -1) and

(k <> Result[Length(Result) - 1].Y) then begin

SetLength(Result, Length(Result) + 1);

Result[Length(Result) - 1].Y:= k;

Result[Length(Result) - 1].X:= Result[Length(Result) - 2].X;

Break;

end;

end;

end

else begin

for k:= 0 to Length(Plan) - 1 do begin

if (Plan[k, Result[Length(Result) - 1].Y] <> -1) and

(k <> Result[Length(Result) - 1].X) then begin

SetLength(Result, Length(Result) + 1);

Result[Length(Result) - 1].X:= k;

Result[Length(Result) - 1].Y:= Result[Length(Result) - 2].Y;

Break;

end;

end;

end;

until (Result[Length(Result) - 1].X = AI);

end;

const

MAX = High(Integer);

var

RowPot, ColPot: TArray;

NewMatr: TMatr;

MinI, MinJ: Integer;

Cicl: TPoints;

Min: Integer;

function AllFull: Boolean;

var

i: Integer;

begin

for i:= 0 to Length(APlan) - 1 do begin

Result:= RowPot[i] <> MAX;

if not Result then begin

Exit;

end;

end;

for i:= 0 to Length(APlan[0]) - 1 do begin

Result:= ColPot[i] <> MAX;

if not Result then begin

Exit;

end;

end;

Result:= True;

end;

var

i, j, c: Integer;

begin

c:=0;

SetLength(RowPot, Length(APlan));

SetLength(ColPot, Length(APlan[0]));

for i:= 0 to Length(APlan) - 1 do

RowPot[i]:= MAX;

ColPot[0]:= 0;

for i:= 1 to Length(APlan[0]) - 1 do

ColPot[i]:= MAX;

repeat

for i:= 0 to Length(APlan) - 1 do begin

for j:= 0 to Length(APlan[0]) - 1 do begin

if APlan[i, j] <> -1 then begin

if (RowPot[i] = MAX) and (ColPot[j] = MAX) then

Continue;

if RowPot[i] = Max then

RowPot[i]:= -(Matr[i, j] + ColPot[j])

else

ColPot[j]:= -(Matr[i, j] + RowPot[i]);

end;

end;

end;

until AllFull;

MinI:= 0;

MinJ:= 0;

SetLength(NewMatr, Length(Matr), Length(Matr[0]));

for i:= 0 to Length(AMatr) - 1 do begin

for j:= 0 to Length(AMatr[0]) - 1 do begin

NewMatr[i, j]:= Matr[i, j] + RowPot[i] + ColPot[j];

if NewMatr[i, j] < NewMatr[MinI, MinJ] then begin

MinI:= i;

MinJ:= j;

end;

end;

end;

Form2.AddSheet1('Итерация' + IntToStr(c) , NewMatr);

if NewMatr[MinI, MinJ] >= 0 then begin

OptPlan:= True;

Exit;

end

else

OptPlan:= False;

Cicl:= FindCicl(APlan, MinI, MinJ);

i:= 3;

MinI:= Cicl[1].X;

MinJ:= Cicl[1].Y;

Min:= APlan[MinI, MinJ];

while i < Length(Cicl) do begin

if Min > APlan[Cicl[i].X, Cicl[i].Y] then begin

MinI:= Cicl[i].X;

MinJ:= Cicl[i].Y;

Min:= APlan[MinI, MinJ];

end;

inc(i, 2);

end;

for i:= 0 to Length(Cicl) - 1 do begin

if i mod 2 = 0 then

if APlan[Cicl[i].X, Cicl[i].Y] = -1 then

inc(APlan[Cicl[i].X, Cicl[i].Y], Min + 1)

else

inc(APlan[Cicl[i].X, Cicl[i].Y], Min)

else begin

dec(APlan[Cicl[i].X, Cicl[i].Y], Min);

end;

end;

APlan[MinI, MinJ]:= -1;

end;

var

OptPlan: Boolean;

c,F: Integer;

begin

c:= 0;

repeat

inc(c);

NewPlan(AMatr, APlan, OptPlan);

F:=Fun(AMatr, APlan);

Form2.AddSheet('Итерация' + IntToStr(c)+ ' F = '+ IntToStr(F), APlan);

until (OptPlan);

Result:= APlan;

end;

procedure Solve(NorthWestCorner: TMatr);

var

i, j, F: Integer;

//TempC, TempP: TArray;

begin

Plan:= NorthWestCorner;

if not RightPlan(Plan) then begin

MessageDlg ('План не удовлетворяет условию пост + потр - 1. Решаем задачу другим методом ', mtError, [mbOk], 0);

for i:= 0 to Length(TempC) do

Customers[i]:= TempC[i];

for i:= 0 to Length(TempP) do

Postavshiki[i]:= TempP[i];

Plan:= NorthWestCorner;

end;

if not RightPlan(Plan) then begin

MessageDlg ('План не удовлетворяет условию пост + потр - 1. Решаем задачу другим методом '', mtError, [mbOk], 0);

for i:= 0 to Length(TempC) do

Customers[i]:= TempC[i];

for i:= 0 to Length(TempP) do

Postavshiki[i]:= TempP[i];

Plan:= MinCost;

end;

if not RightPlan(Plan) then begin

MessageDlg('План не удовлетворяет условию пост + потр - 1. Решаем задачу другим методом ', mtError, [mbOk], 0);

for i:= 0 to Length(TempC) do

Customers[i]:= TempC[i];

for i:= 0 to Length(TempP) do

Postavshiki[i]:= TempP[i];

Plan:= Fogel;

end;

F:=Fun(Matr, Plan);

Form2.AddSheet('Опорный план F = '+ IntTostr(F), Plan);

Plan:= PotencialMethod(Matr, Plan);

F:=Fun(Matr, Plan);

Form2.PageControl1.Pages[Form2.PageControl1.PageCount - 1].Caption:= 'Решение F = '+IntToStr(F);

for i:= 0 to Form2.PageControl2.PageCount - 1 do begin

Form2.PageControl2.Pages[i].Caption:= 'Итерация ' + IntToStr(i);

end;

Form1.Enabled:= True;

Form2.StringGrid1.RowCount:= Form1.StringGrid1.RowCount+1;

Form2.StringGrid1.ColCount:= Form1.StringGrid1.ColCount+1;

for i:= 0 to Form1.StringGrid1.RowCount do begin

for j:= 0 to Form1.StringGrid1.ColCount do begin

Form2.StringGrid1.Cells[i, j]:= Form1.StringGrid1.Cells[i, j];

end;

end;

Form2.Show;

end;

end.

unit Unit2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ComCtrls, Grids, TransportProblem, Unit1, StdCtrls, ShellAPI;

type

TForm2 = class(TForm)

PageControl1: TPageControl;

PageControl2: TPageControl;

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

StringGrid1: TStringGrid;

Label3: TLabel;

procedure Button1Click(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

private

{ Private declarations }

public

{ Public declarations }

procedure AddSheet(Name: String; Plan: TMatr);

procedure AddSheet1(Name: String; Matr: TMatr);

end;

var

Form2: TForm2;

implementation

{$R *.dfm}

procedure TForm2.AddSheet(Name: String; Plan: TMatr);

var

Page1: TTabSheet;

i, j: Integer;

begin

Page1:= TTabSheet.Create(PageControl1);

Page1.Caption:= Name;

Page1.PageControl:= PageControl1;

with TStringGrid.Create(Page1) do begin

Align:= alClient;

Parent:= Page1;

FixedCols:= 0;

FixedRows:= 0;

RowCount:= Length(Plan);

ColCount:= Length(Plan[0]);

DefaultColWidth:= 32;

DefaultRowHeight:= 23;

for i:= 0 to RowCount - 1 do

for j:= 0 to ColCount - 1 do

if Plan[i, j] = -1 then

Cells[j, i]:= '0'

else

Cells[j, i]:= IntToStr(Plan[i, j]);

end;

end;

procedure TForm2.AddSheet1(Name: String; Matr: TMatr);

var

Page1: TTabSheet;

i, j: Integer;

begin

Page1:= TTabSheet.Create(PageControl2);

Page1.Caption:= Name;

Page1.PageControl:= PageControl2;

with TStringGrid.Create(Page1) do begin

Align:= alClient;

Parent:= Page1;

FixedCols:= 0;

FixedRows:= 0;

RowCount:= Length(Matr);

ColCount:= Length(Matr[0]);

DefaultColWidth:= 32;

DefaultRowHeight:= 23;

for i:= 0 to RowCount - 1 do

for j:= 0 to ColCount - 1 do

Cells[j, i]:= IntToStr(Matr[i, j]);

end;

end;

procedure TForm2.Button1Click(Sender: TObject);

begin

Form2.Close;

end;

procedure TForm2.FormClose(Sender: TObject; var Action: TCloseAction);

begin

ShellExecute(0, 'open', PChar(Application.ExeName), nil,

nil,

SW_SHOWNOACTIVATE);

Halt;

end;

end.

program Project1;

uses

Forms,

Unit1 in 'Unit1.pas' {Form1},

TransportProblem in 'TransportProblem.pas',

Unit2 in 'Unit2.pas' {Form2};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm1, Form1);

Application.CreateForm(TForm2, Form2);

if ParamCount > 0 then begin

Form1.OpenDialog1.FileName:= ParamStr(1);

Form1.Load;

end;

Application.Run;

end.

Программа написана и отлажена в среде Borland Delphi 7.

Размещено на Allbest.ru

...