Значения ячейки целевой функции не сходятся что это значит

7

5.5. Итоговые сообщения процедуры поиска решения

Если поиск решения успешно закончен, в окне диалога «Результаты поиска решения» выводится одно из следующих сообщений:

Решение найдено. Все ограничения и условия оптимальности выполнены (см. рис. 5.6).

Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.

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

По результатам поиска решения можно получить разнообразные отчеты. Правда, в данном случае (при решении задачи определения ассортимента выпуска продукции) мы можем получить только один тип отчета — отчет по результатам, так как задача решается в целых числах. Д ля этого необходимо щелкнуть мышкой на строку Результаты в группе Тип отчета: и нажать на кнопку ОК, после чего Microsoft Excel создаст новый лист – Отчет по результатам 1 (рис. 5.8).

В Отчете по результатам приводятся оптимальные значения переменных (изменяемых значений) и целевой функции. Устанавливается статус ограничений (свя­зывающие, не связывающие), по несвязывающим ограничениям типа “” устанавливается значение остатка, по несвязывающим ограничениям типа “” – значение избытка.

Поиск свелся к текущему решению. Все ограничения выполнены.

Значение целевой ячейки, не менялось в течение последних пяти итераций. Решение возможно найдено или итеративный процесс улучшает решение очень медленно.

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

Поиск не может улучшить текущее решение. Все ограничения выполнены.

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

Поиск остановлен (истекло заданное на поиск время).

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

Поиск остановлен (достигнуто максимальное число итераций).

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

Значения целевой ячейки не сходятся.

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

Поиск не может найти подходящего решения. (рис. 5.9)

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

Поиск остановлен по требованию пользователя.

Нажата кнопка Стоп в окне диалога Текущее состояние поиска решения после прерывания поиска решения или в процессе пошагового выполнения итераций.

Условия для линейной модели не удовлетворяются.

Установлен флажок Линейная модель, однако итоговый пересчет порождает такие значения, которые не согласуются с линейной моделью. Это означает, что решение недействительно для данных формул листа. Снимите флажок Линейная модель и запустите задачу снова.

При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.

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

Мало памяти для решения задачи.

Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.

Другой экземпляр Excel использует SOLVER.DLL..

Попробуйте повторить через какое-то время.

Запущено несколько копий Microsoft Excel, в одном из которых используется файл Solver.dll.

Есть несколько вариантов, когда задача не может быть решена. Рассмотрим эти случаи.

Оптимальное решение не найдено.

Процедура поиска решения может остановиться до достижения оптимального решения по следующим причинам:

Пользователь прервал процесс поиска.

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

Установлен флажок Линейная модель, в то время как решаемая задача нелинейная.

Значение целевой ячейки неограниченно увеличивается или уменьшается.

Необходимо изменить значения полей Максимальное время, Итерации или Точность.

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

Заданная ячейка должна находиться на текущем листе.

Данное сообщение появляется на экране при запуске процедуры поиска в книге с названием, содержащим апостроф, например, Tax’95.xls. Переименуйте книгу так, чтобы название не содержало апостроф например, Taxes1995.

Значения влияющих ячеек и целевой ячейки сильно различаются.

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

Предпосылки для запуска процедуры поиска решения с другими начальными условиями.

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

Разрешение вопросов, связанных с созданием структуры

Группирование только подробных данных. Группируя данные, выделяйте только образующие группу строки или столбцы с подробными данными. Не следует включать в выделяемую область соответствующую итоговую строку или столбец. Например, если строка 6 содержит итоговые данные для строк 3—5, то для создания группы выделите только строки 3—5.

Отображение всех данных перед их группированием. Чтобы сгруппировать структуру, состоящую из нескольких уровней, следует отобразить на экране все содержащиеся в ней данные. Убедитесь в том, что все подчиненные итоговые строки или столбцы и соответствующие им подробные данные, образующие следующий уровень структуры, выделены правильно. Например, строка 6 и 10 содержат итоги для строк 3—5 и строк 7—9 соответственно. Строка 11 содержит общий итог. Чтобы сгруппировать детальные данные для строки 11, выделите строки 3—10.

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

Отсутствуют символы структуры

После разгруппирования или удаления структуры данные все еще скрыты

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

Разрешение вопросов, связанных с консолидацией данных

Здесь приводятся советы только для тех случаев, когда консолидация данных осуществлялась с использованием команды Консолидация в меню Данные. Они неприменимы, если консолидация осуществлялась с использованием формул с трехмерными ссылками.

Проверьте ссылки на исходный диапазон. Убедитесь, что ссылки на все исходные диапазоны введены правильно.

Проверьте итоговую функцию. Убедитесь, что в диалоговом окне Консолидация выбрана подходящая итоговая функция.

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

