Эти коэффициенты можно представить в виде следующей суммы

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 11Следующая ⇒

, i = 1,…,n.

Так как план оптимален для t = t₀ , i = 1,…,n,

и, следовательно, совместна система неравенств (из неотрицательности коэффициентов)

, i = 1,…,n. (2)

Для всех неравенства системы можно переписать в следующем виде

,

а для всех

.

Введем следующие обозначения

(3)

Таким образом, можно утверждать, что если , (4)

то найденный оптимальный план для t₀ будет оставаться оптимальным для всех t, удовлетворяющих (4).

Если область изменения параметра t, заданная в технических условиях, не накрывается отрезком , то возникает необходимость исследования параметрической модели для и .(Это в том случае, если хотя бы или ).

Исследуем для . Пусть

Тогда в опорный план (в базис) необходимо ввести переменную, соответствующую столбцу k (x _k).

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

Для нового плана получаем, что , т.е. наше становится левой границей нового интервала.

Находится

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

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

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

Это соответствует (5)

и все коэффициенты в k -м столбце неположительны.

При условие (5) соблюдается для любого значения параметра, а значит задача неразрешима на всей оси t.

Если , то (5) выполняется для всех значений

Если , то (5) выполняется при

Т.о. в первом случае наша задача неразрешима слева от t₁, а в противном – справа от t₁.

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

Если и в этом случае процесс окончился выявлением неразрешимости задачи:

и в столбце коэффициентов ,

то дальнейший анализ зависит от знака . Если , то задача неразрешима всюду.

Или если

и ,

и если при – задача неразрешима и при – неразрешима, то она вообще неразрешима на всей оси.

Алгоритм метода последовательного улучшения плана для параметрической модели обладает некоторыми особенностями. Вместо одной строки критерия вводятся три дополнительные строки и для случая 1⁰ и две строки и в случае 2⁰.

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

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

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

Если в модели , то этот процесс может закончиться раньше, как только область анализа охватит этот интервал.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры