Задача 25 (ошибка в условии)

Есть запасы однотипной продукции у поставщиков A1, A2, A3, A4.

Существует потребность в этой продукции B1, B2, B3.

Стоимость доставки единицы продукции от поставщиков к потребителям представлена в таблице.

Поставщик	Потребитель Запас			Запас
	В1	В2	В2
А1	6	5	2 200	250
А2	3	7	4 100	100
А3	7	8	1 100	80
А4	2	2	3 150	120
Потребность	150	150	250

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

Задача 26

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

	Потребитель				Запас
	В1	В2	В3	В4
А1	7	8	1	2	200
А2	4	5	9	8	180
А3	9	2	3	6	190
Потребность	150	130	150	140

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

РЕШЕНИЕ:

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

Переменные:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7x₁₁ + 8x₁₂ + 1x₁₃ + 2x₁₄ + 4x₂₁ + 5x₂₂ + 9x₂₃ + 8x₂₄ + 9x₃₁ + 2x₃₂ + 3x₃₃ + 6x₃₄ → min

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

	1	2	3	4	Запасы
1	7	8	1	2	200
2	4	5	9	8	180
3	9	2	3	6	190
Потребности	150	130	150	140

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

∑a = 200 + 180 + 190 = 570

∑b = 150 + 130 + 150 + 140 = 570

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

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

	1	2	3	4	Запасы
1	7	8	1	2	200
2	4	5	9	8	180
3	9	2	3	6	190
Потребности	150	130	150	140

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

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

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

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

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

7	8	1	2	200 - 150 = 50
x	5	9	8	180
x	2	3	6	190
150 - 150 = 0	130	150	140

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

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

7	8	x	x	50 - 50 = 0
x	5	9	8	180
x	2	3	6	190
0	130 - 50 = 80	150	140

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

x₂₂ = min(180,80) = 80.

7	8	x	x	0
x	5	9	8	180 - 80 = 100
x	x	3	6	190
0	80 - 80 = 0	150	140

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

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

7	8	x	x	0
x	5	9	x	100 - 100 = 0
x	x	3	6	190
0	0	150 - 100 = 50	140

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

x₃₃ = min(190,50) = 50.

7	8	x	x	0
x	5	9	x	0
x	x	3	6	190 - 50 = 140
0	0	50 - 50 = 0	140

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

x₃₄ = min(140,140) = 140.

7	8	x	x	0
x	5	9	x	0
x	x	3	6	140 - 140 = 0
0	0	0	140 - 140 = 0

	1	2	3	4	Запасы
1	7[150]	8[50]	1	2	200
2	4	5[80]	9[100]	8	180
3	9	2	3[50]	6[140]	190
Потребности	150	130	150	140

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

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

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

F(x) = 7*150 + 8*50 + 5*80 + 9*100 + 3*50 + 6*140 = 3740

ОТВЕТ:

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

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

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

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

Задача 27

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

	1	2	3	4	Запасы
1	1	2	4	3	6
2	4	3	8	5	8
3	2	7	6	3	10
Потребности	4	6	8	8

РЕШЕНИЕ:

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

Переменные:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	1	2	3	4	Запасы
1	1	2	4	3	6
2	4	3	8	5	8
3	2	7	6	3	10
Потребности	4	6	8	8

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

∑a = 6 + 8 + 10 = 24

∑b = 4 + 6 + 8 + 8 = 26

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 2 (24—26). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю.

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

	1	2	3	4	Запасы
1	1	2	4	3	6
2	4	3	8	5	8
3	2	7	6	3	10
4	0	0	0	0	2
Потребности	4	6	8	8

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

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

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

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

x₁₁ = min(6,4) = 4.

1	2	4	3	6 - 4 = 2
x	3	8	5	8
x	7	6	3	10
x	0	0	0	2
4 - 4 = 0	6	8	8

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

x₁₂ = min(2,6) = 2.

1	2	x	x	2 - 2 = 0
x	3	8	5	8
x	7	6	3	10
x	0	0	0	2
0	6 - 2 = 4	8	8

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

x₂₂ = min(8,4) = 4.

1	2	x	x	0
x	3	8	5	8 - 4 = 4
x	x	6	3	10
x	x	0	0	2
0	4 - 4 = 0	8	8

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

x₂₃ = min(4,8) = 4.

1	2	x	x	0
x	3	8	x	4 - 4 = 0
x	x	6	3	10
x	x	0	0	2
0	0	8 - 4 = 4	8

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

x₃₃ = min(10,4) = 4.

1	2	x	x	0
x	3	8	x	0
x	x	6	3	10 - 4 = 6
x	x	x	0	2
0	0	4 - 4 = 0	8

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

x₃₄ = min(6,8) = 6.

1	2	x	x	0
x	3	8	x	0
x	x	6	3	6 - 6 = 0
x	x	x	0	2
0	0	0	8 - 6 = 2

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

x₄₄ = min(2,2) = 2.

1	2	x	x	0
x	3	8	x	0
x	x	6	3	0
x	x	x	0	2 - 2 = 0
0	0	0	2 - 2 = 0

	1	2	3	4	Запасы
1	1[4]	2[2]	4	3	6
2	4	3[4]	8[4]	5	8
3	2	7	6[4]	3[6]	10
4	0	0	0	0[2]	2
Потребности	4	6	8	8

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

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

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

F(x) = 1*4 + 2*2 + 3*4 + 8*4 + 6*4 + 3*6 + 0*2 = 94

ОТВЕТ:

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

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

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

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

Потребность 3-го потребителя остается неудовлетворенной на 2 ед.

Оптимальный план является вырожденным, так как базисная переменная x₄₃=0.

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