Методы нахождения опорного плана транспортной задачи - метод северо-западного угла и метод минимального элемента

МИНИСТЕРСВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

 

Красноярский институт железнодорожного транспорта - филиал ГОУВПО

«Иркутского государственного университета путей сообщения» в  г. Красноярске.

 

Кафедра Э и УП

 

Контрольная работа по дисциплине «Оптимизация в экономике»

Тема: «Методы нахождения опорного плана транспортной задачи - метод северо-западного угла и метод минимального элемента»

 

 

Выполнила: Черемных Ю.Е.

Студентка гр. Э-09-2

Зачетная книжка № 1072023

Проверила: Малахова А.А.

«____»__________

 

(оценка и подпись  преподавателя)

 

 

Красноярск 2013

 

1.Транспортная задача (ТЗ)

Специфика математической модели ТЗ позволяет наряду с общими методами решения задач ЛП применять специальные  методы, позволяющие сократить вычисления.

Постановка  задачи. Имеется m пунктов производства (складов) некоторого одного продукта, задан ai – объем производства в i-м пункте производства,  . Есть n пунктов потребления этого продукта, задан bj – объем потребления (поданные заявки на поставку продукта) в j-м пункте потребления,  .

Пункты производства связаны  с пунктами потребления сетью  дорог с определенными тарифами на перевозки. Стоимость перевозки  одной единицы продукта (груза) из i –го пункта производства в j-ый пункт потребления равна с_ij. Необходимо найти оптимальный план перевозок продукции, при котором транспортные издержки минимальны, продукция полностью вывозится из пунктов производства и полностью удовлетворяется потребность в продукции.

Модель. В качестве переменных выбираются элементы матрицы перевозок:  .  

Пусть   – количество единиц продукции, вывозимых из i-го пункта производства в j-й пункт потребления. 

 

                        

 

Ограничения группы (a) задают условие: из каждого i-го пункта производства должен быть вывезен весь продукт. Например (рис. 3.1), из первого пункта производства с объемом производства a1  продукт может быть перевезен в любой пункт потребления. Объемы перевозок неизвестны и составляют:  – количество единиц продукции, перевезенных из первого пункта производства в первый пукнт потебления;  – количество единиц продукции, перевезенных из первого пункта производства во второй пункт потребления;  – количество единиц продукции, перевезенных из первого пункта производства в n-ый пункт потребления. Сумма всех перевезенных единиц продукции должна быть равна a₁. Получаем ограничение:

.

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

Размерность задачи:  . Транспортная задача – частный случай задачи линейного программирования, в которой все ограничения представлены равенствами. В отличие от общего случая решения задачи ЛП оптимальное решение транспортной задачи всегда существует.  

 

Открытая и  закрытая транспортные задачи. Выделяют два типа ТЗ:  открытая ТЗ и закрытая ТЗ.

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

.                                        (1.1)

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

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный  объем производства меньше суммарного объема потребления:

.                                      (1.2)

Известно, что для существования  допустимого решения транспортной задачи необходимо и достаточно, чтобы  задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

,                              (1.3)

при этом полагают  .

Второй случай. Суммарный  объем производства больше суммарного объема потребления:

.                                     (1.4)

Для сведения ТЗ к закрытому  типу вводят фиктивный пункт потребления  с номером n+1 с объемом потребления:

,                               (1.5)

при этом полагают  .

Методы решения.

·     Как задача линейного программирования ТЗ может быть решена симплекс методом .

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

 

 

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

Решение транспортной задачи, как и всякой задачи ЛП начинается с нахождения допустимого опорного решения (опорного плана). Рассмотрим два  метода нахождения опорного плана транспортной задачи: метод северо-западного угла и метод минимального элемента.

Введем основные определения  и обозначения.

Условие транспортной задачи задают в виде транспортной таблицы (табл. 1.6) вида:

Таблица 1.6.

 

 

Решение транспортной задачи задают в виде матрицы (плана перевозок):

или в виде таблицы плана  перевозок (табл. 3.4): 

 

Таблица 1.7.

 

 

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

План перевозок – допустимый, если он удовлетворяет балансовым условиям (1.1): все заявки удовлетворены, все запасы исчерпаны. 

