Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






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

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

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


Определение выводимой из базиса переменной.

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

  • поочередно разделить значения элементов столбца

на соответствующие положительные элементы ключевого столбца:

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


Выбор начального решения

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

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


Анализ ресурсов.

Предположим, что для некоторых значений А, b и с найден оптимальный план х*, максимизирующий суммарный доход . Достаточно естественным представляется вопрос: как будет изменяться оптимальный план х* при изменении компонент вектора ограничений b и, в частности, при каких вариациях bоптимальный план х* останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчивости х* имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов bi могут существенно колебаться после принятия планового решения х* .

Когда вектор ограничений bизменяется на ∆bили, как еще говорят, получает приращение ∆b, то возникают соответствующие вариации для оптимального плана и значения целевой функции . Допустим, приращение ∆b таково, что оно не приводит к изменению оптимального базиса задачи, т. е. . Определим функцию F(b), возвращающую оптимальное значение целевой функции задачи для различных значений вектора ограничений b (1.55)

Рассмотрим отношение ее приращения к при-

ращению аргумента ∆b. Если для некоторого i устремить , то мы получим (1.56)

Учитывая, что в соответствии с теоремой 1.5 (1.57) и подставив (1.57) в (1.56), приходим к выражению (1.58)Из формулы (1.58) вытекает экономическая интерпретация оптимальных переменных двойственной задачи. Каждый элемент ui* может рассматриваться как предельная (мгновенная) оценка вклада г-го ресурса в суммарный доход F при оптимальном решении х*. Грубо говоря, величина и* равна приросту дохода, возникающему при увеличении ресурса i на единицу при условии оптимального использования ресурсов.

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

На основе теорем двойственности для пары задач ЛП в общей формемогут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.

Если при использовании оптимального плана прямой задачи i-e ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т. е. если

В рамках рассматриваемой задачи производственного планирования это означает, что если некоторый ресурс bi имеется в избыточном количестве (не используется полностью при реализации оптимального плана), то i-e ограничение становится несущественным и оценка такого ресурса равна 0.

Если при использовании оптимального плана двойственной задачи j-e ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если

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


Анализ цен

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

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


Целочисленное деление.

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

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

Проблемы:

- округление оптимальных значений переменных в непрерывном решении может привести к недопустимому решению;

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

Метод ветвей и границ

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

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

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


Последнее изменение этой страницы: 2017-09-22

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...