Задача о назначениях

    Федеральное агентство морского и речного  транспорта 

 Морской государственный университет имени 

 адмирала  Г.И. Невельского 
 
 
 

 Кафедра логистики  
 
 
 

 Практическая  работа №1 

Задача  о назначениях 
 
 
 
 
 
 
 
 

                                                                               
 

Выполнил: студент 0742группы

Замотина Дарья

Проверил: преподаватель

                                                                                           Куция Н.В. 
 
 
 
 
 
 
 
 

 Владивосток

 2010 год.

 

Задача  о назначениях.

Условие задачи на min:

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

Решение.

Составим исходную таблицу 1, в которой по горизонтали  буквами А,Б,В,Г,Д обозначены конфеты, а по вертикали цифрами – кондитеры

Таблица №1                                                                        Таблица №2 

 

1. В каждой строке находим минимальное число  и записываем его в таблицу  №2
2. Вычитаем элементы таблицы №2 из таблицы №1 и записываем в таблицу №3

Таблица №3 

 

3. В таблице  №3 найдем наименьшие элементы по столбцам и запишем их в таблицу №4

 

Таблица№4 

4. Вычтем  из элементов таблицы №3 элементы таблицы №4 и запишем в таблицу  №5

 

Таблица№5

 

5. В каждой строке  и столбце есть нулевой  элемент. Проведем минимальное число  прямых линий проходящих через все  нулевые клетки строк и столбцов таблицы №5
6. Найдем наименьший элемент через который не проходит ни одна прямая. Это элемент 3.
7. Вычтем число 3 из элементов, через которые прямые не проходят. Прибавим число 3 в те клетки, где прямые пересекаются. Клетки через которые проходит только одна прямая оставим без изменения. Получим таблицу №6.

 

Таблица №6 

 
 

Проанализируем  данные таблицы №6. Оптимальное решение  задачи определяют клетки с нулевой  себестоимостью. 

Оптимальное распределение стран между авиакомпаниями:

А-1

Б-2

В-3

Г-4

Д-5 
 

Проверка:

Суммарная себестоимость конфет равна 145. Для сравнения возьмем другое распределение, например:28+40+34+40+39=181. Следовательно выбранный вариант распределения конфет между кондитерами оптимален т.к. имеет минимальную себестоимость.