Консолидация по расположению

Убедитесь, что в каждой исходной области в надлежащем порядке содержатся данные одинакового типа.

Консолидация данных по категории

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

Проверьте идентичность подписей категорий. Убедитесь, что заголовки категорий одинаковы (включая регистр букв) во всех исходных областях. Например, заголовки «Ср. за год» и «Средний за год» различаются и не будут объединены в таблице консолидации.

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

Разрешение вопросов, возникающих при поиске решения

Оптимальное решение не найдено.

Поиск решения может остановиться до достижения оптимального решения по следующим причинам.

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

Значения влияющих ячеек и целевой ячейки или ячейки, на которую наложены ограничения, сильно различаются.

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

Ожидаемое решение не получено.

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

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

Найденное решение отличается от предыдущего результата.

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

Поиск не может найти оптимальное решение.

Далее приведен список итоговых сообщений процедуры поиска решения.

Поиск не может улучшить текущее решение. Все ограничения выполнены.

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

Поиск остановлен (истекло заданное на поиск время).

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

Поиск остановлен (достигнуто максимальное число итераций).

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

Значения целевой ячейки не сходятся.

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

Поиск не может найти подходящего решения.

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

Поиск остановлен по требованию пользователя.

Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.

Условия для линейной модели не выполняются.

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

При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.

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

Имя или формула в окне Добавить ограничение или в окне Изменить ограничение заданы неверно, либо в поле Ограничение было задано целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.

Мало памяти для решения задачи.

Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения и попытайтесь снова выполнить процедуру поиска решения.

Учись Учиться

Составление математических моделей экономических задач. Решение оптимизационных задач с помощью электронных таблиц

Tags:
• Составление математических моделей
• экономических задач
• Решение оптимизационных задач
• с помощью электронных таблиц
• Молоко поставляется
• формат Денежный
• Установить целевую ячейку
• Установить целевую ячейку
• Параметры поиска решения

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

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

Подготовка к работе

Для выполнения упражнений и заданий необходимо наличие надстройки Поиск решения.

· Выполните команду Сервис/Поиск решения…

· Для загрузки надстройки выполните команду Сервис/Надстройки…

· В диалоговом окне Надстройки (рис. 11.1) установите флажок Поиск решения. OK .

Упражнение № 11. SEQ Упражнение_№_*. \* ARABIC 1

Частная фирма занимается переработкой молока на нескольких заводах, расположенных в разных районах Москвы. Молоко поставляется объединениями фермеров, расположенными в городах Московской области. Стоимость молока одинакова, однако перевозка от объединения фермеров на завод зависит от расстояния и отличается для каждого объединения и завода. Потребность заводов в молоке различна. Объем молока в каждом объединении ограничен.

Потребителей (молокоперерабатывающие заводы) назовем по наименованию районов Москвы, в которых они расположены, а поставщиков (объединения фермеров) – по названиям городов Подмосковья.

Потребность перерабатывающих заводов в молоке.

Возможности объединений в доставке молока.

Для минимизации общих затрат на перевозку требуется определить, сколько поставлять молока, от какого объединения и на какой завод.

Затраты на перевозку тонны молока от объединения X к заводу, расположенному в районе Y , указаны в таблице.

· Удалите все листы, кроме первого.

· Сохраните файл под именем Транспортная задача.

· Составьте модель задачи.

§ Заполните 1-ю строку и столбец A (рис. 11.11).

§ Запросы заводов на поставку молока занесите в диапазон ячеек C2:F2.

§ Возможный объем поставки молока объединениями фермеров занесите в диапазон ячеек B12:B16.

§ Общий объем молока, поставляемый каждым объединением фермеров, разместите в диапазоне ячеек B5:B9. Выделите ячейку B5 и введите формулу =СУММ(C5:F5) . Скопируйте формулу в диапазон ячеек B6:B9.

§ В диапазон ячеек С12:F16 занесите стоимость перевозки тонны молока, используя данные из таблицы. Для ячеек указанного диапазона установите формат Денежный с двумя знаками после запятой.

§ Решение задачи (объем молока для перевозки) будет расположено в диапазоне ячеек C5:F9.

§ Полная стоимость перевозки молока по маршруту Наро-Фоминск – Лужники вычисляется по формуле = C 5* C 12 .

§ Общая стоимость перевозок на завод в Лужники составит = C 5* C 12+ C 6* C 13+ C 7* C 14+ C 8* C 15+ C 9* C 16 . Введите эту формулу в ячейку С17.

§ Для подсчета общей стоимости перевозок на другие перерабатывающие заводы скопируйте формулу из ячейки С17 в диапазон ячеек D 17: F 17.

