25. Анализ цен
С точки зрения экономической интерпретации задача исследования параметрической устойчивости может быть рассмотрена как изучение тех пределов колебания цен на продукцию управляемого предприятия (фирмы), при которых принятый план выпуска продукции продолжает оставаться оптимальным.
Т
акже
содержание проблемы устойчивости
оптимального плана
ЗЛП по отношению к вариациям целевой
функции может быть
проиллюстрировано с помощью первой
геометрической интерпретации.
На рис.
1.10 изображено
множество допустимых
планов D
некоторой
задачи ЛП. Как видно из рисунка, целевая
функция f (ее поведение отражает линия
уровня, показанная жирным пунктиром)
достигает экстремального значения
в точке х
, а
изменению ее коэффициентов от с к с' или
с"
на
рисунке
соответствует поворот линии уровня
относительно х'.
Активным,
т. е. обращающимся в равенство, ограничениям
в точке х
соответствуют
линии (1) и (2). До тех пор, пока при повороте,
вызванном изменением вектора с, линия
уровня целевой
функции не выходит за пределы образуемого
линиями ограничений
конуса, х
остается
оптимальным планом. Как показано на
рис. 1.10, этот
план не меняется при переходе от с к с',
и, наоборот,
при переходе от с к с"
линия уровня
целевой функции f(x)
= c"x
пересечет
линию (2), что вызовет изменение оптимального
базисного плана, которым теперь станет
точка х
26. Целочисленное деление.
Задачи оптимизации, в которых искомые переменные должны быть целочисленными, называются задачами целочисленного программирования. В том случае, когда ограничения и целевая функция представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования.
При графическом решении задач целочисленного программирования требование целочисленности отражается в том, что решением задачи могут быть только точки, находящиеся на пересечении целочисленных значений.
Проблемы:
- округление оптимальных значений переменных в непрерывном решении может привести к недопустимому решению;
- оптимальным решением целочисленной задачи может оказаться такое решение, в котором значения переменных не являются ближайшими к оптимальному решению непрерывной задачи.
Метод ветвей и границ
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.
Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.
Вычисление нижней границы является важнейшим элементом данной схемы. Для простейшей задачи размещения один из способов ее построения состоит в следующем.