Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Тамбовский Государственный Университет им. Г.Р. Державина

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

транспортная задача1.doc

Скачиваний:

Добавлен:

23.09.2019

Размер:

1.81 Mб

Скачать

☆

1 / 41 2 3 4 > Следующая >>>

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

Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственно и пункты потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех т пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-получателях:

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

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

При этом каждый потребитель получает нужное количество продукта:

и каждый поставщик отгружает весь произведенный им продукт:

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

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

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

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

Задача :

У поставщиков A₁ , A₂ , A₃ , A₄ , A₅ , находится соответственно 100 , 150 , 350 , 200 , 200 единиц однотипной продукции, которая должна быть доставлена потребителям B₁ , B₂ , B₃ , B₄ , B₅ в количествах 100 , 200 , 200 , 300 , 200 единиц соответственно.

Стоимость доставки единицы продукции от поставщика A₁ к указанным потребителям равна 4 , 3 , 5 , 2 , 3 ден.ед.

Стоимость доставки единицы продукции от поставщика A₂ к указанным потребителям равна 7 , 1 , 2 , 3 , 1 ден.ед.

Стоимость доставки единицы продукции от поставщика A₃ к указанным потребителям равна 9 , 2 , 4 , 5 , 6 ден.ед.

Стоимость доставки единицы продукции от поставщика A₄ к указанным потребителям равна 1 , 3 , 6 , 4 , 10 ден.ед.

Стоимость доставки единицы продукции от поставщика A₅ к указанным потребителям равна 5 , 8 , 15 , 6 , 15 ден.ед.

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

Решение :

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

-
	2

-
	3

100

A ₂

-
	7

-
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

-
	2

-
	4

-
	5

-
	6

350

A ₄

-
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₂B₂ и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₂ к потребителю B₂ наиболее рентабельный.

Запасы поставщика A₂ составляют 150 единиц продукции. Потребность потребителя B₂ составляет 200 единиц продукции.

От поставщика A₂ к потребителю B₂ будем доставлять min = { 150 , 200 } = 150 единиц продукции.

Разместим в ячейку A₂B₂ значение равное 200

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

-
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

-
	2

-
	4

-
	5

-
	6

350

A ₄

-
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₄B₁ и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₄ к потребителю B₁ наиболее рентабельный.

Запасы поставщика A₄ составляют 200 единиц продукции. Потребность потребителя B₁ составляет 100 единиц продукции.

От поставщика A₄ к потребителю B₁ будем доставлять min = { 200 , 100 } = 100 единиц продукции.

Разместим в ячейку A₄B₁ значение равное 100

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

-
	2

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

-
	2

-
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₁B₄ и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₁ к потребителю B₄ наиболее рентабельный.

Запасы поставщика A₁ составляют 100 единиц продукции. Потребность потребителя B₄ составляет 300 единиц продукции.

От поставщика A₁ к потребителю B₄ будем доставлять min = { 100 , 300 } = 100 единиц продукции.

Разместим в ячейку A₁B₄ значение равное 300

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

-
	2

-
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₃B₂ и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₂ наиболее рентабельный.

Запасы поставщика A₃ составляют 350 единиц продукции. Потребность потребителя B₂ составляет 50 единиц продукции.

От поставщика A₃ к потребителю B₂ будем доставлять min = { 350 , 50 } = 50 единиц продукции.

Разместим в ячейку A₃B₂ значение равное 50

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

50
	2

-
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₃B₃ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₃ составляют 300 единиц продукции. Потребность потребителя B₃ составляет 200 единиц продукции.

От поставщика A₃ к потребителю B₃ будем доставлять min = { 300 , 200 } = 200 единиц продукции.

Разместим в ячейку A₃B₃ значение равное 200

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

50
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

-
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₄B₄ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₄ к потребителю B₄ наиболее рентабельный.

Запасы поставщика A₄ составляют 100 единиц продукции. Потребность потребителя B₄ составляет 200 единиц продукции.

От поставщика A₄ к потребителю B₄ будем доставлять min = { 100 , 200 } = 100 единиц продукции.

Разместим в ячейку A₄B₄ значение равное 200

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

50
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₃B₄ и равен 5, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₄ наиболее рентабельный.

Запасы поставщика A₃ составляют 100 единиц продукции. Потребность потребителя B₄ составляет 100 единиц продукции.

От поставщика A₃ к потребителю B₄ будем доставлять 100 единиц продукции.

Разместим в ячейку A₃B₄ значение равное 100

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