§ Для подсчета итоговой стоимости всех перевозок введите в ячейку B 17 формулу =СУММ(C17:F17) .

§ Выделите диапазон ячеек B 17: F 17 и установите для этих ячеек формат Денежный с двумя знаками после запятой.

· Выполните команду Сервис/ Поиск решения…

· В диалоговом окне Поиск решения установите значения (рис. 11.12).

— Поле Установить целевую ячейку: служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу. По условию задачи необходимо минимизировать расходы на перевозку, поэтому в поле Установить целевую ячейку: введите ячейку $ B $17 .

— Поле Равной: служит для выбора варианта оптимизации значения целевой ячейки. Установите переключатель в режим минимальному значению.

— Поле Изменяя ячейки: служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку. Установите диапазон ячеек $ C $5:$ F $9 , так как необходимо определить, от какого производителя, на какой склад и сколько продукции следует перевезти.

— Кнопка Предположить используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.

— Список Ограничения: служит для отображения списка граничных условий поставленной задачи. Добавьте ограничения.

Ограничение

объем поставок не может превышать имеющиеся запасы

запросы потребителей должны быть выполнены полностью

количество перевозок не может быть дробным числом

— Кнопка Параметры служит для отображения диалогового окна Параметры поиска решения (рис. 11.13), в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения. Значения и состояния элементов управления окна, используемые по умолчанию, подходят для решения большинства задач.

§ Поле Максимальное время: служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее число 32767.

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

§ Поле Относительная погрешность служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать десятичную дробь от 0 (нуля) до 1. Чем больше десятичных знаков в задаваемом числе, тем выше точность. Например, число 0,0001 представлено с более высокой точностью, чем 0,01.

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

§ Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков. Например, 0,0001 соответствует меньшему относительному изменению по сравнению с 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения.

§ Элемент управления Линейная модель служит для ускорения поиска решения линейной задачи оптимизации.

§ Элемент управления Показывать результаты итераций служит для приостановки поиска решения для просмотра результатов отдельных итераций. Установите флажок Показывать результаты итераций.

§ Элемент управления Автоматическое масштабирование служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине. Например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

§ Элемент управления Неотрицательные значения позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение. Установите флажок Неотрицательные значения.

— Кнопка Закрыть служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить.

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

— Кнопка Выполнить служит для запуска поиска решения поставленной задачи. Щелкните по кнопке Выполнить.

· Появится диалоговое окно Текущее состояние поиска решения (рис. 11.14). Щелкните по кнопке Продолжить.

· После каждой итерации на экране будет отображаться окно Текущее состояние поиска решения.

· После окончания поиска решения на экране появится окно Результаты поиска решения (рис. 11.15), сообщающее о том, что решение найдено.

— Установите переключатель в значение Сохранить найденное решение.

— Раздел Тип отчета служит для указания типов отчета, которые могут быть добавлены в книгу.

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

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

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

· Щелкните по кнопке OK .

Минимальная сумма затрат на перевозки при соблюдении всех условий составит 2.795.450 рублей. Предлагается выполнять перевозки по следующим маршрутам:

knigechka

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

Решение задач линейного программирования с помощью Excel

Рассмотрим пример задачи линейного программирования.

Математическая модель задачи имеет вид:

где x_j – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса, а правые части показывают количество имеющегося ресурса.

Ввод условий задачи

Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рис. 2.

В ячейку F6 введено выражение целевой функции как суммы произведений значений прибыли от выпуска единицы продукции каждого типа на количество выпускаемой продукции соответствующего типа. Для наглядности на рис. 3 представлена форма ввода исходных данных в режиме вывода формул.

В ячейки F8:F10 введены левые части ограничений для ресурсов каждого вида.

Решение задачи линейного программирования

Для решения задач линейного программирования в Excel используется мощный инструмент, называемый Поиск решения. Обращение к Поиску решения осуществляется из меню Сервис, на экран выводится диалоговое окно Поиска решения (рис. 4).

Ввод условий задачи для поиска ее решения состоит из следующих шагов:

1 Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;

2 Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению;

3 Ввести адреса изменяемых переменных (x_j): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;

4 Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рис. 5) :

— ввести граничные условия для переменных x_j (x_j³0), для этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х₁, выбрать из списка нужный знак (³), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить; повторить описанные действия для переменных х₂, х₃ и х₄;

— ввести ограничения для каждого вида ресурса, для этого в поле Ссылка на ячейку окна Добавление ограничения указать ячейку F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак £ и адрес Н9 правой части ограничения, нажать кнопку Добавить; аналогично ввести ограничения на остальные виды ресурсов;

— после ввода последнего ограничения вместо Добавить нажать ОК и возвратиться в окно Поиск решения.