Допустимый план – опорный, если в нем отличны от нуля не более чем r=m+n-1 базисных перевозок  , а остальные перевозки равны нулю. Если отличных от нуля перевозок менее чем r=m+n-1, то такой план называют вырожденным опорным планом.

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

1.2. Метод северо-западного угла для нахождения опорного плана ТЗ

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 1.6).

Шаг 1. Проверяют выполнение условия баланса (1.1). Если условие баланса не выполняется, т.е. задача открытая, то ее сводят к закрытому типу.

Шаг 2. Создают таблицу  плана перевозок (табл. 1.7), в которой заполнены только объемы производства и объемы потребления. Далее начинают заполнять таблицу перевозок с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз.

Процесс продолжают до тех пор, пока не исчерпаются предложения и полностью не удовлетворится спрос.

Пример. Определить опорный план по методу северо-западного угла для транспортной задачи, заданной в табл. 1.8.

На первом шаге проверяют  выполнение балансовых условий. Суммарный  объем производства составляет: 200+40+110=350 условных единиц; суммарный объем  потребления равен: 120+50+190+110=470. Следовательно, ТЗ – открытая. Для ее сведения к  закрытому типу необходимо ввести четвертый  пункт производства с объемом  производства равным:  =470-350=120 условных единиц. Так как пункт производства фиктивен, то стоимости перевозок продукции из этого пункта в пункты потребления нулевые (табл. 1.9). 

 

Таблица 1.8

Таблица 1.9

 

 

На втором шаге создают  пустую таблицу плана перевозок и начинают ее заполнение (табл. 1.10).

В первую клетку помещают:   (табл. 1.10). Заявки первого потребителя полностью удовлетворены, остальные клетки первого столбца заполняют нулями. Остаток продукции в первом пункте составляет: 200-120=80 условных единиц груза. 

Далее двигаются по первой строке вправо и заполняют клетку (1,2):  . Заявки второго потребителя полностью удовлетворены, оставшиеся клетки второго столбца заполняют нулями. Остаток продукции в первом пункте равен: 80-50=30 условных единиц груза. 

Двигаются по первой строке вправо и заполняют клетку (1,3):   . Предложения первого поставщика исчерпаны, клетка (1,4) заполняется нулем.

Далее заполняют таблицу  плана перевозок по аналогии.

Полученный план перевозок (табл. 1.11) – допустимый, так как для него выполняются условия баланса и опорный, так как число базисных клеток равно 7 и r=m+n-1=4+4-1=7.      

 

Таблица 1.10

Таблица 1.11

 

 

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

.

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

 

1.2. Метод минимального элемента для нахождения опорного плана ТЗ

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

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 1.6).

Шаг 1. Проверяют выполнение условия баланса. Если условие баланса  не выполняется, т.е. задача открытая, то ее сводят к закрытому типу.

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

Процесс продолжается до тех  пор, пока не заполнены все клетки таблицы перевозок.

Пример .Определить опорное решение по методу минимального элемента для транспортной задачи, заданной в табл 1.8.

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

На втором шаге создают  пустую таблицу плана перевозок и начинают ее заполнение (табл. 1.12). 

 

Таблица 1.12 

 

 

Минимальная стоимость перевозки  единицы продукции соответствует  клеткам (4,1), (4,2), (4,3), (4,4): с41= с42= с43= с44=0. Начать заполнение таблицы перевозок  можно с любой из этих клеток. Пусть  . Остальные клетки четвертой строки и первого столбца заполняются нулями.

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

Далее заполняется клетка (1,4), как имеющая наименьшую стоимость  перевозок единицы продукции:  .  Оставшиеся клетки четвертого столбца заполняются нулями. Затем заносится в клетку (1,2):  ; в клетку (2,2):  .

В результате получен допустимый план перевозок, все балансовые условия  выполнены (табл. 3.9). План перевозок  также опорный и вырожденный, так как число базисных клеток равно 5 и меньше r=7.     

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

.

и значительно ниже стоимости  плана, полученного методом северо-западного  угла.

Примечание. Стоимость плана, полученного методом северо-западного  угла, не всегда ниже стоимости плана, полученного методом минимального элемента.