50
	2

200
	4

100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

-
	15

200

Потребность

100

200

300

200

Минимальный элемент матрицы тарифов находится в ячейке A₅B₅ и равен 15, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₅ к потребителю B₅ наиболее рентабельный.

Запасы поставщика A₅ составляют 200 единиц продукции. Потребность потребителя B₅ составляет 200 единиц продукции.

От поставщика A₅ к потребителю B₅ будем доставлять 200 единиц продукции.

Разместим в ячейку A₅B₅ значение равное 200

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

-
	1

150

A ₃

-
	9

50
	2

200
	4

100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

200
	15

200

Потребность

100

200

300

200

Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

Количество базисных ячеек равно 8. Требуется, чтобы было 9.

В свободную ячейку A₂B₅ запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф. Будем считать, что от поставщика A₂ к потребителю B₅ доставляем 0 единиц продукции.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

0
	1

150

A ₃

-
	9

50
	2

200
	4

100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
	6

200
	15

200

Потребность

100

200

300

200

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

Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀ = 2 * 100 + 1 * 150 + 2 * 50 + 4 * 200 + 5 * 100 + 1 * 100 + 4 * 100 + 15 * 200 = 5250 ден. ед.

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

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

 Находим потенциалы поставщиков и потребителей для имеющегося решения.

 Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

 Находим новое решение, как минимум, не хуже предыдущего.

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

Шаг 1

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику A_i ставим в соответствие некоторое число - u_i, называемое потенциалом поставщика.

Каждому потребителю B_j ставим в соответствие некоторое число - v_j, называемое потенциалом потребителя.

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

(u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j)

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

Примем v₄ = 0.

v₄ + u₁ = c₁₄	v₄ + u₁ = 2	u₁ = 2 - 0 = 2
v₄ + u₃ = c₃₄	v₄ + u₃ = 5	u₃ = 5 - 0 = 5
v₄ + u₄ = c₄₄	v₄ + u₄ = 4	u₄ = 4 - 0 = 4
v₂ + u₃ = c₃₂	v₂ + u₃ = 2	v₂ = 2 - 5 = -3
v₃ + u₃ = c₃₃	v₃ + u₃ = 4	v₃ = 4 - 5 = -1
v₁ + u₄ = c₄₁	v₁ + u₄ = 1	v₁ = 1 - 4 = -3
v₂ + u₂ = c₂₂	v₂ + u₂ = 1	u₂ = 1 - ( -3 ) = 4
v₅ + u₂ = c₂₅	v₅ + u₂ = 1	v₅ = 1 - 4 = -3
v₅ + u₅ = c₅₅	v₅ + u₅ = 15	u₅ = 15 - ( -3 ) = 18

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

u ₁ = 2

A ₂

-
	7

150
	1

-
	2

-
	3

0
	1

u ₂ = 4

A ₃

-
	9

50
	2

200
	4

100
	5

-
	6

u ₃ = 5

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

u ₄ = 4

A ₅

-
	5

-
	8

-
	15

-
	6

200
	15

u ₅ = 18

V _i

v ₁ = -3

v ₂ = -3

v ₃ = -1

v ₄ = 0

v ₅ = -3

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

₁₁ = c₁₁ - ( u₁ + v₁ ) = 4 - ( 2 + ( -3 ) ) = 5

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
5	4

-
4	3

-
4	5

100
	2

-
4	3

u ₁ = 2

A ₂

-
6	7

150
	1

-
-1	2

-
-1	3

0
	1

u ₂ = 4

A ₃

-
7	9

50
	2

200
	4

100
	5

-
4	6

u ₃ = 5

A ₄

100
	1

-
2	3

-
3	6

100
	4

-
9	10

u ₄ = 4

A ₅

-
-10	5

-
-7	8

-
-2	15

-
-12	6

200
	15

u ₅ = 18

V _i

v ₁ = -3

v ₂ = -3

v ₃ = -1

v ₄ = 0

v ₅ = -3

₁₂ = c₁₂ - ( u₁ + v₂ ) = 3 - ( 2 + ( -3 ) ) = 4

₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 2 + ( -1 ) ) = 4

₁₅ = c₁₅ - ( u₁ + v₅ ) = 3 - ( 2 + ( -3 ) ) = 4

₂₁ = c₂₁ - ( u₂ + v₁ ) = 7 - ( 4 + ( -3 ) ) = 6

