Значения целевой функции не сходятся excel
Электронные таблицы Excel фирмы Microsoft имеют встроенные средства решения задач поиска экстремума, оформленные в виде так называемой надстройки. Перед началом работы надо убедиться в том, что в составе сгенерированного на вашей ЭВМ пакета Excel требуемая надстройка установлена. Для этого выберите режим Сервис главного меню и проверьте, есть ли в открывшемся ниспадающем меню пункт Поиск решения (рис. 5). Если строка меню Поиск решения отсутствует, то выберите пункт меню Сервис / Надстройки и в открывшейся форме включите режим Поиск решения (рис. 6). Если и в этом окне пункт Поиск решения отсутствует, то это означает, что на вашей машине установлена сокращенная версия электронных таблиц и требуется переустановка пакета Excel.
Надстройка Поиск решения (рис. 7) позволяет, задавая некоторую ячейку в виде целевой (Установить целевую ячейку), при условии обеспечения зависимости результата вычислений в ней от значений некоторых изменяемых ячеек (Изменяя ячейки) с учетом заданных ограничений (Ограничения) получить набор переменных в изменяемых ячейках, обеспечивающий или максимальное, или минимальное, или заданное значение целевой ячейки.
В качестве параметров режима (рис. 8) задаются методы поиска экстремума. Так, при установке флажка Линейная модель надстройка ищет экстремум симплекс-методом. Флажок Неотрицательные значения накладывает дополнительное ограничение на значения переменных задачи. Его установка эквивалентна введению ограничения .
Примечание. Если флажок Линейная модель выключен, решение задачи ведется методом Ньютона или градиентным с использованием прямых или центральных конечных разностей на основе линейной или квадратичной оценки уменьшения приращения экстремума в зависимости от установленных флажков. Эти методы позволяют, в частности, решать нелинейные и целочисленные задачи поиска экстремумов.
Рис. 5. Пункт меню Поиск решения
Рис. 6. Включение надстройки Поиск решения
Режим Автоматическое масштабирование позволяет перейти к отображению данных в относительных единицах, а при установке флажка Показывать результаты итераций включается пошаговый режим. Также к числу параметров относится ограничение по времени процесса поиска решения в секундах (Максимальное время) (максимально 32767) и количеству итераций (Предельное число итераций). Вариант настройки параметров режима Поиск решения может быть сохранен.
Примечание. Точность соответствия результата заданному значению (Относительная погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной математики (Допустимое отклонение), а также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций относятся к параметрам, используемым при решении задачи методом Ньютона или градиентным.
Рис. 7. Главная форма надстройки Поиск решения
Рассмотрим задачу линейного программирования (1,2), записанную в виде целевой (критериальной) функции и набора ограничений, с конкретными числовыми данными, полученными с помощью датчика случайных чисел.
На рис. 9 изображен рабочий лист Excel с данными задачи (4). Для всех ячеек, предназначенных для хранения данных, был задан числовой формат с двумя знаками после запятой режимом Формат/Ячейки…/Число. Матрица размещена в диапазоне ячеек B8:E16. Значения ограничений находятся в диапазоне ячеек G8:G16. Весовые коэффициенты целевой функции занесены в диапазон ячеек B5:E5. Кроме этого, для хранения переменных зарезервирован диапазон ячеек B3:E3. Значения предварительно были обнулены, однако это не является обязательным, поскольку система может начать поиск экстремума с любой начальной комбинации. Очевидно, что в данном случае , .
Рис. 8. Параметры надстройки Поиск решения
Выражение (3) представляет собой ничто иное, как сумму попарных произведений некоторых наборов чисел, которые должны быть заданы в табличной форме или рассчитаны средствами пакета Excel. Рассчитаем значение целевой функции в ячейке F5. Ее программирование сводится к заданию выражения типа (3), которое можно рассчитать непосредственно на основе формулы Excel =B3*B5+C3*C5+D3*D5+E3*E5. Тем не менее, по ряду причин, более удобно воспользоваться встроенной функцией СУММПРОИЗВ(B5:E5;$B$3:$E$3), которая автоматически определяет количество слагаемых и дает результат вычислений в соответствии с (3). Использование абсолютного формата записи диапазона ячеек, используемого для хранения , не является обязательным, однако удобно для последующих действий, которые могут выполняться способом копирования.
Выражения, определяющие расход ресурсов программируются в ячейки F8, F9,…, F16 аналогично предыдущему с той только разницей, что в качестве первого аргумента функции СУММПРОИЗВ() выступает соответствующая строка матрицы , а второй аргумент по-прежнему есть диапазон ячеек B3:E3, заданный в абсолютом формате и используемый для хранения переменных .
Примечание. Остальная информация, нанесенная на рабочий лист (рис. 9), используется для пояснения принципа размещения данных. Она представляет собой либо текстовые строки, записанные в определенные ячейки, либо внедренные объекты и носит вспомогательный характер. Поэтому при повторении примера на ЭВМ она может быть опущена.
Рис. 9. Вариант размещения данных на рабочем листе
Выполненные ранее в операции (заполнение таблиц данными и программирование формул) позволяют полностью подготовиться собственно к решению задачи оптимизации. Теперь нам необходимо вызвать режим Сервис/Поиск решения. В открывшейся главной форме меню режима Поиск решения (рис. 7) надо указать адрес нашей целевой ячейки F5 и проверить или задать тип экстремума (в нашем случае Установить целевую ячейку равной максимальному значению). В окне Изменяя ячейки задаем адреса ячеек переменных (в нашем случае B3:F3). Нажав кнопку Добавить в открывшейся таблице (рис. 10) Добавление ограничения в поле Ссылка на ячейку вводим адреса левых частей неравенств (2) (в нашем случае F8:F16). Устанавливаем (сохраняем) требуемые знаки неравенств (в нашем случае ). Войдя в окно Ограничение, задаем адреса ячеек, содержащих значения (в нашем случае G8:G16). Нажав кнопку Параметры, в открывшейся таблице (рис. 8) задаем режим Линейная модель и Неотрицательные значения, после чего нажимаем кнопку OK. Результат этих действий отображен на рис11.
Решение найдено. Все ограничения и условия оптимальности выполнены (имеет место в рассматриваемом случае).
Поиск не может найти подходящего решения.
Значения целевой ячейки не сходятся.
Если решение найдено, то на рабочем листе Excel в изменяемых ячейках находятся значения переменных (в нашем случае 1,13; 0,00; 0,00; 3,10), обеспечивающие максимальное значение целевой функции (в нашем случае 33,95). Для сохранения результатов вычислений на рабочем листе необходимо выбрать пункт Сохранить найденное решение.
Рис. 10. Добавление ограничений
Рис. 11. Подготовленная к решению задача линейного программирования
По результатам решения в случае установки режима Линейная модель (симплекс-метод) могут быть представлены три типа отчетов: по результатам, по устойчивости и по пределам. Если они требуются, то в меню результаты поиска решения в окне Тип отчета (рис. 12) необходимо выделить соответствующие строки.
Отчет по результатам (рис. 13) содержит начальные (Исходно) и конечные (Результат) значения целевой функции и изменяемых ячеек, а также сводку результатов использования ресурсов. В этой сводке в столбце Статус символами связанное или несвязанное обозначаются соответственно полное или неполное использование соответствующего ресурса. В рассматриваемом примере полностью израсходованы Ресурс 3 и Ресурс 4.
Рис. 12. Результат решения задачи линейного программирования
Отчет по устойчивости (рис. 14) показывает значения нормированной стоимости оценок (Нормир. стоимость), определяющих насколько изменится целевая функция при принудительном включении в план единицы продукции. Кроме этого в отчете содержатся величины использованных ресурсов (Результ. значение), их теневые цены, показывающие насколько изменится целевая функция при увеличении соответствующего ресурса на единицу, а также используемые значения ограничений. Колонки Допустимое увеличение (уменьшение) задают диапазон изменения значений переменных и ограничений, сохраняющих общую структуру решения задачи.
Рис. 13. Отчет по результатам
Рис. 14. Отчет по устойчивости
Отчет по пределам (рис. 15) показывает возможный диапазон изменения значений переменных, сохраняющий структуру оптимального решения, а также получающиеся в этом случае значения целевой функции.
Примечание. Конкретные реализации состава таблиц отчетов по пределам и устойчивости могут отличаться от приведенных выше.
В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям (ОДП задачи пуста)*.
Если необходимо поставить задачу так, чтобы она была разрешима, следует исключить противоречия в ограничениях. Возможно, следует в задаче снять одно ограничение или сразу несколько.
Условия для линейной модели не удовлетворяются.
Установлен флажок “Линейная модель”, однако итоговый пересчет порождает такие значения, которые не согласуются с линейной моделью (попытка решить нелинейную задачу, как линейную).
При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.
При пересчете значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу.
Следует найти целевую ячейку или ячейку ограничения, порождающие ошибку, и изменить формулы в них так, чтобы они возвращали подходящее числовое значение.
Мало памяти для решения задачи.
Система не смогла выделить память, необходимую для поиска решения.
Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.
Другой экземпляр Excel использует SOLVER.DLL. Попробуйте повторить через какое-то время.
Запущено несколько копий Microsoft Excel, в одном из которых используется файл Solver.dll, который необходим для «Поиска решения».
6.6 Типы отчетов
Заголовок каждого отчета состоит из названия версии электронной таблицы, названия типа отчета, указания на рабочий лист (с указанием в квадратных скобках названия книги), а также даты и времени создания отчета, например:
Microsoft Excel 10.0 Отчет по результатам
Рабочий лист: [Пример.xls]Лист7
Отчет создан: 04.12.2005 19:49:24
Отчеты состоят из таблиц, соответствующих целевой функции, ограничениям и переменным. Первые две графы в каждой из них называются «Ячейка» и «Имя». В первой графе указываются адреса соответствующих ячеек. Для ограничений в графе «Ячейка» дается адрес ячейки, на которую имеется ссылка в левой части соответствующего ограничения. Имя ячейки составляется из содержания ближайших текстовых ячеек (см. раздел 6.2).
6.6.1 Отчет по результатам
Данный тип отчета состоит из трех таблиц, озаглавленных «Целевая ячейка», «Изменяемые ячейки» и «Ограничения». Первые две таблицы для примера из раздела 6.2 примут вид таблицы 29. После заголовка «Целевая ячейка» в скобках стоит указание направления экстремизации. В примере заголовок последней таблицы примет вид «Целевая ячейка (Максимум)», так как целевая функция максимизируется.
В первых двух таблицах третья и четвертая графы называются «Исходно» и «Результат». В них указываются соответственно исходное и конечное значения в ячейках. Каждой изменяемой ячейке соответствует одна строка таблицы, таблица «Целевая ячейка» состоит из одной строки.
§ Решение найдено. Все ограничения и условия оптимальности выполнены.
Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.
§ Поиск свелся к текущему решению. Все ограничения выполнены.
Относительное изменение значения в целевой ячейке за последние пять итераций стало меньше установленного значения параметра Сходимость в диалоговом окне Параметры поиска решения. Чтобы найти более точное решение, установите меньшее значение параметра Сходимость, но это займет больше времени.
§ Поиск не может улучшить текущее решение. Все ограничения выполнены.
В процессе поиска решения нельзя найти такой набор значений влияющих ячеек, который был бы лучше текущего решения. Приблизительное решение найдено, но либо дальнейшее уточнение невозможно, либо заданная погрешность слишком высока. Измените погрешность на меньшее число и запустите процедуру поиска решения снова.
§ Поиск остановлен (истекло заданное на поиск время). Время, отпущенное на решение задачи, исчерпано, но достичь удовлетворительного решения не удалось. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решение или Сохранить сценарий.
§ Поиск остановлен (достигнуто максимальное число итераций). Произведено разрешенное число итераций, но достичь удовлетворительного решения не удалось. Увеличение числа итераций может помочь, однако следует рассмотреть результаты, чтобы понять причины остановки. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решениеили нажмите кнопку Сохранить сценарий.
§ Значения целевой ячейки не сходятся. Значение целевой ячейки неограниченно увеличивается (или уменьшается), даже если все ограничения соблюдены. Возможно, следует в задаче снять одно ограничение или сразу несколько. Изучите процесс расхождения решения, проверьте ограничения и запустите задачу снова.
§ Поиск не может найти подходящего решения. В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям при заданной точности. Вероятно, ограничения противоречивы. Исследуйте лист на предмет возможных ошибок в формулах ограничений или в выборе ограничений.
§ Поиск остановлен по требованию пользователя. Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.
§ При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения. При пересчете значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу. Найдите целевую ячейку или ячейку ограничения, порождающие ошибку, и измените их формулы так, чтобы они возвращали подходящее числовое значение.
Набрано неверное имя или формула в окне Добавить ограничение или окне Изменить ограничение или в поле Ограничение были заданы целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.
§ Мало памяти для решения задачи. Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.
§ Другой экземпляр Excel использует SOLVER.DLL. Запущено несколько копий Microsoft Excel, в одном из которых используется файл Solver.dll.
§ Оптимальное решение не найдено.
Поиск решения может остановиться до достижения оптимального решения по следующим причинам:
· Пользователь прервал процесс поиска.
· Команда Показывать результаты итераций в диалоговом окне Параметры поиска решения выбрана перед Выполнить.
· Пользователь нажал кнопку Стоп в режиме пошагового выполнения итераций, по истечении времени, отведенного на работу процедуры, или после выполнения заданного числа итераций.
· Установлен флажок Линейная модель в диалоговом окне Параметры поиска решения, в то время как решаемая задача не линейна.
· Значение, заданное в поле Установить диалогового окна Поиск решения, неограниченно увеличивается или уменьшается.
· Необходимо изменить значения полей Максимальное время или Итерации в диалоговом окне Параметры поиска решения.
· В случае задач, значения в которых ограничены множеством целых чисел, необходимо уменьшить значение в поле Допустимое отклонение диалогового окна Параметры поиска решения, что позволит найти лучшее решение.
· В случае нелинейных задач необходимо уменьшить значение в поле Сходимость диалогового окна Параметры поиска решения, что позволит продолжать поиск решения, когда значение в целевой ячейке изменяется медленно.
· Необходимо установить флажок Автоматическое масштабирование в диалоговом окне Параметры поиска решения, если значения влияющих ячеек или значения влияющей и целевой ячеек различаются на несколько порядков.
После остановки на экране отображается диалоговое окно Результаты поиска решения. Установите переключатель в положение Сохранить найденное решение или Восстановить исходные значения, внесите нужные изменения и запустите процедуру поиска решения снова.
Алгоритм получения решения задачи симплекс-методом с использованием офисного приложения Microsoft Excel рассмотрим на примере 2.2.1. Математическая модель задачи имеет следующий вид:
Для получения решения исходной задачи будем использовать надстройку «Поиск решения».
Ввод исходных данных задачи
При решении задачи линейного программирования симплекс-методом с использованием офисного приложения Microsoft Excel необходимо сначала ввести данные задачи. Для этого создается новая рабочая книга Microsoft Excel, в свободные ячейки которой вносятся коэффициенты целевой функции, левой части ограничений, значения правой части ограничений.
Экранная форма для ввода условий задачи имеет следующий вид
(рис. 2.2.2):
В ячейках В4:С4 находятся значения коэффициентов целевой функции; в массиве В6:С8 –коэффициенты левой части ограничений; в столбце Е6:Е8значения правой части ограничений. Ячейки В2:С2соответствуют переменным задачи, а в ячейке Е2будет отображаться значение целевой функции. Сюда необходимо ввести формулу, по которой это значение рассчитывается, то есть . Для этого курсор ставится в ячейку и далее набирается следующее выражение: .
Имена ячеек можно набирать непосредственно с клавиатуры, либо делая на них ссылку мышью.
Значение целевой функции также можно рассчитать, используя надстройку «Мастер функций», а именно, функцию «СУММПРОИЗВ». Для этого необходимо выполнить следующие действия:
поставить курсор в поле Е2;
выбрать на панели инструментов кнопку ;
в окне «Категория» выбрать «Математические». В окне «Выберите функцию» «СУММПРОИЗВ» (рис. 2.2.3) и нажать «ОК»;
Ввести аргументы функции: в строку «Массив 1» выражение В2:С2, а в строку «Массив 2» выражение В4:С4 (можно, выделять соответствующие массивы с помощью мыши) (рис. 2.2.4) и нажать «ОК»;
После этого в ячейке Е2 появится текущее значение целевой функции, вычисленное по введенной формуле. Оно равно нулю, так как переменные в данный момент равны нулю.
Аналогично в ячейки D6:D8вводятся формулы для расчета левых частей ограничений (рис. 2.2.5):
Для ячейкиD6формула имеет вид ,а ее реализация в ячейке: или =СУММПРОИЗВ(В2:C2; В6:C6).
Для ячейкиD7формула имеет вид ,а ее реализация в ячейке: или = СУММПРОИЗВ(В2:C2; В7:C7).
Для ячейкиD8формула имеет вид ,а ее реализация в ячейке: или = СУММПРОИЗВ(В2:C2; В8:C8).
Как видно, формулы для расчета левой части ограничений отличаются друг от друга только именем второго массива (строчки коэффициентов ограничения), первый же массив (массив значений переменных) один и тот же. Поэтому можно ввести формулу один раз, а затем скопировать ее, сделав абсолютную ссылку на массив переменных В2:C2.
Для того, чтобы сделать абсолютную ссылку на определенный столбец, необходимо поставить символ $, перед буквой, обозначающей имя столбца. Например $В2:$C2.Чтобы зафиксировать строку, символ $, ставится перед номером строки: В$2:C$2.Если необходимо сделать абсолютную ссылку на конкретную ячейку (ячейки), символ $ ставится и перед именем столбца и перед номером строки: $В$2:$C$2.
Абсолютную ссылку на ячейку (ячейки) можно сделать, нажав клавишу F4, когда курсор находится в поле имени ячейки. При однократном нажатии клавиши будет сделана абсолютная ссылка на массив или ячейку ($В$2: $C$2). Если клавишу нажать дважды, будет сделана абсолютная ссылка на номер строки (В$2: C$2). При следующем нажатии клавиши ссылка будет сделана на имя столбца ($В2: $C2).
При данном способе реализации симплекс-метода достаточно сделать ссылку лишь на соответствующую строку: В$2: C$2. В то же время допустима и абсолютная ссылка на конкретный массив ячеек: $В$2: $C$2.
Таким образом, для ячейки D6формула будет иметь вид или = СУММПРОИЗВ(В$2: C$2;В6:C6) (в случае абсолютной ссылки на массив = СУММПРОИЗВ($В$2: $C$2;В6:C6)).
Затем эту формулу необходимо скопировать в ячейки D7иD8.Копировать формулу можно с помощью клавиш «Ctrl-Insert» копировать и клавиш «Shift-Insert» вставить. Другой способ копирования формул поставить курсор в ячейку, содержащую формулу и протянуть ее за правый нижний угол на все ячейки, в которые ее необходимо скопировать.
После этого экранная форма условий задачи будет иметь вид (рис. 2.2.6).
Для получения решения задачи используется надстройка «Поиск решения», которая находится в меню «Сервис».
В диалоговом окне «Поиск решения» (рис. 2.2.7) необходимо выполнить следующие действия:
Поставить курсор в поле «Установить целевую ячейку» и ввести адрес ячейки, в которой находится формула для расчета значения целевой функции (можно сделать ссылку на ячейку мышью). В примере это ячейка E2.
Выбрать критерий оптимизации целевой функции (максимизация, минимизация или точное значение). В примере это максимум.
Поставить курсор в поле «Изменяя ячейки» и ввести адрес массива, в котором находятся значения переменных. В примере это В2:C2.Адрес можно внести также с помощью выделения мышью соответствующих ячеек.
В окне «Ограничения» выбрать кнопку «Добавить», после чего появится окно «Добавление ограничения» (рис. 2.6.8).
В поле «Ссылка на ячейку» ввести адрес ячейки, в которой содержится левая часть ограничения. (Это можно сделать путем выделения мышью соответствующей ячейки на экране). В поле знака открыть список предлагаемых знаков и выбрать нужный. В поле «Ограничения» ввести адрес ячейки, содержащей правую часть ограничений. В примере первое ограничение: D6<=E6в диалоговом окне представлено следующим образом (рис. 2.2.9)
Нажать кнопку «Добавить»и аналогично ввести остальные ограничения. Если при вводе ограничений задачи возникает необходимость изменить или удалить ограничения, то для этого используются кнопки «Изменить» и «Удалить» соответственно.
Диалоговое окно надстройки «Поиск решения» после ввода данных имеет следующий вид (рис. 2.2.10)
Для обеспечения выполнения условия неотрицательности переменных, а также установления конкретных параметров решения задачи оптимизации используется кнопка «Параметры» (рис. 2.2.11)
Установка флажка «Линейная модель» обеспечивает ускорение процесса решения линейной задачи, а установление флажка «Неотрицательные значения» неотрицательность переменных.
Подтверждаются установленные параметры нажатием кнопки «ОК».
В окне «Результат поиска решения» приведены типы отчета: «Результаты», «Устойчивость», «Пределы», которые используются для анализа чувствительности. Чтобы получить отчет, необходимо выбрать соответствующий тип и нажать кнопку «ОК». Результаты каждого отчета будут выведены на отдельных листах рабочей книги с названиями: «Отчет по результатам 1», «Отчет по устойчивости 1», «Отчет по пределам 1» (рис. 2.2.13)
Если необходимо получить только решение задачи, достаточно нажать кнопку «ОК» в диалоговом окне «Результат поиска решения» (рис. 2.2.12), после чего на экране в соответствующих ячейках появятся значения переменных и целевой функции. В нашем примере значения переменных находятся в ячейках В2:C2,а значение целевой функции – в ячейке E2(рис. 2.2.14).
Итак, решение задачи найдено: .
Заметим, что надстройка «Поиск решения» позволяет получать решение и в том случае, если в условии задачи все или некоторые переменные могут принимать только целые значения. Для получения целочисленного решения приведенной выше задачи в описанный процесс необходимо внести некоторые дополнения.
Дополнения вносятся на этапе ввода ограничений. К имеющимся в задаче ограничениям необходимо добавить условие целочисленности переменных. Для этого в диалоговом окне «Поиска решения» надо выбрать кнопку «Добавить», в поле «Ссылка на ячейку» ввести адрес ячеек, содержащих значения переменных (в примере это ячейки В2:С2),а в поле ввода знака ограничения выбрать целое(цел). (рис.2.2.15)
Подтверждается ввод условия целочисленности нажатием кнопки «ОК». Если задача имеет альтернативное решение, то с помощью компьютера получаем только одно решение.
Чтобы провести анализ чувствительности, необходимо в диалоговом окне «Результаты поиска решения» выделить с помощью мыши требуемый тип отчета: «Результаты», «Устойчивость», «Пределы» (рис. 2.2.16) и нажать кнопку «ОК».
Результаты каждого отчета будут выданы на отдельных листах рабочей книги (рис. 2.2.17; 2.2.18; 2.2.19).
В таблице «Отчет по результатам» приведена информация о значениях переменных, целевой функции, а также статусе ограничений (рис. 2.2.17).
Рис. 2.2.17. Отчёт по результатам (первая таблица)
В первой таблице указано оптимальное значение целевой функции. Результат: 52 000.
Вторая таблица позволяет найти значения переменных принятия решения (результат: ).
В третьей таблице отчета указаны значения левой части ограничений при данных значениях переменных, статус ограничений (связующее или не связующее), а также разность между правой и левой частью. Для связующих ограничений разность равна нулю, для не связующих – больше нуля
«Отчет по устойчивости» состоит из двух таблиц (рис. 2.2.18).
В первой таблице приведена информация о переменных.
1. Результат решения, то есть значения переменных.
2. Нормированная стоимость, или альтернативная цена, которая для небазисных переменных показывает, как изменится значение целевой функции, если соответствующую переменную ввести в базис со значением, равным единице. Для базисных переменных нормированная стоимость равна нулю. В данной задаче обе переменные являются базисными, поэтому их альтернативная цена равна нулю.
3. Коэффициенты целевой функции при соответствующих переменных.
4. Предельные приращения коэффициентов целевой функции, при которых текущее базисное решение не изменится. Так, для переменной границы устойчивости коэффициента целевой функции составляют , поскольку максимальное увеличение коэффициента возможно на 200, а уменьшение на 50. Другими словами, текущее оптимальное решение не изменится, пока цена за единицу первого вида продукции будет находиться в пределах от 250 до 500 грн.
Рис. 2.2.18. Отчёт по устойчивости (вторая таблица)
Вторая таблица содержит данные об ограничениях.
1. В столбце «Результ. значение» указано значение левой части ограничений.
2. В столбце «Теневая цена» находится решение двойственной задачи. Теневая цена показывает, на сколько изменится значение целевой функции, если правая часть ограничения увеличится на одну единицу. В приведенном примере третье ограничение не является связующим, то есть, третий вид сырья используется не полностью. Таким образом, можно закупать его меньше на соответствующую величину, то есть на 100 единиц. Это уменьшит затраты как на закупку сырья, так и на его хранение. Теневая цена первого ограничения, равная 400, свидетельствует о том, что каждая дополнительная единица третьего вида сырья увеличит прибыль на 400 грн. Можно также утверждать, что это максимальная цена, которую можно заплатить за 1 единицу сырья первого вида.
3. В столбцах «Допустимое увеличение (уменьшение)» находятся предельные приращения правых частей ограничений, при которых текущий опорный план не изменится. В примере для первого вида сырья границы устойчивости , так как допустимое уменьшение возможно на 25 ед., а увеличение на 20 Для второго вида сырья границы устойчивости составляют (100; 140), а для третьего – (200; ) (здесь 1Е+30 равносильна ). Это означает, что, до тех пор, пока количество сырья будет находиться в данных пределах, оптимальное решение задачи не изменится.
«Отчет по пределам»для рассматриваемой задачи имеет следующий вид (рис. 2.2.19):
Рис. 2.2.19. Отчёт по пределам (третья таблица)
Необходимо отметить, что для задач целочисленного программирования отчеты по устойчивости и пределам не применимы.
Необходимо отметить, что при решении задачи с использованием надстройки «Поиск решения» не важно, в какой форме записана задача линейного программирования и содержит ли система ограничений полный единичный базис. Решение осуществляется так, как было описано выше.
Для составления и анализа двойственной задачи рассмотрим вначале дополнительно основные понятия двойственности.
При составлении двойственных задач будем пользоваться определением. Если задача задана на max то ограничение вида «£» будем называть согласованным или правильным, а «³» – неправильным, несогласованным. Если задача задана на min, то ограничение « ³ » – правильное, а « £ » – неправильное.
Для написания двойственной задачи сформулируем соотношение между отдельными элементами прямой и двойственной задач:
1. Количество двойственных переменных равно количеству ограничений исходной задачи (каждому ограничению ставится в соответствие двойственная переменная).
2. Целевая функция двойственной задачи имеет вид F = b1y1+ b2y2+…+ bmym.
3. Если Z ® max, то F ® min; если Z ® min, то F ® max (направление цели F противоположно направлению цели Z).
4. Количество ограничений двойственной задачи равно количеству переменных исходной задачи. Каждой переменной исходной задачи ставится в соответствие ограничение двойственной задачи.
5. Левая часть j-го ограничения двойственной задачи равна , а правая сj. Если , то j-е ограничение в двойственной задаче правильное. Если , то j-е ограничение – неправильное, если имеет любой знак, то j-е ограничение является равенством.
6. Если i-е ограничение исходной задачи правильное, то , если i-е ограничение исходной задачи неправильное, то , если i-е ограничение исходной задачи « = », то может иметь любой знак.
7. Матрицы исходной и двойственной задач взаимно транспонированные.
Для задачи оптимального выпуска продукции прямая и двойственная записываются в виде:
Прямая задача. Двойственная задача.
Рассмотрим составление двойственной задачи к исходной в общем случае на примере. Написать двойственную задачу к заданной задаче.
Прямая задача Двойственная задача
Решение двойственной задачи можно получить, исследуя решение исходной на основании первой и второй теорем двойственности.
Первая теорема двойственности.Если одна из пары двойственных задач имеет оптимальное решение, то вторая также имеет оптимальное решение, причем
Если одна из пары двойственных задач не ограничена, то у второй несовместна система ограничений.
Если одна из пары двойственных задач несовместна, то вторая несовместна или неограниченная.
Оптимальные значения переменных двойственной задачи можно определять из индексной строки последней симплексной таблицы по следующему правилу.
Чтобы найти надо:
1) в первой строке первой симплексной таблицы выбрать столбец, в котором находится базисная переменная. Пусть это будет столбец, соответствующий вектору ;
2) в этом столбце взять число, которое находится в индексной строке последней симплексной таблицы, т.е. ;
3) к этому числу прибавить коэффициент целевой функции из этого столбца. Это будет , т.е. .
Аналогично по второй, третьей строке и т. д. первой симплексной таблицы и элементам индексной строки последней таблицы находятся , и т. д.
При нахождении решения двойственной ЗЛП надо пользоваться правилом:
при умножении целевой функции на -1 двойственные переменные меняют знак.
при дописывании балансовых и искусственных переменных значения двойственных переменных не изменяются.
при умножении i-го ограничения на -1 i-я двойственная переменная меняет знак.
Значения двойственных переменных можно выписать из значения теневых цен.
4. Напишем двойственную задачу в примере 2.2.1.
5. Находим значения двойственных переменных из табл. 2.2.5.
Их можно выписать из теневых цен или из индексной строки последней симплекс-таблицы.
Читайте также: