Задачи линейного программирования. _Готовое 84-04-3. Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15

• Название: Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15
• Анкор: Задачи линейного программирования
• Дата: 20.04.2022
• Размер: 109.17 Kb.
• Имя файла: _Готовое 84-04-3.docx
• Тип: Задача; #486594
• страница: 4 из 5

Задача 4

На три базы А1, А2, А3 производиться поставка однородного груза в количестве: 220 тонн на базу А1; 180 тонн на базу А2; 200 тонн на базу А3. Полученный груз требуется перевезти в пять пунктов в количестве: 60 тонн в пункт ; 180 тонн в пункт ; 160 тонн в пункт ; 50 тонн в пункт ; 150 тонн в пункт . Составьте оптимальный план перевозок. Стоимость перевозки груза в соответствующий пункт приведена в матрице C:

.
Решение:

По условию задачи составим матрицу перевозок.

	B1	B2	B3	B4	B5	Запасы
A1	13	10	6	11	3	220
A2	7	4	2	12	13	180
A3	14	8	5	9	17	200
Потребности	60	180	160	50	150

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

∑a = 220 + 180 + 200 = 600

∑b = 60 + 180 + 160 + 50 + 150 = 600

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

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

	B1	B2	B3	B4	B5	Запасы
A1	13	10	6	11	3	220
A2	7	4	2	12	13	180
A3	14	8	5	9	17	200
Потребности	60	180	160	50	150	600

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

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

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

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

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

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

x₂₃ = min(180,160) = 160.

13	10	x	11	3	220
7	4	2	12	13	180 - 160 = 20
14	8	x	9	17	200
60	180	160 - 160 = 0	50	150

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

x₁₅ = min(220,150) = 150.

13	10	x	11	3	220 - 150 = 70
7	4	2	12	x	20
14	8	x	9	x	200
60	180	0	50	150 - 150 = 0

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

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

13	10	x	11	3	70
x	4	2	x	x	20 - 20 = 0
14	8	x	9	x	200
60	180 - 20 = 160	0	50	0

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

x₃₂ = min(200,160) = 160.

13	x	x	11	3	70
x	4	2	x	x	0
14	8	x	9	x	200 - 160 = 40
60	160 - 160 = 0	0	50	0

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

x₃₄ = min(40,50) = 40.

13	x	x	11	3	70
x	4	2	x	x	0
x	8	x	9	x	40 - 40 = 0
60	0	0	50 - 40 = 10	0

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

x₁₄ = min(70,10) = 10.

13	x	x	11	3	70 - 10 = 60
x	4	2	x	x	0
x	8	x	9	x	0
60	0	0	10 - 10 = 0	0

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

x₁₁ = min(60,60) = 60.

13	x	x	11	3	60 - 60 = 0
x	4	2	x	x	0
x	8	x	9	x	0
60 - 60 = 0	0	0	0	0

	B1	B2	B3	B4	B5	Запасы
A1	13[60]	10	6	11[10]	3[150]	220
A2	7	4[20]	2[160]	12	13	180
A3	14	8[160]	5	9[40]	17	200
Потребности	60	180	160	50	150

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

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

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

F(x) = 13*60 + 11*10 + 3*150 + 4*20 + 2*160 + 8*160 + 9*40 = 3380 ус. ед.