Примечание. Ограничение состоит из трех составных частей: в поле Ограничение состоит из трех составных частей: в поле Ссылка на ячейку ввести адрес или имя ячейки, на значение кото- рой накладываются ограничения; выбрать из раскрывающегося списка условный оператор (<=, =, >=, цел или двоич); в поле Ограничение ввести число, ссылку на ячейку или ее имя либо формулу, если было выбрано цел, то в поле Ограничение появит- ся «целое», а если выбрано двоич – «двоичное». Чтобы принять ограничение и приступить к вводу нового, надо нажать кнопку Добавить. Чтобы принять ограничение и вернуться в диалоговое окно Поиск решения, надо нажать OK. 6. Перейти в диалоговое окно Параметры (рис. 3.3). Здесь можно установить флажки Линейная модель и Неотрицательные значения. 7. Выбрать кнопку ОК. Рис. 3.3. Диалоговое окно Параметры поиска решения 8. В диалоговом окне Поиск решения (рис. 3.1) нажать кнопку Вы- полнить. В появившемся диалоговом окне Результаты поиска решения выбрать либо Сохранить найденное решение, чтобы установить найденное решение на листе, либо Восстановить исходные значения, что- бы вернуть исходные данные. НЕ ОБЯЗАТЕЛЬНО: В поле Тип отчета выбрать тип отчета (Результаты, Устойчи- вость, Пределы), чтобы создать отчет, основанный на найденном решении (если решение не найдено, данные параметры будут не- доступны), а затем нажать кнопку ОК. Сохранить сценарий, чтобы сохранить значения изменяющейся ячейки в качестве сценария, который можно будет отобразить позже. В появившемся диалоговом окне в поле Название сцена- рия ввести имя для этого сценария. Чтобы просмотреть, изменить или выполнить сценарий, надо: Microsoft Office 2007: на ленте Данные в группе Работа с дан- ными выберите команду Анализ «что-если __
ВОПРОС37 Задача о назначениях: стандартная постановка и особенности решения Задача о назначениях – это РЗ, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем ТЗ. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научно-исследовательским лабораториям и т.п. СТАНДАРТНАЯ ПОСТАНОВКАЗадачу о назначениях можно сформулировать следующим образом. Необходимо выполнить N различных работ. Для их выполнения можно привлечь N рабочих. Каждый рабочий за определенную плату готов выполнить любую работу. Выполнение любой работы следует поручить одному рабочему. Требуется так распределить работы между рабочими, чтобы общие затраты на выполнение всех работ были минимальными. ОСОБЕННОСТЬЮ ЗАДАЧ О НАЗНАЧЕНИЯХ ЯВЛЯЕТСЯ ТО,ЧТО ПЕРЕМЕННЫЕ(ЗНАЧЕНЯЯ ИЗМЕНЯЕМЫХ ЯЧЕЕК) ЯВЛЯЮТСЯ НУЛЕВЫМИ ПЕРЕМЕННЫЕ,Т.Е МОГУТ ПРИНИМАТЬ ЗНАЧЕНИЕ «0» ЛИБО «1» Этот алгоритм состоит из трех этапов. Этап 1: 1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи. 2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки. 3. Повторить ту же самую процедуру для столбцов. Теперь в каждой строке и в каждом столбце таблицы есть по крайней мере один нулевой элемент. Представленная в полученной с помощью описанного выше приема "приведенной" транспортной таблице задача о назначениях эквивалентна исходной задаче, и оптимальное решение для обеих задач будет одним и тем же. Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным. Этап 2. Если некоторое решение является допустимым, то каждой строке и каждому столбцу соответствует только один элемент. Если процесс распределения элементов осуществляется только в клетки с нулевой стоимостью, он приведет к получению минимального значения целевой функции. 1. Найти строку, содержащую только одно нулевое значение стоимости, и в клетку, соответствующую данному значению, поместить один элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости. 2. Зачеркнуть оставшиеся нулевые значения данного столбца. 3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным. Если на данном этапе окажется, что есть несколько нулей, которым не соответствуют назначения и которые являются незачеркнутыми, то необходимо: 4. Найти столбец, содержащий только одно нулевое значение, и в соответствующую клетку поместить один элемент. 5. Зачеркнуть оставшиеся нули в данной строке. 6. Повторять пункты 4 и 5 до тех пор, пока дальнейшая их реализация окажется невозможной. Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3. Этап 3. 1. Провести минимальное число прямых через строки и столбцы матрицы (но не по диагоналям) таким образом, чтобы они проходили через все нули, содержащиеся в таблице. 2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых. 3. Вычесть его из всех элементов, через которые не проходят прямые. 4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых 5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения. В результате применения данной процедуры в таблице появляется по крайней мере один новый ноль. Необходимо возвратиться к этапу 2 и повторять алгоритм до тех пор, пока не будет получено оптимальное решение. ВОПРОС 40
|
