Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A₁, A₂, ..., А _m в n пунктов назначения В₁, В₂, ..., В _n.

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

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

Обозначим через c_ij тарифы перевозки единицы груза из i–го пункта отправления в j–й пункт назначения, через а _i – запасы груза в i–м пункте отправления, через b_j – потребности в грузе в j–м пункте назначения, а через х _ij – количество единиц груза, перевозимого из i–го пункта отправления в j–й пункт назначения.

Тогда математическая постановка задачи состоит в определении минимального значения функции

                       (7.5)

при условиях                                                        (7.6)

                        (7.7)

                 (7.8)

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

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

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

Обычно исходные данные задачи записывают в виде табл. 7.1.

Таблица 7.1

Исходные данные транспортной задачи

Пункты отправления	Пункты назначения					Запасы
	B1	…	Bj	…	Bn
A1	c11 x11	…	c1j x1j	…	c1n x1n	a1
…	…	…	…	…	…	…
Ai	ci1 xi1	…	cij xij	…	cin xin	ai
…	…	…	…	…	…	…
Am	cm1 xm1	…	cmj xmj	…	cmn xmn	am
Потребности	b1	…	bj	…	bn

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

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

                                    (7.9)

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

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

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

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

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

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

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

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

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

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

Число переменных x_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (7.6) и (7.7) равно n + m.

Так как мы предполагаем, что выполняется условие (7.9), то число линейно независимых уравнений равно n + m – 1.

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

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

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

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

Для определения оптимального плана транспортной задачи можно использовать стандартные методы линейного программирования, например, симплекс–метод. Однако ввиду исключительной практической важности этой задачи и специфики её ограничений [каждая неизвестная входит лишь в два уравнения систем (7.6) и (7.9) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы: метод потенциалов, метод дифференциальных рент и др.

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

Поиск оптимального плана транспортной задачи начинают с нахождения какого–нибудь её опорного плана.

Опорный план находят последовательно за n+m–1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой.

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

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

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

После того как проделаны n+m–2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения.

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

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

В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что–нибудь одно).

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

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

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

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

Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x₁₁ («северо–западный угол») и заканчивается клеткой для неизвестного x_mn, т. е. идёт как бы по диагонали таблицы.

Пример 7.2. На три базы A₁, A₂, A₃ поступил однородный груз в количествах, соответственно равных 140, 180 и 160 ед. Этот груз требуется перевезти в пять пунктов назначения B₁, B₂, B₃, B₄, B₅ соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза указаны в следующей табл. 7.2. Найти план перевозок данной транспортной задачи методом северо–западного угла.

Таблица 7.2

Исходные данные задачи

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

 

Решение. Здесь число пунктов отправления m = 3, а число пунктов назначения n = 5. Следовательно, опорный план задачи определяется числами, стоящими в 7 (5 + 3 – 1 = 7) заполненных клетках.

Заполнение таблицы начнём с клетки для неизвестного x₁₁, т.е. попытаемся удовлетворить потребности первого пункта назначения за счёт запасов первого пункта отправления.

Так как запасы пункта A₁ больше, чем потребности пункта B₁, то полагаем x₁₁ = 60, записываем это значение в соответствующей клетке табл.7.3 и временно исключаем из рассмотрения столбец B₁, считая при этом запасы пункта А₁ равными 80.

Таблица 7.3

Получение опорного решения задачи

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

 

Рассмотрим первые из оставшихся пунктов отправления А₁ и назначения В₂. Запасы пункта А₁ больше потребностей пункта В₂.

Положим x₁₂ = 70, запишем это значение в соответствующей клетке табл. 7.3 и временно исключим из рассмотрения столбец B₂.

В пункте A₁ запасы считаем равными 10 ед.

Снова рассмотрим первые из оставшихся пунктов отправления А₁ и назначения В₃.

Потребности пункта В₃ больше оставшихся запасов пункта A₁.

Положим x₁₃ = 10 и исключим из рассмотрения строку A₁.

Значение x₁₃ = 10 запишем в соответствующую клетку табл. 7.3 и считаем потребности пункта В₃ равными 110 ед.

Теперь перейдём к заполнению клетки для неизвестного x₂₃ и т.д.

Через шесть шагов остаётся один пункт отправления A₃ с запасом груза 100 ед. и один пункт назначения B₅ с потребностью 100 ед.

Соответственно имеется одна свободная клетка, которую и заполняем, полагая x₃₅ = 100 (табл. 7.3).