₂₃ = c₂₃ - ( u₂ + v₃ ) = 2 - ( 4 + ( -1 ) ) = -1

₂₄ = c₂₄ - ( u₂ + v₄ ) = 3 - ( 4 + 0 ) = -1

₃₁ = c₃₁ - ( u₃ + v₁ ) = 9 - ( 5 + ( -3 ) ) = 7

₃₅ = c₃₅ - ( u₃ + v₅ ) = 6 - ( 5 + ( -3 ) ) = 4

₄₂ = c₄₂ - ( u₄ + v₂ ) = 3 - ( 4 + ( -3 ) ) = 2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 6 - ( 4 + ( -1 ) ) = 3

₄₅ = c₄₅ - ( u₄ + v₅ ) = 10 - ( 4 + ( -3 ) ) = 9

₅₁ = c₅₁ - ( u₅ + v₁ ) = 5 - ( 18 + ( -3 ) ) = -10

₅₂ = c₅₂ - ( u₅ + v₂ ) = 8 - ( 18 + ( -3 ) ) = -7

₅₃ = c₅₃ - ( u₅ + v₃ ) = 15 - ( 18 + ( -1 ) ) = -2

₅₄ = c₅₄ - ( u₅ + v₄ ) = 6 - ( 18 + 0 ) = -12

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A₅B₄ ( ₅₄ =-12).

Построим цикл для выбранной ячейки:

Поставьте курсор мыши в выбранную свободную ячейку A₅B₄. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A₅B₄. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A₅B₄ :

A₅B₄ , A₅B₅ , A₂B₅ , A₂B₂ , A₃B₂ , A₃B₄

Пусть ячейка A₅B₄, для которой мы строили цикл, имеет порядковый номер один.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

0
	1

150

A ₃

-
	9

50
	2

200
	4

1100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
-12	6

200
	15

200

Потребность

100

200

300

200

Среди ячеек цикла A₅B₅ , A₂B₂ , A₃B₄ , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 200, 150, 100 } = 100

В данном случае, это ячейка A₃B₄.

Другими словами, из маршрутов достаки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A₃ к потребителю B₄, по которому доставляется меньше всего (100) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150
	1

-
	2

-
	3

0
	1

150

A ₃

-
	9

50
	2

200
	4

100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

-
-12	6

200
	15

200

Потребность

100

200

300

200

От ячеек цикла с четными номерами отнимает 100. К ячейкам с нечетными номерами прибавляем 100.

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A₅ к потребителю B₄. По данному маршруту доставим 100 единиц продукции, по цене доставки 6 за единицу продукции. Общие затраты увеличатся на 6 * 100 ден. ед.

Сократим поставку от поставщика A₅ к потребителю B₅ на 100 единиц продукции, по цене доставки 15 за единицу продукции. Общие затраты уменьшатся на 15 * 100 ден. ед.

От поставщика A₂ к потребителю B₅ дополнительно поставим 100 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 100 ден. ед.

Сократим поставку от поставщика A₂ к потребителю B₂ на 100 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты уменьшатся на 1 * 100 ден. ед.

От поставщика A₃ к потребителю B₂ дополнительно поставим 100 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 100 ден. ед.

По маршруту от поставщика A₃ к потребителю B₄ мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 5 * 100 ден. ед.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

150 - 100
	1

-
	2

-
	3

0 + 100
	1

150

A ₃

-
	9

50 + 100
	2

200
	4

100 - 100
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

+ 100
-12	6

200 - 100
	15

200

Потребность

100

200

300

200

Что в итоге?

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

6 * 100 - 15 * 100 + 1 * 100 - 1 * 100 + 2 * 100 - 5 * 100 = ( 6 - 15 + 1 - 1 + 2 - 5 ) * 100 = -12 * 100 ден. ед.

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

ГЛАВНОЕ : В тот момент, когда мы нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на ₅₄ * 100 = -12 * 100 = -1200 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S₀ = 5250 + ( - 1200 ) = 4050 ден. ед. .

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

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

ячейки A₂B₃, общая стоимость доставки всей продукции изменилась бы на ₂₃ * 150 = -1 * 150 = -150 ден. ед.
ячейки A₂B₄, общая стоимость доставки всей продукции изменилась бы на ₂₄ * 100 = -1 * 100 = -100 ден. ед.
ячейки A₅B₁, общая стоимость доставки всей продукции изменилась бы на ₅₁ * 100 = -10 * 100 = -1000 ден. ед.
ячейки A₅B₂, общая стоимость доставки всей продукции изменилась бы на ₅₂ * 150 = -7 * 150 = -1050 ден. ед.
ячейки A₅B₃, общая стоимость доставки всей продукции изменилась бы на ₅₃ * 150 = -2 * 150 = -300 ден. ед.

