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

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Таблица 1

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

Очевидно, общее наличие груза у поставщиков равно

а общая потребность в грузе в пунктах назначения равна

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

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

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

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

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

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

Аналогично, при

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

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

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

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

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

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

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

Рассмотрим пример (1):

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

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение.

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

При данном плане перевозок общая стоимость перевозок составит

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

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

транспортный задача потенциал фогель

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

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

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

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

При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривает первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнения клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного т.е. идет как бы по диагонали таблицы.

Рассмотрим пример(2):

На три базы ,, поступил однородный груз в количествах, соответственно равных 140,180 и 160 единиц. Этот груз требуется перевезти в пять пунктов назначения ,,, соответственно в количествах 60,70,120,130 и 100 единиц. Тарифы перевозок единицы груза с каждого из пунктов назначения указаны в следующей таблицы:

Таблица 2

Пункты отправления	Пункты назначения	Запасы
	2	3	4	2	4	140
	8	4	1	4	1	180
	9	7	3	7	2	160
Потребности	60	70	120	130	100	480

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

Решение.

Здесь число пунктов отправления , а число пунктов назначения . Следовательно, опорный план задачи определяется числами, стоящими в заполненных клетках.

Заполнение таблицы начнем с клетки для неизвестного , т.е. попытаемся удовлетворить первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта больше, чем потребности пункта , то полагаем , записываем это значение в соответствующей клетке таблицы 2 и временно исключаем из рассмотрения столбец ,считая при этом запасы пункта равными 80.

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

Теперь перейдем к заполнению клетки для неизвестного и так далее. Через шесть шагов остается один пункт отправления с запасом груза 100 единиц и один пункт назначения с потребностью 100 единиц. Соответственно имеется одна свободная клетка, которую заполняем, пологая =100 (таблица 3). В результате получаем опорный план:



Таблица 3

Пункты отправления	Пункты назначения	Запасы
	2 60	3 70	4 10	2	4	140
	8	4	1 110	4 70	1	180
	9	7	3	7 60	2 100	160
Потребности	60	70	120	130	100	480

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет

Метод минимального элемента

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

Пример (3):

Найти опорный план примера (1) методом минимального элемента.

Решение.

Исходные данные запишем в виде таблицы (4). Минимальный тариф, равный 1, находятся в клетке для переменной . Положим запишем это значение в соответствующую клетку таблицы (4) и исключим временно из рассмотрения строку Потребности пункта назначения считаем равным 30 единиц. В оставшейся части таблицы с двумя строками и и четырьмя столбцами и клетка с наименьшим значением тарифа находится на пересечении строки и столбца , где . Положим . и внесем это значение в соответствующую клетку таблицы 4. Временно исключим из рассмотрения столбец и будем считать запасы пункта равными 120 единиц. После этого рассмотрим оставшуюся часть таблицы с двумя строками и и тремя столбцами и . В ней минимальный тариф находится в клетке на пересечении строки и столбца и равен 3. Заполним описанным выше способом эту клетку и аналогично заполним (в определенной последовательности) клетки, находящиеся на пересечении строки и столбца ,строки и столбца ,строки и столбца . В результате получим опорный план .

Таблица 4

Пункты отправления	Пункты назначения	Запасы
	7	8	1160	2	160
	4120	5	9	820	140
	9	250	330	690	170
Потребности	120	50	190	110	470

При данном плане перевозок общая стоимость перевозок составляет:

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

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

Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи.

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

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

Пример (4)

Найти опорный план примера (1) методом аппроксимации Фогеля. Исходные данные приведены в таблице 5.



Таблица 5

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

Решение.

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

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

Таблица 6

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

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

При этом плане общая стоимость перевозок такова

.

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

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

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

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

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

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

Теорема 2. Если для некоторого опорного плана , транспортной задачи существуют такие числа:

что:

при (8)

при (9)

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

Определение 3: Числа ( и ) называются потенциалами соответственно пунктов назначения и пунктов потребления.

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы ( и ). Эти числа находят из системы уравнений

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

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

.

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

Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных c заполненной так называемым циклом.

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

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

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

1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке -- знак плюс, а всем остальным клеткам -- поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);

2) в данную свободную клетку переносят меньшее из чисел стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел считается свободной.

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

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

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

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

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

