Применение транспортной модели к решению задач оптимального назначения (выбора)

 Минимальный элемент сокращенной матрицы = 1, вычитаем его из всех оставшихся элементов. Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов (Таблица 2.2(9)).

 

 

 

 

 

 

 

Таблица 2.2(8)

Матрица H

2	6	0	0	4
0	5	1	7	4
2	0	0	0	0
1	7	4	8	0
5	8	1	17	0

 

Таблица 2.2(9)

Матрица I

3	6	0	0	5
0	4	0	6	4
3	0	0	0	1
1	6	3	7	0
5	7	0	16	0

 

9) Находим в каждой строке минимальный элемент и вычитаем его из всех элементов данной строки, затем находим в каждом столбце минимальный элемент и вычитаем его из всех элементов данного столбца (аналогично с пунктами 2 и 3). Так как минимальными элементами всех строк и столбцов являются нули, следовательно, матрица остается без изменений (Таблица 2.2(9)).

10) В данной  матрице находим строку (столбец) с нулевым элементом и делаем назначение в клетку этого элемента (аналогично с пунктом 4).

 

Таблица 2.2(10)

Матрица J

3	6	0	0	5
0	4	0	6	4
3	0	0	0	1
1	6	3	7	0
5	7	0	16	0

 

Полученное  решение допустимо и оптимально. Количество найденных нулей равно  количеству назначений = 5. Сложить наименования отмеченных ячеек (с выделенными  нулями). Минимальное время выполнения всего комплекса работ L(X) = 25+15+17+14+12 = 83.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3. Решение  транспортной задачи о назначениях  с помощью средств Microsoft Excel (функция «Поиск решения»)

Решим ту же самую задачу в Microsoft Excel с помощью надстройки «поиск решения»:

1) Вводим, известные нам, условия задачи:

2) Выбираем надстройку «поиск решения» и вводим необходимые данные:  для нашей задачи отмечаем целевую функцию – ячейка B16; отмечаем, что задача решается на минимум; далее выбираем изменяемые ячейки –B:9-B:13, C:9-C:13, D:9-C:13, E:9-E:13, F:9-F:13, так как мы отмечаем все сразу, то записывается как B:9;F:13; вписываем ограничения B:14;F:14=1, B:9;F:13 = двоичное, G:9;G:13=1.

 

Устанавливаем нужные параметры:

Отмечаем, что модель линейная, а  значения неотрицательные. Жмем «ок». Далее нажимаем «выполнить».

Выделенные  ячейки и будут решением нашей  задачи. Наше решение «вручную» и  решение в Excel совпадают. Это доказывает, что при решении «Венгерским методом», ошибок мы не допустили.

 

 

 

 

 

 

 

 

 

 

 

 

2.4. Интерпретация результатов расчетов и выработка управленческого решения

Проведем анализ решения нашей задачи по отчетам из Microsoft Excel.

Отчет по результатам:

Разъяснения:

отчет по результатам содержит информацию о трех компонентах задачи оптимизации: целевой функции (Целевая ячейка), плана (Изменяемые ячейки), и ограничений (Ограничения).

Таблица «целевая ячейка»:

«Исходное значение» – начальное значение целевой функции при начальном опорном плане («исходные значения» во второй таблице); 
«Результат» – минимальное значение (в нашем случае)  целевой функции.

Таблица «изменяемые ячейки»: 
«Исходные значения» – начальный опорный план; 
«Результат» – оптимальный план задачи.

Таблица «ограничения»: 
«Формула» – формулы ограничений; 
«Статус» – показывает влияние ограничений на конечный результат. Если статус «связанное», тогда данное ограничение влияет на полученный план, если «не связан» - тогда не влияет.

«Разница» – разница между имеющимся в наличии количеством ресурсов (рабочих) и тем количеством, которое используется в полученном плане.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отчет по устойчивости:

Разъяснения:

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

 

Таблица «изменяемые  ячейки»:

«Нормированная  стоимость» - до какого значения надо уменьшить  тарифы, чтобы невыгодные маршруты стали выгодными;

«Целевой коэффициент» – тарифы на перевозку груза (столбцы  «Нормированная стоимость» и «Целевой коэффициент» не несут в себе нужной информации и во всех строках не имеют наименования, так как в задаче нет тарифов);

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

Таблица «ограничения»:

«Теневые цены» запасов поставщиков - отрицательные числа, они показывают, как уменьшатся затраты при увеличении дефицитных запасов поставщиков;

«Теневые цены» потребностей потребителей указывают, как увеличатся затраты при увеличении потребностей («Теневая цена» не имеет особого значения для задач о назначениях);

«Ограничения  правая часть» показывает запас ресурсов на складах (количество имеющихся работников);

«Допустимое увеличение и уменьшение» - показывают, на сколько можно изменять соответствующий ресурс (в нашем случае рабочих), чтобы базисное решение осталось неизменным.

 

 

 

 

 

Отчет по пределам:

 

Разъяснения:

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

 

После получения  результатов решения можно выработать управленческое решение. При данных условиях, и так как мы знаем, что решение одно единственное, руководителю надо последовать оптимальному предлагаемому плану. На Работу 1 назначить Синицына, на Работу 2 – Галкина, на Работу 3 – Орлова, на Работу 4 – Воробьева и на Работу 5 – Сорокина. Минимальное время выполнения всего комплекса работ составит 83 часа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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

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

• рассмотрели экономико-математические модели как транспортной задачи в целом, так и транспортной задачи о назначениях в отдельности;
• рассмотрели методы решения задач линейного программирования;
• решили задачу одним из этих методов;
• также, решили задачу с использованием Excel;
• провели краткий анализ решенной задачи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список  использованной литературы:

1. Орлова И. В., Половников В. А.. «Экономико-математические методы и модели: компьютерное моделирование». – М.: Вузовский учебник, 2007. – 365с.
2. Алесинская Т.В., Сербин В.Д., Катаев А.В.. "Экономико-математические методы и модели. Линейное программирование". – М.: Учебно-методическое пособие, Таганрог: Изд-во ТРТУ, 2001. – 79 с.
3. Бережная Е. В., Бережной В. И.. «Математические методы моделирования экономических систем». Учебное пособие. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006. – 432 с.
4. Кремер Н.Ш.. «Исследование операций в экономике». – М.: ЮНИТИ, 2001.