В результате получаем опорный план

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

S = 2×60 + 3×70 + 4×10 + 1×110 + 4×70 + 7×60 + 2×100 = 1370.

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

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

Если для некоторого опорного плана

транспортной задачи существуют такие числа a₁, a₂, …, a _m, b₁, b₂, …, b _n, что

при x_ij > 0                       (7.10)

при  x_ij = 0                             (7.11)

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

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

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

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

Для каждого из пунктов отправления и назначения определяют потенциалы a _i и   

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

,                                        (7.12)

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

Так как число заполненных клеток опорного плана равно n+m–1, то система (7.12) с n + m неизвестными содержит n + m – l уравнений.

Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например a₁ = 0, и найти последовательно из уравнений (7.12) значения остальных неизвестных.

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

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

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

Для этого рассматривают все свободные клетки, для которых , и среди данных чисел выбирают максимальное.

Клетку, которой это число соответствует, следует заполнить.

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

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

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

При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл.

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

Это перемещение производят по следующим правилам:

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

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

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

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

При сдвиге по циклу пересчёта число занятых клеток остаётся неизменным и равным n + m – 1.

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

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

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

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

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

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

1. Находят опорный план.

При этом число заполненных клеток должно быть равным n + m – 1.

2. Находят потенциалы b _j и a _i соответственно пунктов назначения и отправления из соотношения  для заполненных клеток.

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

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

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

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

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

Таблица 7.4

Исходные данные задачи

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

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

При опорном плане стоимость перевозок составляет величину

S = 1×30 + 2×20 + 10×3 + 10×1 + 10×5 + 10×4 = 200.

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

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

 

 

Полагая a₁  = 0, находим

 

b₁ = 1,  b₂ = 2,  a₂ = – 1,  b₃ = 0,  b₄ = 4,  a₃ = 0.

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

Найденные числа записываем в свободные клетки табл. 7.5.

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

Наибольшим среди положительных чисел D_ij  являются D₁₄ = 3, поэтому для данной свободной клетки строим цикл пересчёта (табл. 7.5) и производим сдвиг по этому циклу.

Наименьшее из чисел в минусовых клетках равно 10.

Клетка, в которой находится это число, становится свободной в новой табл. 7.5.

Таблица 7.5

Промежуточные результаты решения транспортной задачи

 

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	1 30	2  (–) 20	4  ( –4 )	1 (+) ( + 3)	50
A2	2   ( 0 )	3  (+) 10	1 10	5 (–) 10	30
A3	3  ( –2 )	2  ( 0 )	4 ( –4 )	4 10	10
Потребности	30	30	10	20	90

 

Другие числа в табл. 7.5 получаются так: к числу 10, стоящему в плюсовой клетке табл.7.5, добавим 10 и вычтем 10 из числа 20, находящегося в минусовой клетке табл. 7.5. Клетка на пересечении строки A₂ и столбца B₄ становится свободной.

После этих преобразований получаем (табл. 7.6) новый опорный план. Этот план проверяем на оптимальность.

Снова находим потенциалы пунктов отправления и назначения.

Для этого составляем следующую систему уравнений:

Полагаем a₁ = 0, получаем

b₁ = b₄ = 1, b₂ = 2, b₃ = 0, a₃ = –3, a₂ = –1.

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

Имеем:

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

S = 1×30 + 2×0 + 1×10 + 3×20 + 1×10 + 4×10 = 170.

Поэтому переходим к новому опорному плану (табл. 7.7).

Таблица 7.6

Новый опорный план решения транспортной задачи

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	1 30	2   (–) 10	4 ( –2 )	1 (+) 10	50
A2	2   ( 0 )	3 20	1 10	5 (–3)	30
A3	3  ( +1 )	2  (+3)	4 ( –1 )	4 (–) 10	10
Потребности	30	30	10	20	90

 

Таблица 7.7

Улучшенный опорный план решения транспортной задачи

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	1 30	2 (0)	4 (–4)	1 20	50
A2	2  (0)	3 20	1 10	5 (–3)	30
A3	3 (–2)	2 10	4 (–4)	4 (–3)	10
Потребности	30	30	10	20	90

 

Новые потенциалы: a₁ = a₃ = 0, a₂ = –1, b₁ = 1, b₂ = 2, b₃ = 0, b₄ = 4.

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

Следовательно, получен оптимальный план:

.

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

S = 1×30 + 2×0 + 1×20 + 3×20 + 1×10 + 2×10 = 140.