Решение задачи линейного программирования начинается с установки параметров поиска:

— в окне Поиск решения нажать кнопку Параметры, на экран выводится окно Параметры поиска решения (рис. 6);

— установить флажок Линейная модель, что обеспечивает применение симплекс-метода;

— указать предельное число итераций (по умолчанию – 100, что подходит для решения большинства задач);

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

— нажать ОК, возврат в окно Поиск решения .

Для решения задачи нажать кнопку Выполнить в окне Поиск решения, на экране – окно Результаты поиска решения (рис. 7), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения. Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся.

Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F6 формы ввода, оптимальный план выпуска продукции х₁=10, х₂=0, х₃=6, х₄=0 указывается в ячейках В3:С3 формы ввода (рис. 8).

Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.

Если при установке параметров в окне Параметры поиска решения (рис. 6) был установлен флажок Показывать результаты итераций, то будут показаны последовательно все шаги поиска. На экран будет выводиться окно Текущее состояние поиска решения (рис. 9). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке 10 .

Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения.

Анализ оптимального решения

Прежде чем, перейти к анализу результатов решения, представим исходную задачу в форме

введя дополнительные переменные у_i, представляющие собой величины неиспользованных ресурсов.

Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные v_i.

Анализ результатов поиска решения позволит увязать их с переменными исходной и двойственной задач.

С помощью окна Результаты поиска решения можно вызвать отчеты трех типов, позволяющие анализировать найденное оптимальное решение:

Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК.

1 Отчет по результатам (рис. 11) состоит из трех таблиц:

— таблица 1 содержит сведения о целевой функции; в столбце Исходно указывается значение целевой функции до начала вычислений;

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

— таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Для Ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное; при неполном использовании ресурса в этой графе указывается не связан. Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной x_j в найденном оптимальном решении и заданным для нее граничным условием (x_j³0).

Именно в графе Разница можно увидеть значения дополнительных переменных y_i исходной задачи в формулировке (2). Здесь у₁=у₃=0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у₂=26, значит, имеются излишки сырья.

2 Отчет по устойчивости (рис. 12) состоит из двух таблиц.

В таблице 1 приводятся следующие значения:

— результат решения задачи (оптимальный план выпуска);

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

— коэффициенты целевой функции;

— предельные значения приращения коэффициентов целевой функции, при которых сохраняется оптимальный план выпуска.

В таблице 2 содержатся аналогичные данные для ограничений:

— величины использованных ресурсов;

— Теневая цена, показывающая, как изменится целевая функция при изменении величины соответствующего ресурса на единицу;

— допустимые значения приращений ресурсов, при которых сохраняется оптимальный план выпуска продукции.

Отчет по устойчивости позволяет позволяет получить двойственные оценки.

Как известно, двойственные переменные z_i показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете Excel двойственная оценка называется Теневой ценой.

В нашем примере сырье не используется полностью и его ресурс у₂=26. Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z₂=0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.

В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у₁=у₃=0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и следовательно, на величину целевой функции. Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z₁=20, z₃=10.

Значения двойственных оценок находим в Отчете по устойчивости, в таблице 2, в графе Теневая цена.

При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна

F=1320+20×1=1340 ( при увеличении).

Аналогично, при увеличении объема финансов на единицу целевая функция будет

Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида. Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.

Дополнительные двойственные переменные также отражены в Отчете по устойчивости в графе Нормир. стоимость таблицы 1.

Если основные переменные не вошли в оптимальное решение, т.е. равны нулю ( в примере х₂=х₄=0), то соответствующие им дополнительные переменные имеют положительные значения (v₂=10, v₄=20). Если же основные переменные вошли в оптимальное решение (х₁=10, х₃=6), то их дополнительные двойственные переменные равны нулю (v₁=0, v₃=0).

Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v₂ и v₄) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на 10 единиц и будет равна 1320 -10×1 =1310.

Обозначим через Dс_j изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.

В графах Допустимое увеличение и Допустимое Уменьшение таблицы 1 Отчета по устойчивости показаны пределы изменения Dс_j , при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида Продj. Например, при изменении Dс₁ в пределах -12£ Dс₁ £ 40, как показано в отчете, по-прежнему будет выгодно выпускать продукцию вида Прод1. При этом значение целевой функции будет F=1320+x₁×Dс_j =1320+10×Dс_j.

3 Отчет по пределам приведен на рис. 13. В нем показывается, в каких пределах могут изменяться значения x_j, вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х₁=10, х₂=0, х₃=6, х₄=0 положить х₁=0 (нижний предел) при неизменных х₂, х₃ и х₄, то значение целевой функции будет равно 60×0+70×0+120×6+130×0=720.

Далее приводятся верхние пределы изменения x_j и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах. Поэтому везде F=1320.