 | Сервис для решения задач по линейному программированиюи другие интересные типовые задачи |
English |
Пример №1. Решение транспортной задачи линейного программирования.
Метод наименьшей стоимости (сбалансированная задача)
Данное решение сделано калькулятором, представленным на сайте.
Пример №2. Транспортная задача. Метод наименьшей стоимости (фиктивный поставщик)
Пример №3. Транспортная задача. Метод наименьшей стоимости (фиктивный потребитель)
Пример №4. Транспортная задача. Метод северо-западного угла (сбалансированная задача)
Пример №5. Транспортная задача. Метод северо-западного угла (фиктивный поставщик)
Пример №6. Транспортная задача. Метод северо-западного угла (фиктивный потребитель)
Пример №3. Транспортная задача. Метод наименьшей стоимости (фиктивный потребитель)
Пример №4. Транспортная задача. Метод северо-западного угла (сбалансированная задача)
Пример №5. Транспортная задача. Метод северо-западного угла (фиктивный поставщик)
Пример №6. Транспортная задача. Метод северо-западного угла (фиктивный потребитель)
Задача:
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
|
1
| 10 |
| A 2 |
3
|
2
|
4
| 20 |
| A 3 |
4
|
1
|
2
| 30 |
| Потребность | 15 | 20 | 25 | |
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Решение:
Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.
Проверим.
Запасы поставщиков: 10 + 20 + 30 = 60 единиц продукции.
Потребность потребителей: 15 + 20 + 25 = 60 единиц продукции.
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.
Проверим.
Запасы поставщиков: 10 + 20 + 30 = 60 единиц продукции.
Потребность потребителей: 15 + 20 + 25 = 60 единиц продукции.
Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.
Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.
Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
|
1
| 10 |
| A 2 |
3
|
2
|
4
| 20 |
| A 3 |
4
| ?
1
|
2
| 30 |
| Потребность | 15 | 20 | 25 | |
20 = min { 20, 30 }
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| ?
1
| 10 |
| A 2 |
3
|
2
|
4
| 20 |
| A 3 |
4
| 20
1
|
2
| 30 10 |
| Потребность | 15 | 20 нет | 25 | |
10 = min { 25, 10 }
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 нет |
| A 2 |
3
|
2
|
4
| 20 |
| A 3 |
4
| 20
1
| ?
2
| 30 10 |
| Потребность | 15 | 20 нет | 25 15 | |
10 = min { 15, 10 }
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 нет |
| A 2 | ?
3
|
2
|
4
| 20 |
| A 3 |
4
| 20
1
| 10
2
| 30 10 нет |
| Потребность | 15 | 20 нет | 25 15 5 | |
15 = min { 15, 20 }
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 нет |
| A 2 | 15
3
|
2
| ?
4
| 20 5 |
| A 3 |
4
| 20
1
| 10
2
| 30 10 нет |
| Потребность | 15 нет | 20 нет | 25 15 5 | |
5 = min { 5, 5 }
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 нет |
| A 2 | 15
3
|
2
| 5
4
| 20 5 нет |
| A 3 |
4
| 20
1
| 10
2
| 30 10 нет |
| Потребность | 15 нет | 20 нет | 25 15 5 нет | |
Стоимость доставки продукции, для начального решения, не сложно посчитать.
10*1 + 15*3 + 5*4 + 20*1 + 10*2 = 115 ден. ед.
Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число U i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число V j , называемое потенциалом потребителя.
Каждому потребителю B j ставим в соответствие некоторое число V j , называемое потенциалом потребителя.
Для задействованного маршрута:
потенциал поставщика + потенциал потребителя = тариф задействованного маршрута.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
потенциал поставщика + потенциал потребителя = тариф задействованного маршрута.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
|
|
||||||||||||||||||||||||||||||||||||||||||
Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?
|
|||||||||||||||||||||||||||||||||||||||||||
Есть отрицательная оценка. Следовательно, возможно получить новое решение, как минимум, не хуже имеющегося.
ШАГ №1.
Выберем ячейку A2B2, ее оценка отрицательная.
Пожалуйста, поставьте курсор мыши в выбранную ячейку A2B2
Используя только горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку A2B2
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки
(см. выделенные ячейки в таблице ниже). Он единственный. Направление обхода не имеет значения.
Используя только горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией заполненные ячейки так, чтобы вернуться в исходную ячейку A2B2
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной ячейки
(см. выделенные ячейки в таблице ниже). Он единственный. Направление обхода не имеет значения.
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 |
| A 2 | 15
3
|
-1
2
| 5
4
| 20 |
| A 3 |
4
| 20
1
| 10
2
| 30 |
| Потребность | 15 | 20 | 25 | |
5 = min { 5, 20 } ?
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 |
| A 2 | 15
3
|
-1
2
| 5
4
| 20 |
| A 3 |
4
| 20
1
| 10
2
| 30 |
| Потребность | 15 | 20 | 25 | |
Данное преобразование не изменит баланса.
А вот общая стоимость доставки продукции изменится на величину:
2 * 5 - 4 * 5 + 2 * 5 - 1 * 5 = ( 2 - 4 + 2 - 1 ) * 5 = -1 * 5 ден. ед.
Вы правильно заметили, что -1 * 5 = Δ22 * 5 ?
А вот общая стоимость доставки продукции изменится на величину:
2 * 5 - 4 * 5 + 2 * 5 - 1 * 5 = ( 2 - 4 + 2 - 1 ) * 5 = -1 * 5 ден. ед.
Вы правильно заметили, что -1 * 5 = Δ22 * 5 ?
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 |
| A 2 | 15
3
| +5
-1
2
| 5 - 5
4
| 20 |
| A 3 |
4
| 20 - 5
1
| 10 + 5
2
| 30 |
| Потребность | 15 | 20 | 25 | |
Получили новое решение. ?
| Поставщик | Потребитель | Запас | ||
| B 1 | B 2 | B 3 | ||
| A 1 |
5
|
3
| 10
1
| 10 |
| A 2 | 15
3
| 5
2
|
4
| 20 |
| A 3 |
4
| 15
1
| 15
2
| 30 |
| Потребность | 15 | 20 | 25 | |
Общую сумму доставки продукции, для данного решения, легко посчитать.
S = 115 + Δ22 * 5 = 115 -1 * 5 = 110 ден. ед.
Полученное решение является оптимальным?
Проверим.
Каждому поставщику A i ставим в соответствие некоторое число U i , называемое потенциалом поставщика.
Каждому потребителю B j ставим в соответствие некоторое число V j , называемое потенциалом потребителя.
Каждому потребителю B j ставим в соответствие некоторое число V j , называемое потенциалом потребителя.
Для задействованного маршрута:
потенциал поставщика + потенциал потребителя = тариф задействованного маршрута.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
потенциал поставщика + потенциал потребителя = тариф задействованного маршрута.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u2 = 0.
|
|
||||||||||||||||||||||||||||||||||||||||||
Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?
|
|||||||||||||||||||||||||||||||||||||||||||
Нет отрицательных оценок. Следовательно, уменьшить общую стоимость доставки продукции невозможно.
Ответ:X опт = |  | 0 | 0 | 10 |  | |
| 15 | 5 | 0 | ||||
| 0 | 15 | 15 |