Ячейка A₃B₄ выйдет из базиса, мы перестали доставлять продукцию от поставщика A₃ к потребителю B₄

Ячейка A₅B₄ станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₅ к потребителю B₄ .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

100
	6

100
	15

200

Потребность

100

200

300

200

Шаг 2

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику A_i ставим в соответствие некоторое число - u_i, называемое потенциалом поставщика.

Каждому потребителю B_j ставим в соответствие некоторое число - v_j, называемое потенциалом потребителя.

(u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j)

Примем v₄ = 0.
v₄ + u₁ = c₁₄	v₄ + u₁ = 2	u₁ = 2 - 0 = 2
v₄ + u₄ = c₄₄	v₄ + u₄ = 4	u₄ = 4 - 0 = 4
v₄ + u₅ = c₅₄	v₄ + u₅ = 6	u₅ = 6 - 0 = 6
v₅ + u₅ = c₅₅	v₅ + u₅ = 15	v₅ = 15 - 6 = 9
v₅ + u₂ = c₂₅	v₅ + u₂ = 1	u₂ = 1 - 9 = -8
v₁ + u₄ = c₄₁	v₁ + u₄ = 1	v₁ = 1 - 4 = -3
v₂ + u₂ = c₂₂	v₂ + u₂ = 1	v₂ = 1 - ( -8 ) = 9
v₂ + u₃ = c₃₂	v₂ + u₃ = 2	u₃ = 2 - 9 = -7
v₃ + u₃ = c₃₃	v₃ + u₃ = 4	v₃ = 4 - ( -7 ) = 11

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
	3

u ₁ = 2

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

u ₂ = -8

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

u ₃ = -7

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

u ₄ = 4

A ₅

-
	5

-
	8

-
	15

100
	6

100
	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = 9

v ₃ = 11

v ₄ = 0

v ₅ = 9

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

₁₁ = c₁₁ - ( u₁ + v₁ ) = 4 - ( 2 + ( -3 ) ) = 5

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
5	4

-
-8	3

-
-8	5

100
	2

-
-8	3

u ₁ = 2

A ₂

-
18	7

50
	1

-
-1	2

-
11	3

100
	1

u ₂ = -8

A ₃

-
19	9

150
	2

200
	4

-
12	5

-
4	6

u ₃ = -7

A ₄

100
	1

-
-10	3

-
-9	6

100
	4

-
-3	10

u ₄ = 4

A ₅

-
2	5

-
-7	8

-
-2	15

100
	6

100
	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = 9

v ₃ = 11

v ₄ = 0

v ₅ = 9

₁₂ = c₁₂ - ( u₁ + v₂ ) = 3 - ( 2 + 9 ) = -8

₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 2 + 11 ) = -8

₁₅ = c₁₅ - ( u₁ + v₅ ) = 3 - ( 2 + 9 ) = -8

₂₁ = c₂₁ - ( u₂ + v₁ ) = 7 - ( -8 + ( -3 ) ) = 18

₂₃ = c₂₃ - ( u₂ + v₃ ) = 2 - ( -8 + 11 ) = -1

₂₄ = c₂₄ - ( u₂ + v₄ ) = 3 - ( -8 + 0 ) = 11

₃₁ = c₃₁ - ( u₃ + v₁ ) = 9 - ( -7 + ( -3 ) ) = 19

₃₄ = c₃₄ - ( u₃ + v₄ ) = 5 - ( -7 + 0 ) = 12

₃₅ = c₃₅ - ( u₃ + v₅ ) = 6 - ( -7 + 9 ) = 4

₄₂ = c₄₂ - ( u₄ + v₂ ) = 3 - ( 4 + 9 ) = -10

₄₃ = c₄₃ - ( u₄ + v₃ ) = 6 - ( 4 + 11 ) = -9

₄₅ = c₄₅ - ( u₄ + v₅ ) = 10 - ( 4 + 9 ) = -3

₅₁ = c₅₁ - ( u₅ + v₁ ) = 5 - ( 6 + ( -3 ) ) = 2

₅₂ = c₅₂ - ( u₅ + v₂ ) = 8 - ( 6 + 9 ) = -7

