Задача 28

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

Поставщик	В1	В2	В3	Запас
А1	2	1	2	100
А2	5	7	6	200
А3	3	2	5	300
Потребности	150	150	300

РЕШЕНИЕ:

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x₁₁ – количество груза из 1-го склада к 1-у потребителю.

x₁₂ – количество груза из 1-го склада к 2-у потребителю.

x₁₃ – количество груза из 1-го склада к 3-у потребителю.

x₂₁ – количество груза из 2-го склада к 1-у потребителю.

x₂₂ – количество груза из 2-го склада к 2-у потребителю.

x₂₃ – количество груза из 2-го склада к 3-у потребителю.

x₃₁ – количество груза из 3-го склада к 1-у потребителю.

x₃₂ – количество груза из 3-го склада к 2-у потребителю.

x₃₃ – количество груза из 3-го склада к 3-у потребителю.

Ограничения по запасам:

x₁₁ + x₁₂ + x₁₃ ≤ 100 (для 1 базы)

x₂₁ + x₂₂ + x₂₃ ≤ 200 (для 2 базы)

x₃₁ + x₃₂ + x₃₃ ≤ 300 (для 3 базы)

Ограничения по потребностям:

x₁₁ + x₂₁ + x₃₁ = 150 (для 1-го потребителя.)

x₁₂ + x₂₂ + x₃₂ = 150 (для 2-го потребителя.)

x₁₃ + x₂₃ + x₃₃ = 300 (для 3-го потребителя.)

Целевая функция:

2x₁₁ + 1x₁₂ + 2x₁₃ + 5x₂₁ + 7x₂₂ + 6x₂₃ + 3x₃₁ + 2x₃₂ + 5x₃₃ → min

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

	1	2	3	Запасы
1	2	1	2	100
2	5	7	6	200
3	3	2	5	300
Потребности	150	150	300

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 100 + 200 + 300 = 600

∑b = 150 + 150 + 300 = 600

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

Занесем исходные данные в распределительную таблицу.

	1	2	3	Запасы
1	2	1	2	100
2	5	7	6	200
3	3	2	5	300
Потребности	150	150	300

Этап I. Поиск первого опорного плана.

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

План начинается заполняться с верхнего левого угла.

Искомый элемент равен c₁₁=2. Для этого элемента запасы равны 100, потребности 150. Поскольку минимальным является 100, то вычитаем его.

x₁₁ = min(100,150) = 100.

2	x	x	100 - 100 = 0
5	7	6	200
3	2	5	300
150 - 100 = 50	150	300

Искомый элемент равен c₂₁=5. Для этого элемента запасы равны 200, потребности 50. Поскольку минимальным является 50, то вычитаем его.

x₂₁ = min(200,50) = 50.

2	x	x	0
5	7	6	200 - 50 = 150
x	2	5	300
50 - 50 = 0	150	300

Искомый элемент равен c₂₂=7. Для этого элемента запасы равны 150, потребности 150. Поскольку минимальным является 150, то вычитаем его.

x₂₂ = min(150,150) = 150.

2	x	x	0
5	7	x	150 - 150 = 0
x	2	5	300
0	150 - 150 = 0	300

Искомый элемент равен c₃₃=5. Для этого элемента запасы равны 300, потребности 300. Поскольку минимальным является 300, то вычитаем его.

x₃₃ = min(300,300) = 300.

2	x	x	0
5	7	x	0
x	2	5	300 - 300 = 0
0	0	300 - 300 = 0

Далее, согласно алгоритму, ищем элементы среди не вычеркнутых.

2	1	2	100
5	7	6	200
3	2	5	300
150	150	300

Искомый элемент равен c₁₂=1, но т.к. ограничения выполнены, то x₁₂=0.

	1	2	3	Запасы
1	2[100]	1[0]	2	100
2	5[50]	7[150]	6	200
3	3	2	5[300]	300
Потребности	150	150	300

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

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*100 + 5*50 + 7*150 + 5*300 = 3000

ОТВЕТ:

Анализ оптимального плана.

Из 1-го склада необходимо весь груз направить к 3-у потребителю.

Из 2-го склада необходимо весь груз направить к 3-у потребителю.

Из 3-го склада необходимо груз направить к 1-у потребителю (150), к 2-у потребителю (150)

Задача имеет множество оптимальных планов, поскольку оценка для (3;3) равна 0.

Задача 29

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

Заказчики/пункты	В1	В2	В3	В4	В5	aj
А1	4	9	2	5	3	23
А2	4	6	2	1	8	25
А3	6	2	3	4	5	17
bi	14	10	16	10	15

Требуется: найти оптимальное решение транспортной задачи методом потенциалов.

РЕШЕНИЕ:

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

Ограничения для поставщиков:

Ограничения для потребителей:

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

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

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

В нашем случае:

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