Из изложенного выше следует, что процесс нахождения решения транспортной задачи методом потенциалов включает следующие этапы:

1). Находят опорный план. При этом число заполненных клеток должно быть равным

2). Находят потенциалы ,- соответственно пунктов назначения и отправления.

3). Для каждой свободной клетки определяют число . Если среди чисел нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то переходят к новому опорному плану.

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

5). Полученный опорный план проверяют на оптимальность, т. е. снова повторят все действия начиная с этапа 2.

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

Пример (4):

Для транспортной задачи, исходные данные которой приведены в табл. 7, найти оптимальный план.

Решение. Сначала, используя метод северо-западного угла, находим опорный план задачи. Этот план записан в табл. 7.

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

Таблица 7

Пункты отправления	Пункты назначения	Запасы
	1 30	2 20	4	1	50
	2	3 10	1 10	5 10	30
	3	2	4	4 10	10
Потребности	30	30	10	20	90

,

Для каждой свободной клетки вычисляем число

:

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

Таблица 8

Пункты отправления	Пункты назначения	Запасы
	1 30	2 20	4 4	1 3	50
	2 0	3 10	1 10	5 10	30
	3 -2	2 0	4 -4	4 10	10
Потребности	30	30	10	20	90

Так как среди чисел имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Наибольшим среди положительных чисел являются , поэтому для данной свободной клетки строим цикл пересчета (табл. 8) и производим сдвиг по этому циклу. Наименьшее из чисел в минусовых клетках равно 10. Клетка, в которой находится это число, становится свободной в новой табл. 9. Другие числа в табл..9 получаются так: к числу 10, стоящему в плюсовой клетке табл. 8, добавим 10 и вычтем 10 из числа 20, находящегося в минусовой клетке табл. 8. Клетка на пересечении строки и столбца становиться свободной.

После этих преобразований получаем новый опорный план (табл. 9). Этот план проверяем на оптимальность. Снова находим потенциалы пунктов отправления и назначения. Для этого составляем следующую систему уравнений

Полагаем , получаем ,, , , Для каждой свободной клетки вычисляем число : имеем,,

Таблица 9

Пункты отправления	Пункты назначения	Запасы
	1 30	2 20	2 2	1 10	50
	2 0	3 20	1 10	5	30
	3	2	4	4 10	10
Потребности	30	30	10	20	90

Таблица 10

Пункты отправления	Пункты назначения	Запасы
	1 30	2 0	4 4	1 20	50
	2 0	3 20	1 10	5	30
	3	2 10	4	4	10
Потребности	30	30	10	20	90

Таким образом, видим, что данный план перевозок не является оптимальным. Поэтому переходим к новому опорному плану (табл.10).

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

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

Метод дифференциальных рент.

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

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

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

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

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

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

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

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

Пример (4):

Для транспортной задачи, исходные данные которой приведены в табл.11, найти оптимальный план методом дифференциальных рент.

Решение. Перейдем от табл.11 к табл.12, добавив один дополнительный столбец для указания избытка и недостатка по строкам и одну строку для записи соответствующих разностей.

Таблица 10

Пункты отправления	Пункты назначения	Запасы
	7	12	4	8	5	180
	1	8	6	5	3	350
	6	13	8	7	4	20
Потребности	110	90	120	80	150	550

Таблица 11

