Организация данных и расчетные формулы

Решение задачи.

Это простая задача на максимизацию прибыли в условиях ограниченных ресурсов. Переменные задачи – количество закупаемых коробок замороженных овощей (всего 15 переменных).

Задачи транспортного типа и задачи о назначениях

Переход к целочисленным ограничениям в задачах линейной оптимизации приводит к изменению алгоритма решения задачи – вместо очень эффективного симплекс-метода используется медленный и не очень надежный метод ветвей и границ. Это приводит к катастрофическому увеличению времени расчета и к необходимости специального исследования корректности решения, что чаще всего обесценивает метод линейной оптимизации в конкретном случае с точки зрения практического менеджера.

В некоторых случаях задачу, требующую использования целых или двоичных ограничений, удается сформулировать так, что решение заведомо получается целочисленным даже при отсутствии соответствующих ограничений. Разумеется, задача в этих случаях решается очень быстро и при большом числе переменных, так как для решения по-прежнему используется алгоритм симплекс-метода.

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

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

Мини-кейс: Формирование команд

Фирма, занимающаяся продажей оборудования для компьютерных сетей, наняла 10 новых специалистов по продажам и 10 новых техников-программистов, которых необходимо объединить в пары (техник + менеджер по продажам) - команды по продаже оборудования, соответствующего нуждам конкретного клиента.

Менеджер по работе с персоналом провел среди них тест Майер-Бриггс и определил индекс взаимной совместимости для каждой возможной пары техник - продавец. Индекс может принимать значения в интервале от 1 до 16. Значение индекса 1 показывает, что пара обладает наилучшей совместимостью. Индекс 16 свидетельствует о практической невозможности какого бы то ни было сотрудничества. Более подробные характеристики смотрите в файлах папки «Соционические типы».

Результаты тестов представлены в таблице.

		IT-специалисты
Менеджеры по продажам		Александр	Ашот	Михаил	Сергей	Иван	Илья	Федор	Виктор	Дмитрий	Петр
Тип
Наталия
Елена
Татьяна
Вероника
Нина
Ольга
Ирина
Лолита
Юлия
Светлана

Необходимо провести формальный Team-building, т.е. по результатам тестирования наилучшим образом составить команды техник + продавец для работы с потенциальными клиентами.

a. Сформулируйте целевую функцию для данной проблемы.

b. Определите переменные задачи и организуйте данные для вычислений.

c. Поставьте задачу для «Поиска решения» и получите оптимальное решение.

d. Заставьте «Поиск решения» решить задачу несколько раз, не обнуляя переменные, и убедитесь, что минимальному значению суммарного индекса несовместимости соответствует несколько различных решений (способов объединений работников в команды). Сравните эти способы. Какой Вы бы предпочли?

e. Введите дополнительное ограничение, чтобы все команды имели бы индекс не хуже 8. Что при этом получается?

f. Попробуйте бороться с нецелыми решениями - явно потребуйте, чтобы решения были двоичными (либо 0, либо 1).

g. Говорят, что нехорошо объединять в команды друзей. Попробуйте добавить ограничение, что индекс команд должен быть не лучше 2.

Организация данных (часть столбцов скрыта).

Результат оптимизации.

Мини-кейс: Ремонт автодорог.

С восьми асфальтобетонных заводов должен вывозиться асфальт для ремонта пяти больших участков автодорог области. Транспортные издержки при перевозках в общем различны (см. таблицу).

Транспортные издержки

	Участок A	Участок B	Участок C	Участок D	Участок E
АБЗ 16
АБЗ 17
АБЗ 18
АБЗ 19
АБЗ 20
АБЗ 21
АБЗ 22
АБЗ 23

Заказы дорожно-строительных бригад на завтра:

	Участок A	Участок B	Участок C	Участок D	Участок E
Количество машин

Заводы в состоянии предоставить завтра:

Источник	АБЗ 16	АБЗ 17	АБЗ 18	АБЗ 19	АБЗ 20	АБЗ 21	АБЗ 22	АБЗ 23
Кол-во машин

Менеджер подрядной организации хочет минимизировать транспортные расходы для данных условий.

a. Каковы наименьшие транспортные издержки?

b. Какие участки недополучат заказанный ими асфальт и в каком количестве?

c. Найдите разницу между наилучшим и наихудшим планом перевозок?

d. Выяснилось, что из-за аварийного состояния моста перевозка асфальта с АБЗ 20 на участок D по прямому маршруту невозможна. Объездной маршрут увеличивает стоимость рейса на 200 рублей. Как из-за этого возрастут транспортные расходы?

e. Есть ли у задачи альтернативные решения?

Формулы для расчетов в транспортной задаче.

Установки «Поиска решения».

Для несбалансированной задачи о перевозках
(фиктивные клиенты и поставщики).

Если сумма заказов клиентов МЕНЬШЕ, чем имеется на складах поставщиков

Если сумма заказов клиентов БОЛЬШЕ, чем имеется на складах поставщиков - Дефицит.

Если задача не сбалансирована.

В качестве запаса у фиктивного поставщика должна фигурировать разница сумм заказов и запасов в исходной проблеме. Аналогично и у фиктивного клиента.

Мини-кейс: Маршрут Сочи - Элиста

Требуется найти наиболее короткий маршрут для проезда на автомашине из Сочи в Элисту. На схеме и в таблице показаны дороги между наиболее важными населенными пунктами – узлами дорог.

Местность вблизи Кавказа пересеченная, поэтому схема часто не дает правильного представления о реальных расстояниях между городами вдоль шоссейных дорог.

Город	Расстояние, км.		Город	Расстояние, км.
Армавир - Кропоткин			Кропоткин - Усть-Лабинск
Армавир - Майкоп			Майкоп - Туапсе
Армавир - Ставрополь			Майкоп - Усть-Лабинск
Армавир - Усть-Лабинск			Мин. Воды - Светлоград
Армавир - Черкесск			Мин. Воды - Сухуми
Ипатово - Кропоткин			Мин. Воды - Черкесск
Ипатово - Светлоград			Светлоград - Ставрополь
Ипатово - Элиста			Сочи - Сухуми
Краснодар - Тихорецк			Сочи - Туапсе
Краснодар - Туапсе			Ставрополь - Черкесск
Краснодар - Усть-Лабинск			Сухуми - Черкесск
Кропоткин - Ставрополь			Тихорецк - Усть-Лабинск
Кропоткин - Тихорецк			Тихорецк - Элиста

a. Определите кратчайший по расстоянию маршрут, без учета каких-либо предпочтений по маршруту.

b. Как увеличится длина маршрута, если в пути необходимо посетить Мин. Воды? Тихорецк?

Дата добавления: 2014-01-05