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

U₃+V₄=6. Поскольку U₃=–4, –4+V₄=6, следовательно, V₄=10 руб./кг

При компьютерной реализации удобно использовать рекурсию: взаимный вызов двух функций, которые отрабатывают алгоритм, соответственно, по строкам и по столбцам. Если на предыдущем шаге 4 (в разделе «Проверка плана на вырожденность»)  в базис была введена случайная не занятая ячейка (без проверки ее на ацикличность), то вычисление u и v может дать сбой, и в этом случае случайный выбор вводимой в базис нулевой ячейки на предыдущем шаге 4 следует повторить.

 

3.8.6. Проверка решения на оптимальность

Для всех не занятых ячеек (с нулевым объемом перевозки) вычисляют оценки клеток распределительной  таблицы Δij по формуле Δ_ij = С_ij – U_i – V_j, где U_i и V_j берутся из вычислений, выполненных в разделе выше (здесь они вписаны в заголовки таблицы).

Для всех занятых ячеек (с ненулевыми объемами перевозки, отмечены зеленым цветом) полагают Δ_ij=0, поскольку на следующем шаге нам потребуется значение с минимальной оценкой в незанятых ячейках.

 

	V1=2	V2=3	V3=6	V4=10
U1=0	Δ11=0	Δ12=0	Δ13 = 2–0–6 = –4	Δ14=4–0–10 = –6
U2=–1	Δ21=3–(–1)–2 = 2	Δ22=0	Δ23=0	Δ24=1–(–1)–10 = –8
U3=–4	Δ31=4–(–4)–2 = 6	Δ32=3–(–4)–3 = 4	Δ33=0	Δ34=0

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

В данном примере есть отрицательные значения. Наличие  отрицательных значений Δ_ij означает, что решение не оптимально.

 

	B1	B2	B3	B4
A1	Δ11=0	Δ12=0	Δ13=–4	Δ14=–6
A2	Δ21=2	Δ22=0	Δ23=0	Δ24=–8
A3	Δ31=6	Δ32=4	Δ33=0	Δ34=0

 

Наименьшее отрицательное значение Δ₂₄=–8 (начальная вершина для цикла перераспределения поставок, о котором см. ниже) отмечено красным цветом. Если одинаковых отрицательных значений несколько, то берется любое.

3.8.7. Построение цикла

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

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

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

 

	B1, 20 кг	B2, 30 кг	B3, 30 кг	B4, 10 кг
A1, 30 кг	X11=20 кг	Х12=10 кг
A2, 40 кг		Х22=20 кг	(*) Х23=20 кг	(*)
A3, 20 кг			(*) Х33=10 кг	(*) Х44=10 кг

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

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

3.8.8. Перераспределение поставок по циклу

«Красной» ячейке цикла  присваиваем знак (+), следующей по циклу (начать двигаться можно в  любом направлении) — знак (–), следующей ячейке цикла — опять (+) и так далее. Находим минимальную поставку по отмеченным знаком (–) вершинам цикла и обозначаем ее θ. Эта вершина цикла Х₃₄=10 кг помечена желтым цветом. Значение θ вычитаем из вершин цикла, которые помечены знаком (–) и прибавляем его к вершинам цикла, которые помечены знаком (+).

 

	B1, 20 кг	B2, 30 кг	B3, 30 кг	B4, 10 кг
A1, 30 кг	X11=20 кг	Х12=10 кг
A2, 40 кг		Х22=20 кг	(–) Х23=20 кг	(+)
A3, 20 кг			(+) Х33=10 кг	(–) Х34=10 кг

 

3.8.9. Зацикливание решения

Поскольку алгоритм является циклическим (итерационным), переходим  к пункту 1.

Примечание: есть опасность, что алгоритм впадет в бесконечный цикл из-за вырожденности или каких-либо ошибок реализации, поэтому полезно предусмотреть проверку на максимальное число шагов или максимальное время, которое будет исполняться программа (например, при поиске решения в Microsoft Excel эти параметры вынесены в пользовательские настройки). Впрочем, по мнению Данцига, те меры, которые можно предпринять для исключения вырожденности приводят к успеху в 100 % случаев. Для подстраховки можно применить метод Фогеля, который не склонен «впадать» в бесконечные циклы, и выдает более или менее приближенное к оптимальному решение за ограниченное число шагов.

3.8.10. Получение результата

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

 

3.9. Решение транспортной задачи симплекс-методом

 

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

Например, для транспортной задачи с 3 поставщиками и 5 потребителями (цены перевозки Cij — на пересечении строк и столбцов) вида:

	Потребитель B1,  потребность 20 шт.	Потребитель B2,  потребность 12 шт.	Потребитель B3,  потребность 5 шт.	Потребитель B4,  потребность 8 шт.	Потребитель B4,  потребность 15 шт.
Поставщик A1,  запас 15 шт.	С11=1	С12=0	С13=3	С14=4	С15=2
Поставщик A2,  запас 25 шт.	С21=5	С22=1	С23=2	С24=3	С25=3
Поставщик A3,  запас 20 шт.	С31=4	С32=8	С33=1	С34=4	С35=3

Можно построить следующую систему линейных уравнений:

x11

+x12

+x13

+x14

+x15

=15

x21

+x22

+x23

+x24

+x25

=25

x31

+x32

+x33

+x34

+x35

=20

x11

+x21

+x31

=20

x12

+x22

+x32

=12

x13

+x23

+x33

=5

x14

+x24

+x34

=8

x15

+x25

+x35

=15

1x11

+0x12

+3x13

+4x14

+2x15

+5x21

+1x22

+2x23

+3x24

+3x25

+4x31

+8x32

+1x33

+4x34

+3x35

=z

 

 

 

 

 

4. Реализация программы

 

В рамках данной работы была создана программа, находящая решение  транспортной задачи методом наименьших значений. Для реализации данной программы была использована среда Borland C++ Builder. В сравнении с разобранным в пункте 3.6. примером программа выдаёт лучший результат (в примере – 210р, с помощью программы – 170р.). Это происходит потому, что в разобранном примере получены несколько значений, равных 2р/кг, по алгоритму необходимо выбрать любое из них. В программе вычисление ведётся относительно значения, расположенного в 1-м столбце таблицы, в примере – относительно 3-го столбца. Этим обусловлено получение различных результатов. Листинг кода данной программы представлен в Приложении A.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список  использованных источников

 

1. Данциг, Дж. «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 

2. Гасс, С. Линейное программирование (методы и приложения) / Пер. с англ. Гольштейна Е. Г. и Сушкевича М. И., под ред. Юдина Д. Б. Государственное издательство физико-математической литературы, Москва, 1961

3. Самаров, К. Л.  Учебное пособие для студентов. Транспортная задача. Москва, СВАО, Учебный центр «Резольвента»

4. Лунгу, К. Н. Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.

5. Томас Х. Кормен и др. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.

6. ru.wikipedia.org

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ A

 

Листинг программного кода

 

 

void __fastcall TForm1::Button1Click(TObject *Sender)

{

        double a[3];    //запасы

        double b[4];    //потребности

        double c[3][4]; //стоимость доставки