₅₃ = c₅₃ - ( u₅ + v₃ ) = 15 - ( 6 + 11 ) = -2

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A₁B₅ ( ₁₅ =-8).

Построим цикл для выбранной ячейки:

Поставьте курсор мыши в выбранную свободную ячейку A₁B₅. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A₁B₅. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A₁B₅ :

A₁B₅ , A₁B₄ , A₅B₄ , A₅B₅

Пусть ячейка A₁B₅, для которой мы строили цикл, имеет порядковый номер один.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
-8	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

100
	6

100
	15

200

Потребность

100

200

300

200

Среди ячеек цикла A₁B₄ , A₅B₅ , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 100, 100 } = 100

В данном случае, таких ячеек 2. Остановим свой выбор на ячейке A₅B₅, как обладающую наибольшим тарифом (15 ден.ед) среди 2.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100
	2

-
-8	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

100
	6

100
	15

200

Потребность

100

200

300

200

От ячеек цикла с четными номерами отнимает 100. К ячейкам с нечетными номерами прибавляем 100.

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A₁ к потребителю B₅. По данному маршруту доставим 100 единиц продукции, по цене доставки 3 за единицу продукции. Общие затраты увеличатся на 3 * 100 ден. ед.

Сократим поставку от поставщика A₁ к потребителю B₄ на 100 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты уменьшатся на 2 * 100 ден. ед.

От поставщика A₅ к потребителю B₄ дополнительно поставим 100 единиц продукции, по цене доставки 6 за единицу продукции. Общие затраты увеличатся на 6 * 100 ден. ед.

По маршруту от поставщика A₅ к потребителю B₅ мы полностью перестаем доставлять продукцию.

Общие затраты уменьшатся на 15 * 100 ден. ед.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

100 - 100
	2

+ 100
-8	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

100 + 100
	6

100 - 100
	15

200

Потребность

100

200

300

200

Что в итоге?

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

3 * 100 - 2 * 100 + 6 * 100 - 15 * 100 = ( 3 - 2 + 6 - 15 ) * 100 = -8 * 100 ден. ед.

ГЛАВНОЕ : В тот момент, когда мы нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на ₁₅ * 100 = -8 * 100 = -800 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S₀ = 4050 + ( - 800 ) = 3250 ден. ед. .

ячейки A₁B₂, общая стоимость доставки всей продукции изменилась бы на ₁₂ * 50 = -8 * 50 = -400 ден. ед.
ячейки A₁B₃, общая стоимость доставки всей продукции изменилась бы на ₁₃ * 50 = -8 * 50 = -400 ден. ед.
ячейки A₂B₃, общая стоимость доставки всей продукции изменилась бы на ₂₃ * 50 = -1 * 50 = -50 ден. ед.
ячейки A₄B₂, общая стоимость доставки всей продукции изменилась бы на ₄₂ * 50 = -10 * 50 = -500 ден. ед.
ячейки A₄B₃, общая стоимость доставки всей продукции изменилась бы на ₄₃ * 50 = -9 * 50 = -450 ден. ед.
ячейки A₄B₅, общая стоимость доставки всей продукции изменилась бы на ₄₅ * 100 = -3 * 100 = -300 ден. ед.
ячейки A₅B₂, общая стоимость доставки всей продукции изменилась бы на ₅₂ * 50 = -7 * 50 = -350 ден. ед.
ячейки A₅B₃, общая стоимость доставки всей продукции изменилась бы на ₅₃ * 50 = -2 * 50 = -100 ден. ед.

Ячейка A₅B₅ выйдет из базиса, мы перестали доставлять продукцию от поставщика A₅ к потребителю B₅

Ячейка A₁B₅ станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₁ к потребителю B₅ .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

0
	2

100
	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

200

Потребность

100

200

300

200

Шаг 3

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику A_i ставим в соответствие некоторое число - u_i, называемое потенциалом поставщика.

Каждому потребителю B_j ставим в соответствие некоторое число - v_j, называемое потенциалом потребителя.

(u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j)

Примем v₄ = 0.

