Транспортная задача. Постановка задачи. Открытая и закрытая задачи. Теорема существования. Двойственная транспортная задача

Федеральное агентство по образованию

ГОУВПО «Удмуртский государственный  университет»

Институт экономики и  управления

 

 

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

По Экономике Математическим Методам

На тему: «Транспортная  задача. Постановка задачи. Открытая и  закрытая задачи. Теорема существования. Двойственная транспортная задача»

 

 

 

 

 

Выполнил студент

Гр. 00611-31                                                                                         М.А. Шевякова

 

 

Проверил

К.э.н., доцент                                                                                       А.Ф. Гольдман

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ижевск, 2012

 

Оглавление

 

Введение. 3

Постановка задачи. 4

Основные свойство транспортной задачи. 6

Двойственная задача. 8

Теоремы двойственности. 9

Построение опорного плана транспортной задачи. 10

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

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

Вычислительная схема  метода потенциалов 13

Заключение. 15

Использованная литература. 16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Постановка задачи.

 

Классическая транспортная задача ЛП формулируется следующим  образом.

Имеется  m  пунктов производства (поставщиков) и n  пунктов потребления (потребителей) однородного продукта. Заданы величины:

  - объем производства (запас) i-го поставщика,  i=1, m  ;

  - объем потребления   (спрос) j-го потребителя, i=1, n ;

   - стоимость перевозки (транспортные  затраты) единицы продукта от i-го поставщика к  j-му потребителю.            

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

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

Транспортная задача, в  которой суммарные запасы                                               

и суммарные потребности                                                

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

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

вводится фиктивный n+1 потребитель, потребности которого                                               

В случае, когда суммарные  потребности превышают суммарные

запасы,  т.е.                                               

, вводится фиктивный m+1 поставщик, запасы которого                                               

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные свойство транспортной задачи.

 

 

            Математические модели любых транспортных задач ЛП обладают общими чертами, а  именно,            

1) коэффициенты  целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);             

2) коэффициенты правых  частей ограничений неотрицательны (запасы и потребности продукта);             

3) коэффициенты в ограничениях  принимают только два значения, это нули и единицы.            

В силу этих особенностей транспортная задача обладает следующими свойствами.             

Теорема 1.

Базисное решение  закрытой модели транспортной задачи содержит m+n-1 базисных компонент.            

Доказательство.

Количество базисных компонент  определяется число линейно-независимых  ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.             

Действительно, сложив первые m ограничений и  следующие n ограничений задачи, получим                                   

            

Но в закрытой модели выполняется  балансовое равенство                                   

            

поэтому получаем, что нетривиальная  линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это  означает, что среди ограничений  задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых  ограничений равно  m+n-1 и базис задачи состоит из m+n-1 компонент.

Теорема доказана             

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

Теорема 2.

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

Доказательство.

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

Покажем существование допустимого  решения. Так как           

суммарные запасы                                                

  

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

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

Покажем ограниченность целевой  функции.            

Так как            

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

Теорема доказана

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Двойственная задача.

 

 

            Запишем транспортную задачу в матричном  виде

            

A- матрица ограничений,  имеющая в соответствии с векторами  х и b вид :              

            

Двойственная задача к  транспортной задаче в матричном  виде будет иметь вид

у- произвольного знака.            

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

            

Тогда                        

и ограничения двойственной задачи будут иметь вид :                                   

или  в общем виде двойственная задача            

            

Двойственные переменные ai, i=1,...,m, bj, j=1,...,n, называются платежами, а                                   

- псевдостоимость перевозок единицы груза из пункта i в пункт j, i=1,...,m, j=1,...,n.

 

 

 

Теоремы двойственности.

 

 

            ИЗ теории двойственности ЛП практический интерес представляет вторая теорема  двойственности, из которой получается следующий критерий.            

Критерий  оптимальности транспортной задачи             

План перевозок                                   

является оптимальным  планом тогда и только тогда, когда  найдется система платежей                                   

для которой выполняются  условия :            

       Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.            

Ели                        

удовлетворяют ограничениям прямой задачи, а                        

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

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

            

Условие а) выполняется для  любых допустимых решений прямой задачи, так как                                   

            

Условие b) можно расписать  как следствие о дополняющей нежесткости, а именно            

            

Итак, для базисных переменных                                    

имеем равенство            

 

а для небазисных переменных                                      

достаточно выполнения допустимости двойственных переменных                                         

Таким образом имеем условия 1) и 2) критерия.

Критерий  доказан.

 

Построение опорного плана транспортной задачи.

 

 

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

Базисными клетками транспортной таблицы являются клетки с от-

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

1) сумма перевозок в  каждой строке равна запасу   в данной

строке;            

2) сумма перевозок в  каждом столбце равна соответствующему

столбцу спросу                                               

            

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок                                                

            

Опорный план называется вырожденным, если число ненулевых перевозок                                               

 

меньше и n+m-1, опорный план - невырожден, если число

ненулевых перевозок равно n+m-1.            

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 Рассмотрим "северо-западный угол" незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю.             

Возможны три случая.            

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

запас равен нулю, поэтому                                    

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

            

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

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

            

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

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

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

            

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

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