Лекции по "Развитию операционных систем"

Лекция 21.

 

п.18.  Дискретное программирование.

 

18.4.  Общая задача целочисленного программирования.

 

В п. 18.1. было оговорено, что математическая модель общей задачи целочислен-ного программирования имеет такой же вид, как модель ЗЛП, только на переменные накладывается условие целочисленности.

Пример 18.1.  Станкостроительный завод выпускает две модели станков с ЧПУ. Изготовление частей станков и их сборка производиться последовательно в трех цехах. Мощности цехов составляют 300, 170 и 200 чел.´дней в декаду. В первом цехе для изготовления частей одного станка первой модели требуется 6 чел.´дней в декаду, для второй модели – 4 чел.´дней в декаду; во втором цеху на сборку станка первой модели требуется 3 чел.´дней в декаду, для второй модели – 4 чел.´дней в декаду; в третьем цеху – соответственно 2 и 6 чел.´дней в декаду. Прибыль, получаемую заводом от продажи одного станка с ЧПУ каждой модели, составляют соответственно 15 и 13 млн. руб. Известно, что все выпущенные станки будут проданы. Каким должен быть оптимальный выпуск станков в течение декады?

 

_____________________

 

 

18.5.  Задача о назначении.

 

Математическая модель задачи о назначении была введена в п.18.1., в которой рассматривается целевая функция максимизирующая суммарную полезность назначений. Но в группе задач о назначении есть такие, в которых рассматривается целевая функция минимизирующая некоторые суммарные затраты.

Для решения этих задач используется алгоритм венгерского метода. (Е. Эгервари (1932 г.) – венгерский математик)

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

 

Алгоритм венгерского метода.

 

Этап 1.  Приведение матрицы C.

Суть приведения – получение нулей в каждом столбце и каждой строке матрицы C.

 

Этап 2.  Поиск назначения.

Выбираем один из нулей, помечаем его, например, точкой или звездочкой (или еще каким-нибудь способом), а остальные нули строки и столбца, в которых стоит выбранный нуль, перечеркиваем. Далее переходим к следующему нулю. И так до тех пор, пока каждый нуль будет либо помечен, либо перечеркнут. Помеченные нули составят назначения. Если число помеченных нулей равно n, то назначение будет полным. Тогда задача решена. Если назначение неполное, переходим к следующему этапу.

Замечание.  Пометку рекомендуется начинать со строк и столбцов, содержащих минимальное количество нулей.

Этап 3.  Выделение в матрице C подматрицы, не содержащей нулей.

3 (а)  помечаем (тоской, звездочкой) строки, не содержащие помеченных нулей;

3 (б)  помечаем столбцы, содержащие перечеркнутый нуль в одной из помеченных строк;

3 (в)  помечаем строки, содержащие помеченный нуль хотя бы в одном из помеченных столбцов. От 3 (в) опять переходим к 3 (б).

Пункты 3 (б) и 3 (в) повторяются до тех пор, пока есть что помечать.

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

 

Этап 4.  Перемещение нулей.

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

Переходим на 2-й этап. Пометку следует начинать со вновь полученного нуля. И так до тех пор, пока не получим полное назначение.

 

Пример 18.2.  Решить на максимум задача о назначениях с матрицей эффек-тивности C:

.