v₄ + u₁ = c₁₄	v₄ + u₁ = 2	u₁ = 2 - 0 = 2
v₅ + u₁ = c₁₅	v₅ + u₁ = 3	v₅ = 3 - 2 = 1
v₅ + u₂ = c₂₅	v₅ + u₂ = 1	u₂ = 1 - 1 = 0
v₄ + u₄ = c₄₄	v₄ + u₄ = 4	u₄ = 4 - 0 = 4
v₄ + u₅ = c₅₄	v₄ + u₅ = 6	u₅ = 6 - 0 = 6
v₂ + u₂ = c₂₂	v₂ + u₂ = 1	v₂ = 1 - 0 = 1
v₂ + u₃ = c₃₂	v₂ + u₃ = 2	u₃ = 2 - 1 = 1
v₃ + u₃ = c₃₃	v₃ + u₃ = 4	v₃ = 4 - 1 = 3
v₁ + u₄ = c₄₁	v₁ + u₄ = 1	v₁ = 1 - 4 = -3

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

0
	2

100
	3

u ₁ = 2

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

u ₂ = 0

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

u ₃ = 1

A ₄

100
	1

-
	3

-
	6

100
	4

-
	10

u ₄ = 4

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = 1

v ₃ = 3

v ₄ = 0

v ₅ = 1

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

₁₁ = c₁₁ - ( u₁ + v₁ ) = 4 - ( 2 + ( -3 ) ) = 5

₁₂ = c₁₂ - ( u₁ + v₂ ) = 3 - ( 2 + 1 ) = 0

₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 2 + 3 ) = 0

₂₁ = c₂₁ - ( u₂ + v₁ ) = 7 - ( 0 + ( -3 ) ) = 10

₂₃ = c₂₃ - ( u₂ + v₃ ) = 2 - ( 0 + 3 ) = -1

₂₄ = c₂₄ - ( u₂ + v₄ ) = 3 - ( 0 + 0 ) = 3

₃₁ = c₃₁ - ( u₃ + v₁ ) = 9 - ( 1 + ( -3 ) ) = 11

₃₄ = c₃₄ - ( u₃ + v₄ ) = 5 - ( 1 + 0 ) = 4

₃₅ = c₃₅ - ( u₃ + v₅ ) = 6 - ( 1 + 1 ) = 4

₄₂ = c₄₂ - ( u₄ + v₂ ) = 3 - ( 4 + 1 ) = -2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 6 - ( 4 + 3 ) = -1

₄₅ = c₄₅ - ( u₄ + v₅ ) = 10 - ( 4 + 1 ) = 5

₅₁ = c₅₁ - ( u₅ + v₁ ) = 5 - ( 6 + ( -3 ) ) = 2

₅₂ = c₅₂ - ( u₅ + v₂ ) = 8 - ( 6 + 1 ) = 1

₅₃ = c₅₃ - ( u₅ + v₃ ) = 15 - ( 6 + 3 ) = 6

₅₅ = c₅₅ - ( u₅ + v₅ ) = 15 - ( 6 + 1 ) = 8

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
5	4

-
0	3

-
0	5

0
	2

100
	3

u ₁ = 2

A ₂

-
10	7

50
	1

-
-1	2

-
3	3

100
	1

u ₂ = 0

A ₃

-
11	9

150
	2

200
	4

-
4	5

-
4	6

u ₃ = 1

A ₄

100
	1

-
-2	3

-
-1	6

100
	4

-
5	10

u ₄ = 4

A ₅

-
2	5

-
1	8

-
6	15

200
	6

-
8	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = 1

v ₃ = 3

v ₄ = 0

v ₅ = 1

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A₄B₂ ( ₄₂ =-2).

Построим цикл для выбранной ячейки:

Поставьте курсор мыши в выбранную свободную ячейку A₄B₂. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A₄B₂. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки образующие цикл для свободной ячейки A₄B₂ :

A₄B₂ , A₄B₄ , A₁B₄ , A₁B₅ , A₂B₅ , A₂B₂

Пусть ячейка A₄B₂, для которой мы строили цикл, имеет порядковый номер один.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

0
	2

100
	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
-2	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

200

Потребность

100

200

300

200

Среди ячеек цикла A₄B₄ , A₁B₅ , A₂B₂ , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 100, 100, 50 } = 50

В данном случае, это ячейка A₂B₂.

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

0
	2

100
	3

100

A ₂

-
	7

50
	1

-
	2

-
	3

100
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

-
-2	3

-
	6

100
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

200

Потребность

100

200

300

200

От ячеек цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Что мы делаем?

Мы вводим новый маршрут доставки продукции от поставщика A₄ к потребителю B₂. По данному маршруту доставим 50 единиц продукции, по цене доставки 3 за единицу продукции. Общие затраты увеличатся на 3 * 50 ден. ед.

Сократим поставку от поставщика A₄ к потребителю B₄ на 50 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты уменьшатся на 4 * 50 ден. ед.