Пункты отправления	Пункты назначения	Запасы	Недостаток избыток (
	7	12	4 120	8	5	180	+60
	1 110	8 90	6	5 80	3 70	350	-80
	6	13	8	7	4	20	+20
Потребности	110	90	120	80	150	550
Разность	5	4		2	1

В каждом из столбцов табл.12 находим минимальные тарифы и обводим их кружками. Заполняем клетки, в которых стоят указанные числа. Для этого в каждую из клеток записываем максимально допустимое число. Например, в клетку, находящуюся на пересечении строки и столбца ,записываем число 120. В эту клетку нельзя поместить большее число, поскольку в таком случае были бы превышены потребности пункта назначения .

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

После получения условно оптимального плана определяем избыточные и недостаточные строки. Здесь недостаточной является строка , так как запасы пункта отправления полностью использованы, а потребности пункта назначения удовлетворены частично. Величина недостатка равна 80 ед.

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

После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 5, 4, 2, 1 (табл.11). Для столбца разность не определена, так как число, записанное в кружке в данном столбце, находится в положительной строке. В столбце число, стоящее в кружке, равно , а в избыточных строках в клетках данного столбца наименьшим является число . Следовательно, разность для данного столбца равна Аналогично находим разности для других столбцов: для ; для ; для . .

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

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

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

Таблица 11

Пункты отправления	Пункты назначения	Запасы	Недостаток избыток (
	7	12	4 120	8	5	180	+60
	2 110	9 90	6	6 80	4 70	350	-60
	6	13	8	7	4 20	20	-0
Потребности	110	90	120	80	150	550
Разность	5	3		2	1

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

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

Таблица 12

Пункты отправления	Пункты назначения	Запасы	Недостаток избыток (
	7	12	4 120	8	5 60	180	0
	3 110	10 90	8	7 80	5 70	350	0
	7	14	9	8	5 20	20	0
Потребности	110	90	120	80	150	550

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

При этом плане перевозок общие затраты таковы

Решение задач

Задача №1

Решим эту задачу с помощью Maple 7.

> x:=matrix (3,4);

> C:=matrix([[7,8,1,2],[4,5,9,8],[9,2,3,6]]);

> F:=sum(sum(C[i,j]*x[i,j],i=1..3),j=1..4);

> with(simplex);

minimize(F,{sum(x[1,j],j=1..4)=160,sum(x[2,j],j=1..4)=140,sum(x[3,j],j=1..4)=170,sum(x[i,1],i=1..3)=120,sum(x[i,2],i=1..3)=50,sum(x[i,3],i=1..3)=190,sum(x[i,4],i=1..3)=110},NONNEGATIVE);

> V:=matrix([[0,0,50,110],[120,20,0,0],[0,30,140,0]]);

> sum(sum(C[i,j]*V[i,j],i=1..3),j=1..4);

Задача № 2

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

Найти оптимальный план.

> x:=matrix (3,4);

> C:=matrix([[2,3,4,3],[5,3,1,2],[2,1,4,2]]);

> F:=sum(sum(C[i,j]*x[i,j],i=1..3),j=1..4);

> with(simplex);

minimize(F,{sum(x[1,j],j=1..4)<=180,sum(x[2,j],j=1..4)<=60,sum(x[3,j],j=1..4)<=80,sum(x[i,1],i=1..3)=120,sum(x[i,2],i=1..3)=40,sum(x[i,3],i=1..3)=60,sum(x[i,4],i=1..3)=80},NONNEGATIVE);

> V:=matrix([[120,0,0,40],[0,0,60,0],[0,40,0,40]]);

> sum(sum(C[i,j]*V[i,j],i=1..3),j=1..4);

Задача № 3

Производственное объединение имеет в своем составе три филиала, которые производят однородную продукцию соответственно в количествах, равных 75,125 и 100 единиц. Эту продукцию получают четыре потребителя, расположенные в разных местах. Их потребности соответственно равны 80,65,70 и 85 единиц. Тарифы перевозок единицы продукции от каждого из филиалов соответствующим потребителям задаются матрицей

Найти оптимальный план.

>

with(linalg); c := vector([464, 513, 654, 867, 352, 416, 690, 791, 995, 682, 388, 658]); x := vector(12); z := dotprod(x, c);

cs := {x[1]+x[5]+x[9] = 80, x[2]+x[6]+x[10] = 65, x[3]+x[7]+x[11] = 70, x[4]+x[8]+x[12] = 85, x[1]+x[2]+x[3]+x[4] = 75, x[5]+x[6]+x[7]+x[8] = 125, x[9]+x[10]+x[11]+x[12] = 100};

with(simplex); sol := minimize(z, cs, NONNEGATIVE);

assign(sol); z;



Задача № 4

Пункты отправления	Пункты назначения
					Запасы
	4	2	3	1	80
	6	3	5	6	140
	3	2	6	3	70
Потребности	80	50	50	70

Найти оптимальный план

>



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

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов экономической специальности вузов.-М: Высшая школа 1986.-319 с. Ил.

2. Сдвижков О.А Математика на компьютере:Maple 8 М.:СОЛОН-Пресс,2003.-176с.(Серия «Библиотека студента»)

3. Кирсанов М.Н Maple и Maplet. Решения задач механики: Учебное пособие.-СПб.: Издательство «Лань», 2012.-512 с.:ил.-(Учебники для вузов. Специальная литература).

Размещено на Allbest.ru

...