Тема: Решение транспортной задачи средствами ЭТ Excel
Цель:
1. Ознакомиться с математической постановкой транспортной задачи и задачи оптимального назначения
2. Освоить порядок решение задачи средствами ЭТ Excel
3. Научиться анализировать полученные оптимальные решения
Теоретические сведения
1.1 Транспортная задача
Постановка транспортной задачи:
Некоторый однородный продукт, сосредоточенный у М поставщиков в количестве ai (i = 1…. M) единиц соответственно, необходимо доставить N потребителям в количестве bj (j=1… N). Известна стоимость Сij перевозки единицы груза от i – го поставщика к j – ому потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.
Математическая модель:
Xij ¾ количество единиц груза
Целевая функция:
(5.1)
Система ограничений:
- все грузы вывезены
(5.2)
- все потребности удовлетворены
(5.3)
Граничные условия Xij ³ 0
Прежде чем решать транспортную задачу, необходимо сначала определить, к какому типу она принадлежит.
Типы моделей
1. Модель закрытая
(5.4)
2. Модель открытая
2.1. Суммарные запасы превышают суммарные потребности
(5.5)
Решение: Вводим фиктивного потребителя, потребности которого равны
(5.6)
2.2. Суммарные потребности превышают суммарные запасы
(5.7)
Решение: Вводим фиктивного поставщика, объем производства которого
равен
(5.8)
3. При решении транспортной задачи можно встретить случаи, когда необходимо применить метод блокирования клеток. Обычно вместо стоимости перевозки в блокируемой клетке таблицы исходных данных ставят знак ´, переменную, соответствующую данной клетке не включают в ограничения.
Рассмотрим несколько примеров.
Пример 1
Суммарный объем потребностей больше суммарного объема производства. Потребности некоторых потребителей обязательно должны быть удовлетворены полностью.
Решение:
- Ввести фиктивного поставщика
- Стоимость перевозки от фиктивного поставщика к потребителям, потребности которых следует удовлетворить, установить значительно большими любой из стоимости перевозок решаемой задачи или заблокировать эти клетки .
Пример 2
Суммарный объем производства больше суммарного объема потребностей. От некоторых поставщиков нужно вывести всю продукцию.
Решение:
- Ввести фиктивного потребителя
- Стоимость перевозки от поставщика к фиктивному потребителю, установить значительно большими любой из стоимости перевозок решаемой задачи или заблокировать эти клетки .
Пример 3
Груз от поставщика, по каким – то причинам не может быть направлен одному из потребителей.
Решение: Заблокировать клетки
1.2 Задача оптимального назначения
Частным случаем транспортной задачи является задача оптимального назначения. Постановка задачи:
Пусть, имеются М лиц ai (i=1…M), которые могут выполнять bj (j=1…M) видов различных работ. Известна производительность i – го лица при выполнении j – ой работы Сij. Необходимо определить, кого и на какую работу следует назначить, что бы добиться максимальной суммарной производительности при условии, что каждое лицо может быть назначено только на одну работу.
Математическая модель:
Xij ¾ назначение i – го лица на j ¾ ю работу.
Xij принимает значение “0” или “1”. (“0” – не назначен; “1” – назначен).
Целевая функция:
(5.9)
Система ограничений:
(5.10)
Граничные условия Xij ³0
Пример выполнения лабораторной работы
2.1 Постановка транспортной задачи
Составить план перевозки песка из пунктов отправления: песчаный карьер №1, железнодорожная товарная станция, речной грузовой порт, песчаный карьер №2, в пункты назначения ЖБИ №1, ЖБИ №2, ДСК, при котором затраты на перевозку будут минимальными; затраты на перевозку 1 т песка между пунктами отправления и назначения указаны в таблице исходных данных в км. Потребности ДСК должны быть удовлетворены полностью.
Математическая модель
Таблица 5.1 – Таблица исходных данных
Поставщик bj | Потребитель | Запас ai | ||
ЖБИ №1 | ЖБИ №2 | ДСК | ||
Песчаный карьер №1 | 11 x11 | x12 | x13 | |
Ж/д станция | x21 | x22 | x23 | |
Речной порт | x31 | x32 | ||
Песчаный карьер №1 | x41 | x42 | x43 | |
Фиктивный поставщик | x51 | x52 | ||
Заявки |
Определим тип модели.
Следовательно, модель открытого типа. Для решения задачи необходимо ввести фиктивного поставщика, а также учесть, что потребности ДСК должны быть удовлетворены полностью, запретив перевозку Фиктивный поставщик – ДСК.
Целевая функция:
W = 11 X11+15 X12+ 17 X13+ 12 X21+ 16 X22+ 14 X23+ 13 X31 +10 X32 +9 X33+ 14 X41+ 9 X42 + 11 X43 + 0 X51 + 0 X52 ® min
Система ограничений:
Ø все потребности удовлетворены
Ø все запасы вывезены
Граничные условия Xij ³0
Решение задачи
Решение транспортной задачи и задачи о назначении проводится по алгоритмам 1.1, 1.2, 1.3 из лабораторной работы № 1 «Решение задач линейного программирования средствами ЭТ Excel».
На рисунке 5.1 представлена форма для решения задачи с введенными в нее исходными данными. Результаты поиска решения приведены на рисунке 5.2.
Ответ:
x11= 110 x12=0 x13=0
x21= 40 x22=0 x23=160
x31= 0 x32=20 x33=60
x 41= 0 x42=100 x43=0
x51= 0 x52=50
Целевая функция: W=5680
Вывод:
Затраты на перевозку будут минимальными и составят 5680 тг, если перевезти по маршруту:
Песчаный карьера №1 ¾ ЖБИ №1 110 т песка
Ж/д станция ¾ ЖБИ №1 40 т песка
Ж/д станция ¾ ДСК 160 т песка
Речной порт ¾ ЖБИ №2 20 т песка
Речной порт ¾ ДСК 60 т песка
Песчаный карьер №2 ¾ ЖБИ №2 100 т песка
Потребности ДСК и ЖБИ №1 удовлетворены полностью, для ЖБИ №2 недопоставка составит 50 т песка.
Рисунок 5.1
Рисунок 5.2
Задание
- Составить и решить транспортную задачу открытой модели. Условие сформулировать так, чтобы при решении задачи использовать метод запрещения перевозок.
- Составить и решить задачу о назначении.
Требования к отчету по лабораторной работе
Отчет должен содержать:
1. Словесное описание условия задачи
2. Таблицу исходных данных
3. Математическую модель
4. Результаты решения задачи
5. Выводы по решению задачи
Лабораторная работа N 6