От поставщика A₁ к потребителю B₄ дополнительно поставим 50 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 50 ден. ед.

Сократим поставку от поставщика A₁ к потребителю B₅ на 50 единиц продукции, по цене доставки 3 за единицу продукции. Общие затраты уменьшатся на 3 * 50 ден. ед.

От поставщика A₂ к потребителю B₅ дополнительно поставим 50 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 50 ден. ед.

По маршруту от поставщика A₂ к потребителю B₂ мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 1 * 50 ден. ед.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

0 + 50
	2

100 - 50
	3

100

A ₂

-
	7

50 - 50
	1

-
	2

-
	3

100 + 50
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

+ 50
-2	3

-
	6

100 - 50
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

200

Потребность

100

200

300

200

Что в итоге?

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

3 * 50 - 4 * 50 + 2 * 50 - 3 * 50 + 1 * 50 - 1 * 50 = ( 3 - 4 + 2 - 3 + 1 - 1 ) * 50 = -2 * 50 ден. ед.

ГЛАВНОЕ : В тот момент, когда мы нашли ячеку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на ₄₂ * 50 = -2 * 50 = -100 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют S₀ = 3250 + ( - 100 ) = 3150 ден. ед. .

ячейки A₂B₃, общая стоимость доставки всей продукции изменилась бы на ₂₃ * 50 = -1 * 50 = -50 ден. ед.
ячейки A₄B₃, общая стоимость доставки всей продукции изменилась бы на ₄₃ * 50 = -1 * 50 = -50 ден. ед.

Ячейка A₂B₂ выйдет из базиса, мы перестали доставлять продукцию от поставщика A₂ к потребителю B₂

Ячейка A₄B₂ станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₄ к потребителю B₂ .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

50
	2

50
	3

100

A ₂

-
	7

-
	1

-
	2

-
	3

150
	1

150

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

350

A ₄

100
	1

50
	3

-
	6

50
	4

-
	10

200

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

200

Потребность

100

200

300

200

Шаг 4

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.

Каждому поставщику A_i ставим в соответствие некоторое число - u_i, называемое потенциалом поставщика.

Каждому потребителю B_j ставим в соответствие некоторое число - v_j, называемое потенциалом потребителя.

(u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j)

Примем v₄ = 0.
v₄ + u₁ = c₁₄	v₄ + u₁ = 2	u₁ = 2 - 0 = 2
v₅ + u₁ = c₁₅	v₅ + u₁ = 3	v₅ = 3 - 2 = 1
v₅ + u₂ = c₂₅	v₅ + u₂ = 1	u₂ = 1 - 1 = 0
v₄ + u₄ = c₄₄	v₄ + u₄ = 4	u₄ = 4 - 0 = 4
v₄ + u₅ = c₅₄	v₄ + u₅ = 6	u₅ = 6 - 0 = 6
v₁ + u₄ = c₄₁	v₁ + u₄ = 1	v₁ = 1 - 4 = -3
v₂ + u₄ = c₄₂	v₂ + u₄ = 3	v₂ = 3 - 4 = -1
v₂ + u₃ = c₃₂	v₂ + u₃ = 2	u₃ = 2 - ( -1 ) = 3
v₃ + u₃ = c₃₃	v₃ + u₃ = 4	v₃ = 4 - 3 = 1

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
	4

-
	3

-
	5

50
	2

50
	3

u ₁ = 2

A ₂

-
	7

-
	1

-
	2

-
	3

150
	1

u ₂ = 0

A ₃

-
	9

150
	2

200
	4

-
	5

-
	6

u ₃ = 3

A ₄

100
	1

50
	3

-
	6

50
	4

-
	10

u ₄ = 4

A ₅

-
	5

-
	8

-
	15

200
	6

-
	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = -1

v ₃ = 1

v ₄ = 0

v ₅ = 1

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

₁₁ = c₁₁ - ( u₁ + v₁ ) = 4 - ( 2 + ( -3 ) ) = 5

₁₂ = c₁₂ - ( u₁ + v₂ ) = 3 - ( 2 + ( -1 ) ) = 2

₁₃ = c₁₃ - ( u₁ + v₃ ) = 5 - ( 2 + 1 ) = 2

₂₁ = c₂₁ - ( u₂ + v₁ ) = 7 - ( 0 + ( -3 ) ) = 10

₂₂ = c₂₂ - ( u₂ + v₂ ) = 1 - ( 0 + ( -1 ) ) = 2

