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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Транспортная задача: сравнение методов нахождения первоначального распределения

Информация:

Тип работы: курсовая работа. Добавлен: 05.09.2012. Сдан: 2011. Страниц: 24. Уникальность по antiplagiat.ru: < 30%

Описание (план):


     Содержание 

 
 

Введение

     В современной экономике большую  роль играют проблемы, связанные с  транспортировкой грузов. Они обусловлены удаленностью источников сырья от пунктов производства, пунктов производства от пунктов потребления и другими объективными факторами. Затраты на перевозки всех видов грузов всеми видами транспорта в целом по стране составляют более 20 млрд. руб. Столь большой объем затрат дает основание полагать, что при правильном решении вопросов, связанных с использованием транспорта, особенно учитывая, с одной стороны, разнообразие его видов, богатство природных условии, сложность схем перевозок, дальность расстояний, а с другой — дефицитность транспортных средств и их загруженность, можно ожидать существенного сокращения этих затрат. Такое предположение подтверждается и значительным уже опытом применения математических методов планирования на транспорте.
     Остановимся на некоторых характерных особенностях транспортных задач. Прежде всего — проблема оптимальности. Что значит транспорт работает хорошо? Один из основных показателей работы транспорта — грузооборот — измеряется в тонно-километрах. Получается, если транспортная организация «выполнила» много тонно-километров, то она работала хорошо. А ведь оптимальная система перевозок, несомненно, приносящая пользу государству, ведет к сокращению этого показателя и тем самым ухудшает показатели работы организации. Можно, конечно, измерять качество работы по затратам при существующих тарифах и пытаться, планируя перевозки, минимизировать эти затраты. Но тогда сразу же возникает вопрос о правильном, научно обоснованном исчислении тарифов.
     Очень эффективно, например, было бы оптимально планировать совместную деятельность сразу нескольких видов транспорта. Но возникающая при этом математическая задача будет иметь весьма большой размер, что, естественно, затруднит поиск оптимального решения, и без того осложненного тем, что такая задача «принадлежит разным ведомствам». В общем здесь есть еще немало вопросов, ждущих своего решения с помощью точных математических методов.
     Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного  типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
     Таким образом, тема курсовой работы является актуальной.
     Целью выполнения курсовой работы является разработка приложения для решения  транспортной задачи линейного программирования и сравнения методов нахождения первоначального распределения. Достижение указанной цели потребовало постановки и решения следующих задач:
    Изучить суть и общую математическую постановку транспортной задачи.
    Изучить и сравнить методы нахождения первоначального распределения.
    Разработать приложение, которое позволяло бы решать вышеуказанные задачи.
 

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

 
      Построим математическую модель, описывающую одну довольно простую, но типичную ситуацию. Речь будет идти о рациональной перевозке некоторого однородного (одного и того же назначения и качества) продукта от производителей к потребителям. В этом случае каждому потребителю безразлично, откуда, из каких пунктов производства будет поступать этот продукт, лишь бы он поступал в нужном объеме. Однако от того, насколько рациональным окажется прикрепление пунктов потребления к пунктам производства, существенно зависит объем транспортной работы. В связи с этим, естественно, возникает вопрос о наиболее рациональном прикреплении производителей к потребителям (и наоборот), о правильном направлении перевозок груза, при котором потребности удовлетворяются, а затраты на транспортировку минимальны.
      Пусть имеются пункты производства 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).
     Математическая  модель транспортной задачи получает все большее и большее практическое применение. В настоящее время  в Государственном комитете по материально-техническому снабжению на основе методики, разработанной по этой модели, произведено прикрепление и составлены рациональные планы перевозок для десятков видов продукции химической промышленности, промышленности строительных материалов и продукции других отраслей хозяйства, что дает миллионы рублей экономии в затратах на железнодорожный транспорт.
     Необходимо  подчеркнуть, что постановка транспортной задачи в наибольшей степени характерна именно для социалистической экономики. Критерием оптимальности в этой задаче является минимум суммарных затрат по перевозке груза, т. е. народнохозяйственный эффект, а не выгода отдельных грузополучателей. Ясно, что не только цель, но и сама возможность широкой реализации решения, требующая переформирования всех грузопотоков в масштабах страны, осуществима лишь в условиях научно планируемой экономики. Причем решение транспортной задачи обеспечивает условия для установления экономически обоснованной, дифференцированной системы цен (или транспортных накидок), делающей рациональные прикрепления экономически выгодными и взаимоувязанными для всех производителей и потребителей данной продукции. Такие цены способствуют реализации оптимальных решений в хозяйственной деятельности.
     Очень важно знать, что транспортная задача используется не только для решения транспортных проблем. Ее первое применение действительно осуществлялось на примере этой отрасли народного хозяйства, но вообще математическая модель транспортной задачи может описывать самые разные ситуации, очень далекие от перевозок.
    Рассмотрим  сначала  решение  закрытой  транспортной  задачи,  т.е. когда сумма всех  заявок  ровна  сумме  всех  запасов.
 

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

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

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

     При составлении первоначального опорного плана методом северо-западного  угла стоимость перевозки единицы  не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ.
     По  аналогии с другими задачами линейного  программирования решение транспортной задачи начинается с построения допустимого  базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге 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. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

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

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

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

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

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

    В  предыдущих  случаях  мы  рассматривали  только  такую  задачу  о  перевозках, в  которой  сумма  запасов  ровна  сумме  заявок:
                    (где 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, причём
 a аi > a 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 равным недостающему запасу и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равным  нулю.
 

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

    Имеется  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 не вызывает внутреннего отторжения, а наоборот, оставляет ощущение комфорта. Эти приложения надежны и при эксплуатации обладают предсказуемым поведением.
      Программа имеет удобный и интуитивно понятный интерфейс.
 

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

    Кузнецов  А.В., Сакович В.А., Холод Н.И. ”Высшая  математика. Математическое программирование ”, Минск, Вышэйшая школа, 2001г.
    Акулич И.Л. «Математическое программирование в примерах и задачах», Высшая школа, 1984г.
    Ермаков В.И. “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
    Канторович Л.В., Горстко А.Б. «Математическое оптимальное программирование  в экономике», Знание, 1968г.
    Канторович Л.В., Горстко А.Б. «Оптимальные решения в экономике», Наука, 1972г.
    Конюховский П.В. «Математические методы исследования операций в экономике», Питер, 2000г.
    Кузнецов А.В., Новикова Г.И., Холод И.И. – «Сборник задач по математическому программированию». Минск, Высшая школа, 1985г.
    Справочная система Delphi 7.
    Ресурсы сети 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
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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