Транспортная задача

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

            

то есть спрос первого  потребителя полностью удовлетворен и поэтому                    

а остаток продукта в первом пункте производства равен                                   

            

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

поэтому условно считается, что выбывает только поставщик,                        

а спрос потребителя остается неудовлетворенным и равным нулю.                                    

            

После этого рассматриваем  северо-западный угол оставшейся не-

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

через n+m-1   шагов получим опорный план.

9.7 Пример            

Найти опорный план транспортной задачи                                   

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

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

 

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

 

 

            Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 , Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться.             

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

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

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

платежей                                   

и определяются величины                                   

называемые "псевдостоимостями" перевозок единицы груза из пункта i

в пункт j.  При этом цена цикла пересчета для каждой свободной клетки

равна                        

если платежи            

                                  для всех базисных клеток (i, j)

9.9 Вычислительная схема  метода потенциалов  [1, 3]            

Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1   базисными клетками.            

Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю.            

Шаг 3. Считаем псевдостоимости                                   

для всех свободных клеток. Если                                   

 

для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.                                     

Шаг 4. Если есть свободная клетка, для которой                        

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

Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.                        

Пример

Решить методом потенциалов  транспортную задачу                                   

        

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

Приписываем к таблице  добавочную строку для платежей                                               

   

и добавляем столбец для  платежей                                               

 

Псевдостоимости записываем в левом углу клетки, а стоимости - в правом углу.            

Из условий                                   

 

в базисных клетках получаем систему уравнений                                   

Полагая    ,  находим последовательно платежи                        

и псевдостоимости для свободных клеток. Получаем таблицу                        

Стоимость перевозок по плану  этой таблицы            

            

Так как клетка (1,3) имеет  отрицательную цену                                               

то план не является оптимальным. Строим для клетки (1,3) цикл. Цена

цикла                                   

 

По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки  в клетке (1, 2) не стали отрицательными).При

этом стоимость плана  уменьшается на                                   

 

Для нового плана вычисляем  новые значения платежей и псевдостоимостей:                                      

 

Стоимость перевозок по плану  этой таблицы                        

Полученная таблица имеет  клетку (2,1 ) с отрицательной ценой                                   

По циклу этой клетки переносим 10 единиц груза,

при этом стоимость плана  уменьшается на                                               

единиц, и получаем новый  опорный план с новой системой платежей и псевдостоимостей:                                               

 

Стоимость перевозок по плану  этой таблицы                                   

Так как в последней  таблице все псевдостоимости не превосходят

соответствующих стоимостей, то полученный опорный план                        

является оптимальным. Стоимость  перевозок при этом                                   

 

1.1.2 Терминология

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

Главное окно – основное окно программы.

Рабочая область - основная часть Главного окна, предназначенная  для отображения данных.

 

 

1.1.3 Спецификация  качества программного обеспечения

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

Надёжность: программа должна быть автономной.

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

 

2 ПРОЕКТИРОВАНИЕ

2.1 Выбор используемых  технологий

Разработка проекта производиться  на языке программирования С#, в среде разработки Microsoft Visual Studio 2010.

Язык С# является продолжение языков С и С++. Однако отличается от языка программирования С#, данный язык является объектно - ориентированным. От С++ данный язык отличается измененным, более удобным синтаксисом, и тем что все равно эту хуйню никто читать не будет он является .NET платформенным. Что позволяет использовать в данной разработке программное обеспечение промежуточного уровня   .NET Framework 4.0.

Благодаря использованию  среды разработки Microsoft Visual Studio 2010, процесс написания и отладки программы становится проще, это достигается встроенными средствами Microsoft Visual Studio.

 

2.2 Проектирование  графического интерфейса

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

Интерфейс - в широком  смысле слова, это способ (стандарт) взаимодействия между объектами. Интерфейс  в техническом смысле слова задаёт параметры, процедуры и характеристики взаимодействия объектов.

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

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

 

                                                

  Рисунок 1 – Главное окно программы.

 

Вкладка Условия задачи содержит три таблицы, содержащие исходные данные решаемой задачи (рис. 2).

 

 

Рисунок 2 – Вкладка Условия  задачи.

 

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

 

 

Рисунок 3 – Вкладка Опорный  план.

 

Следом располагается  вкладка Оптимальное решение. В  ней содержатся кнопки  Найти и Стоимость. С помощью кнопки Найти  находим оптимальное решение задачи, которое отображается в таблице в  рабочей области. А кнопкой Стоимость можем узнать стоимость доставки груза после оптимизации (рис. 4).

 

 

Рисунок 4 – Вкладка Оптимальное  решение.

 

 

3 РУКОВОДСТВО  ПОЛЬЗОВАТЕЛЯ

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

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

 

Первая строка:

4 6 - размеры массивов A и B

Вторая строка:

14 7 22 17 - массив А

Третья строка

7 12 3 11 8 20 - массив В

Далее количество строк, равные количеству символов в  массиве А:  матрица С

1,1 2 2,05 1 3 0,5

3 2,15 4,8 3 11,07 2,2

0,8 1 0,75 2,12 0,1 2,8

0,7 3 1,1 3,7 1 0,2

Для отделения  целой части от дробной используется символ запятой «,»

В конце строк  не должно быть пробелов.

 

Сохраните файл в любое, удобное  вам место.

Далее в Главном окне программы  с помощью кнопки Импорт загружаем  в программу исходные данные.

Проверяем наличие опорного плана и стоимость перевозок  до оптимизации во вкладке Опорный  план.

Во вкладке Оптимальное  решение с помощью кнопки Найти находим оптимальное решение транспортной задачи. Кнопкой Стоимость можем проверить стоимость перевозок после оптимизации.