Транспортная задача
На трех станциях отправления имеется соответственно 30, 50, и 20 ед. однородного груза, который нужно доставить в четыре пункта назначения согласно их потребностям. Эти данные, а также стоимость перевозки единицы груза от каждой станции отправления к каждому пункту назначения указаны в таблице. Составить план перевозок грузов, чтобы затраты на эти перевозки были минимальными.
| Пункты отправления | Запасы груза | Пункты назначения | |||
| 
| 
| 
| ||
| |||||
| |||||
| |||||
| Потребности |
Решение.
Этап 1.
Часто условие транспортной задачи оформляют матрицей:
Построим математическую модель транспортной задачи.
1. «Составить план перевозок грузов» - значит определить сколько, от куда и куда надо перевезти груза, чтобы достичь поставленной цели - «затраты на эти перевозки были минимальными». Введем управляющие переменные: 
- количество груза, перевозимого из пункта 
в пункт 
(
).
2. Стоимость этой перевозки составит 
. Тогда целевая функция - суммарные затраты, связанные с реализацией всего плана перевозок – запишется выражением:
в общем виде 
, где
в нашей задаче 
3. Для построения системы ограничений проверим, является ли задача сбалансированной.
Суммарная мощность поставщиков  ед
Суммарная мощность потребителей 
| 
|
Следовательно, условие сбалансированности не выполнено.
4. Запишем систему ограничений:
По потребителю: мощности поставщиков меньше мощности потребителей, следовательно, кто-то из потребителей получит груза меньше, чем его потребность 
.
Количество груза, которое потребитель действительно получит запишется выражением: 
. Так как это меньше, чем его потребность, ограничение будет иметь вид: 
.
Аналогично строятся ограничения по другим потребителям. Так как в задаче заранее не оговаривается, потребности какого потребителя не будут удовлетворены, знак 
поставим в ограничениях по всем потребителям. Получим систему ограничений по потребителю:
По поставщику: весь имеющийся на станции отправления груз будет вывезен (т.е. 
):
;
Прямые ограничения .
Этап 2.
1. Подготовим форму для ввода исходных данных (Рис 15.),
В нашем примере матрица затрат по доставке груза с конкретной станции отправления каждому потребителю 
вводится в ячейки блока В3:E5. В ячейках В6:E6 указываются потребности 
в пунктах назначения , мощности 
поставщиков записаны в блоке F3:F5.
Рис. 15 Ввод исходных данных.
2. Зарезервируем изменяемые ячейки, в которых после решения задачи будет находиться оптимальный план перевозок . Размерность этого массива обязательно должна совпадать с размерностью матрицы затрат: выделим блок ячеек I3:L5 (можно ввести в эти ячейки «1») (рис. 16).
Рис 16. Создание формы для ввода условий задачи.
3. Введем зависимость для целевой функции (рис. 17). Оптимальное значение целевой функции будет помещено в ячейке В8:
· Курсор в ячейку В8 
.
· Мастер функций fx / Математические / СУММПРОИЗВ (В3:E5; I3:L5)
Рис. 17 Ввод зависимости для целевой функции
4. Введем зависимости ограничений, стоящие в левых частях ограничений.
- вводим условия реализации мощностей поставщиков (рис 18.):
· Курсор в ячейку М3.
· Мастер функций fx / Математические / СУММ (I3:L3)
· Курсор в ячейку М3.
· Растянуть (копировать) ячейку М3 в ячейки М4 и М5.
Рис. 18. Ввод зависимостей ограничений по поставщикам.
- вводим зависимостей ограничений по потребителям (рис. 19):
· курсор в ячейку I6. ;
· Мастер функций fx / Математические / СУММ (I3:I5)
· Курсор в ячейку I6.
· Растянуть (копировать) ячейку I6 в ячейки J6, K6 и L6.
Рис. 19. Ввод зависимостей ограничений по потребителям.
На этом ввод зависимостей закончен.
Этап 3. Запуск программы Поиск решений
После выбора команд Поиск решения появится диалоговое окно Поиск решения.
· Назначение целевой ячейки: курсор в поле Установить целевую ячейку. . Левой кнопкой мыши щелкнуть на ячейке В8.
· Ввести направление целевой функции: минимальному значению.
· Ввести адреса искомых переменных: курсор в поле Изменяя ячейки. . Выделить мышью адреса ячеек I3:L5.
· Ввести ограничения:
o курсор в поле Ограничения . Выбрать режим Добавить .
o курсор в поле Ссылка на ячейку
o выбрать мышью ячейки I6:L6
o ввести знак ограничения <=
o курсор в правое окно Ограничение .
o указать мышью адреса В6:E6
o 
Остальные ограничения ввести аналогично. В результате этих действий окно Поиск решений будет выглядеть, как представлено на рис 20.
Рис. 20. Введены все ограничения.
· Выбрать параметры модели: рис 4.
Этап 4. Выполнить.
На экране диалоговое окно Результат поиска решения (рис.18.).
Рис.21. Решение найдено.
Найденный план перевозок означает, что общая стоимость перевозок составит 235 ден.ед., если
ед. груза перевести со станции 1 потребителю 3;
ед. груза перевести со станции 2 потребителю 1;
ед. груза перевести со станции 2 потребителю 3;
ед. груза перевести со станции 2 потребителю 4;
ед. груза перевести со станции 3 потребителю 2.
Неудовлетворены будут потребители и 
, т.к. они получат груза меньше, чем составляют их потребности. Так, например, потребность составляет 35 ед. груза (ячейка C6), а получит он только 20 ед. (ячейка J6).
Остальные потребители удовлетворены полностью.
Вопросы:
1. Сколько груза должно быть перевезено из А2 в П1?
2. С кем работает поставщик А2?
3. С кем работает потребитель П4?
4. Измените модель, добавив условие:
1. Потребности П2 обязательно должны быть удовлетворены. (F=265)
2. Запрещены перевозки в направлении А2 –П3.(F=245)
3. В направлении А3—П1 необходимо перевезти не менее 5 тонн.(F=250)
4. Возможности А3 стали равны 50; (F=290)
Задача о назначениях
Известна матрица эффективности. Осуществить назначение продавцов по торговым точкам для достижения максимального объема продаж.
| Прода- вец | средний дневной объем продаж продуктов по торговым точкам, у.е. | |||
| 
| 
| 
| |
| ||||
| - | |||
| ||||
|
(назначение продавца на торговую точку недопустимо по медицинским показаниям, т.е. в матрице эффективностей знаком «-» проставлен запрет назначений).
Решение.
Этап 1.
Построим математическую модель задачи о назначениях.
1. Введем управляющие переменные:
- факт назначения ресурса 
на работу 
:
, если кандидат 
назначен на работу 
,
, если кандидат не назначен на работу .
2. Объем продаж -го продавца на -ой торговой точке равны 
, 
, 
.
Функция цели - объем продаж по всем продавцам и всем торговым точкам - определяется выражением:
, или
3. Определим баланс задачи: имеется 
торговых точки и 
продавца, значит, задача является сбалансированной. Это означает, что на каждую торговую точку обязательно будет назначен продавец, причем только один, и каждый продавец получит назначение, причем только на одну торговую точку.
4. Построим систему ограничений.
По продавцам: каждый продавец будет назначен только на одну торговую точку, т.е. сумма назначений первого продавца (
) будет равна 1. Аналогично для других продавцов. Получим систему ограничений:
или 
По торговым точкам: на каждую торговую точку будет назначен только один продавец. Следовательно, эти ограничения будут записаны в виде:
, или 
Добавим ограничение 
- двоичные переменные.
Кроме того, в задаче имеется дополнительное ограничение: запрет назначения продавца на торговую точку , которое реализуется ограничением 
Этап 2.
1.Подготовим форму для ввода исходных данных (Рис. 22.).
В нашем примере матрица эффективности назначений продавцов по торговым точкам вводится в ячейки блока В3:E6.
Зарезервированы изменяемые ячейки H3:K6 - для создания матрицы назначений (размерность матрицы назначений должна совпадать с размерностью матрицы эффективности). В этих ячейках будут находиться оптимальные значения управляющих переменных .
Рис. 22. Создание формы для ввода условий задачи.
2. Введем зависимость для целевой функции (рис. 23).
Оптимальное значение целевой функции будет помещено в ячейке В8
· Курсор в ячейку В8 .
· Мастер функций fx / Математические / СУММПРОИЗВ (В3:E6; H3:K6)
Рис. 23 Ввод зависимости целевой функции
2. Введем зависимости ограничений (рис 24.).
- вводим условия по продавцам:
· курсор в ячейку L3. ;
- Мастер функций fx / Математические / СУММ (H3:K3)
- Скопировать ячейку L3 в L4, L5 и L6.
- вводим условия удовлетворения запросов по торговым точкам:
· курсор в ячейку Н7. ;
- Мастер функций fx / Математические / СУММ(Н3:Н6);
- Скопировать ячейку Н7 в I7, J7 и K7.
Рис 24. Ввод формул для вычисления левых частей ограничений.
Этап 3. Запуск программы Поиск решений
· Назначение целевой ячейки: курсор в поле Установить целевую ячейку. Левой кнопкой мыши щелкнуть на ячейке В8.
· Ввести направление целевой функции: максимальному значению.
· Ввести адреса искомых переменных: курсор в поле Изменяя ячейки. . Выделить мышью ячейки Н3:К6.
· Ввести ограничения:
o курсор в поле Ограничения . Выбрать режим Добавить .
o курсор в поле Ссылка на ячейку
o выбрать мышью ячейки в L3: L6
o ввести знак ограничения =
o курсор в правое окно Ограничение .
o Ввести 1
o Выбрать режим Добавить
o курсор в поле Ссылка на ячейку
o выбрать мышью ячейки в Н7: К7
o ввести знак ограничения =
o курсор в правое окно Ограничение .
o Ввести 1
o Добавим ограничение - двоичные переменные.
В результате окно Поиск решения будет выглядеть как показано на рисунке:
· Выбрать параметры модели: рис 4.
Этап 4. Выполнить (рис.25.).
На экране диалоговое окно Результат поиска решения.
Рис.25. Решение найдено.
Найденный план назначений означает, что суммарный объем продаж будет максимальным и составит 218у.е., если:
- продавец назначен на торговую точку 
;
- продавец назначен на торговую точку ;
- продавец назначен на торговую точку 
;
- продавец назначен на торговую точку 
.
Все ограничения при этом выполнены.
Вопросы:
Измените модель, добавив условие:
1. На третьей точке обязательно должен работать продавец П2.(F=173)
2. Запрещено назначение продавца П1 на торговую точку Т2.(F=218)
3. Измените модель при условии, что закрыли IV торговую точку. (F=173)
4. В рамках несбалансированной задачи выполните условия:
1) Продавец П1 обязательно должен быть назначен на какую-либо торговую точку.(F=173)
2) Продавец П1 обязательно должен быть назначен на 2 торговую точку.(F=169)
Задачи для самостоятельного решения
Задание 1.
Компания занимается ремонтом дорог. Имеются экономические оценки транспортных затрат на перевозку 1 тонны песка с каждого карьера на каждый участок, известны объемы поставок по карьерам и объемы потребностей по участкам:
| Участки Карьеры | В1 | В2 | В3 | В4 | Предложение |
| К1 | |||||
| К2 | |||||
| К3 | - | ||||
| К4 | |||||
| Потребности |
Составить оптимальный план перевозок, обеспечивающий минимальные транспортные расходы.
Ответ:
| В1 | В2 | В3 | В4 | ||
| К1 | |||||
| К2 | |||||
| К3 | |||||
| К4 | |||||
| ФЦ= |
Задание 2.
Эффективность работы продавцов (объем продаж) в различных торговых точках приведена в таблице:
| Торговые точки продавец | I | II | III | IV |
| А | ||||
| В | ||||
| С |
Как осуществить назначение продавцов по торговым точкам, чтобы обеспечить максимальный объем продаж?
Ответ:
| I | II | III | IV | ||
| А | |||||
| В | |||||
| С | |||||
| ФЦ= |