₂₃ = c₂₃ - ( u₂ + v₃ ) = 2 - ( 0 + 1 ) = 1

₂₄ = c₂₄ - ( u₂ + v₄ ) = 3 - ( 0 + 0 ) = 3

₃₁ = c₃₁ - ( u₃ + v₁ ) = 9 - ( 3 + ( -3 ) ) = 9

₃₄ = c₃₄ - ( u₃ + v₄ ) = 5 - ( 3 + 0 ) = 2

₃₅ = c₃₅ - ( u₃ + v₅ ) = 6 - ( 3 + 1 ) = 2

₄₃ = c₄₃ - ( u₄ + v₃ ) = 6 - ( 4 + 1 ) = 1

₄₅ = c₄₅ - ( u₄ + v₅ ) = 10 - ( 4 + 1 ) = 5

₅₁ = c₅₁ - ( u₅ + v₁ ) = 5 - ( 6 + ( -3 ) ) = 2

₅₂ = c₅₂ - ( u₅ + v₂ ) = 8 - ( 6 + ( -1 ) ) = 3

₅₃ = c₅₃ - ( u₅ + v₃ ) = 15 - ( 6 + 1 ) = 8

₅₅ = c₅₅ - ( u₅ + v₅ ) = 15 - ( 6 + 1 ) = 8

Поставщик

Потребитель

U _j

B ₁

B ₂

B ₃

B ₄

B ₅

A ₁

-
5	4

-
2	3

-
2	5

50
	2

50
	3

u ₁ = 2

A ₂

-
10	7

-
2	1

-
1	2

-
3	3

150
	1

u ₂ = 0

A ₃

-
9	9

150
	2

200
	4

-
2	5

-
2	6

u ₃ = 3

A ₄

100
	1

50
	3

-
1	6

50
	4

-
5	10

u ₄ = 4

A ₅

-
2	5

-
3	8

-
8	15

200
	6

-
8	15

u ₅ = 6

V _i

v ₁ = -3

v ₂ = -1

v ₃ = 1

v ₄ = 0

v ₅ = 1

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

Ответ:

X _опт =	0	0	0	50	50
	0	0	0	0	150
	0	150	200	0	0
	100	50	0	50	0
	0	0	0	200	0

S_min = 2 * 50 + 3 * 50 + 1 * 150 + 2 * 150 + 4 * 200 + 1 * 100 + 3 * 50 + 4 * 50 + 6 * 200 = 3150

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

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

9.1. Постановка задачи

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины: - объем производства (запас) i-го поставщика, i=1, m ; - объем потребления (спрос) j-го потребителя, i=1, n ; - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

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

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

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

и суммарные потребности

совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой.

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

вводится фиктивный n+1 потребитель, потребности которого

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

вводится фиктивный m+1 поставщик, запасы которого

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

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

9.2 Основные свойство транспортной задачи

Математические модели любых транспортных задач ЛП обладают общими чертами, а именно,

1) коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);

3) коэффициенты в ограничениях принимают только два значения, это нули и единицы.

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

Теорема 1. Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

Доказательство. Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.

Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

Но в закрытой модели выполняется балансовое равенство

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

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

Теорема 2. Оптимальный план закрытой модели транспортной задачи существует всегда.

Доказательство. Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.

Покажем существование допустимого решения. Так как

суммарные запасы

совпадают с суммарными потребностями

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

Покажем ограниченность целевой функции.

Так как

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

1 / 41 2 3 4 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
07.02.201532.91 Кб753ТОПОГРАФИЧЕСКАЯ АНАТОМИЯ ВЕРХНЕЙ КОНЕЧНОСТИ.docx
#
22.04.2019119.24 Кб2ТОФМ шпоры.docx
#
19.08.2019121.86 Кб0Травма МПС.doc
#
18.11.201924.59 Кб0Транскрипция и правила чтения 2.docx
#
13.07.2019101.38 Кб1Транскрипция, правила чтения..doc
#
23.09.20191.81 Mб2транспортная задача1.doc
#
24.08.2019160.26 Кб2Требования к дипломным работам.doc
#
07.05.201940.65 Кб4труд. отн. ч.1.docx
#
19.08.2019147.97 Кб1туберкулез МПС.doc
#
14.04.201522.5 Кб65Туберкулез ЦНС.docx
#
28.10.2018536.06 Кб10ТУЛЬЧИНСКИЙ скр книга.DOC