Метод аппроксимации Фогеля нахождения опорного плана транспортной задачи

 

 

 

 

 

 

 

 

Содержание

 

                                Введение                                                                                                                                                     3             

Метод аппроксимации Фогеля нахождения опорного плана транспортной задачи

1.Математическая постановка транспортной задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

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

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

4.Пример. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

 

Список использованной литературы                                                                                         10

 

Введение

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

 

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначив через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через - запасы груза в i-м пункте отправления, через   - потребности в грузе в j-м пункте назначения, а через – количество единиц груза, перевозимого из i–го пункта отправления в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции:

 

при условиях:

                                                                                                             (1)                                                                                            

                                                                                                     (2)

                                                                                                      (3)

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

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

Исходные данные транспортной задачи записывают в виде таблицы:

Пункт отправления	Пункт назначения					Запасы
		…		…
		…
…	…	…	…	…	…	…
…	…	…	…	…	…	…
Потребности		…		…

 

Таблица 1.

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

                                                                                                                      (4)       то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.

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

                                                                                                                                                                               вводят фиктивный (n + 1)-й пункт назначения с потребностью:

                                                                                                            и соответствующие тарифы считают равными нулю:

                                                                      

Полученная задача является транспортной задачей, для которой выполняется равенство (4). Аналогично, при

                                                                                                                   вводят фиктивный (m+1)-й пункт отправления с запасом груза:

                                                                                                           и соответствующие тарифы полагают равными нулю:

                                                      .

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

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (1) и (2) равно n + m. Так как мы предполагаем, что выполняется условие (4), то число линейно независимых уравнений равно       n + m – 1. Следовательно, опорный план транспортной задачи может иметь не более n + m–1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n + m – 1, то план является невырожденным, а если меньше – то вырожденным.

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

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

Как и при решении задачи линейного программирования симплексным методом, определение оптимального плана транспортной задачи начинают с поиска какого-нибудь ее опорного плана. Его находят методом северо - западного угла, методом минимального элемента или методом аппроксимации Фогеля. Сущность этих методов состоит в том, что опорный план находят последовательно за n + m – 1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, называемую занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения (того, в столбце которого находится заполненная клетка), либо вывоз груза из какого-либо пункта отправления (из того, в строке которого находится заполняемая клетка).

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

После того как проделаны m + n – 2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом остается свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают (n + m – 1) – й шаг и получают искомый опорный план.

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

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

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

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

4. Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

 

.

 

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

Исходные данные задачи приведены в таблице 2.

 

 

Пункт отправления	Пункт назначения				Запасы
Потребности	7 8 9 120	8 5 2 50	1 9 3 190	2 8 6 110	160 140 170 470

 

Таблица 2.

Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке (таблица 3). Так, в строке минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5 – 4 = 1. Точно так же разность между минимальными элементами в столбце равна 6 – 2 = 4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу . В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки и столбца Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта . Поэтому исключим из рассмотрения столбец и будем считать запасы пункта равными 160 – 110 = 50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором столбце и во второй дополнительной строке (таблица 3).