Изменения, влияющие на оптимальность решения.

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

.

Отсюда следует, что на оптимальность решения влияют только коэффициенты с, целевой функции (и, следовательно, вектор ) и/или стоимости ресурсов, представленные векторами . Рассмотрим последовательно каждый фактор, влияющий на оптимальность решения.

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

Вычислительная процедура заключается в следующем.

1. Вычисляется вектор двойственных цен для нового вектора коэффициентов .

2. Вычисляются разности для текущей небазисной переменной . При этом возможны два варианта:

 

А). Если условие оптимальности выполняется, текущее решение остается опти­мальным, но значение целевой функции может измениться.

Б). Если условие оптимальности не выполняется, следует применить (прямой) симплекс-метод для получения нового оптимального решения.

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

Максимизировать

.

Поскольку текущее базисное решение состоит из переменных х₂, х₃ и х₆, имеем . Вычислим вектор двойственных цен.

.

Разности для небазисных переменных , и вычисляются по формуле :

,

,

.

Отметим, что здесь использовалось новое значение коэффициента целевой функции .

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

.

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

Максимизировать .

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

Отсюда следует, что переменную необходимо включить в базисное решение. Имеем следующую симплекс-таблицу.

Базис Решение

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

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

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

Пусть в задаче о фабрике игрушек TOYCO нас интересует интервал допустимости для значения фонда рабочего времени первой операции. Заменим вектор вектором

.

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

.

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

Фонд рабочего времени операции

или

Фонд рабочего времени операции

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

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

.

Для вычисления нового значения целевой функции сначала найдем значения двойственных цен.

.

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

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

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

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

1. Новое ограничение является избыточным. Это означает, что новое ограничение выполняется при текущем оптимальном решении.

 

2. Новое ограничение не выполняется при ткущем оптимальном решении. В этом случае необходимо применить двойственный симплекс-метод, чтобы получить (или хотя бы попытаться получить) новое оптимальное решение.

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

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

Базис Решение

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

Новая -строка Старая -строка ( -строка) ( -строка)

В результате получим новую симплекс-таблицу.

Базис Решение

С помощью двойственного симплекс-метода находим новое оптимальное решение , , и

 

Тема 9. Сетевые модели

Сетевые модели (СМ) или методы сетевого планирования и управления (СПУ) — способ исследования и проектирования сложных систем, анализа и оптимизации процессов, состоящих из связанных подсистем или совокупности последовательных и взаимосвязанных работ и событий.

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

Анализ сетевой модели, представленной в графической или табличной

(матричной) форме, позволяет,

· во-первых, более четко выявить взаимосвязи этапов реализации проекта и

· во-вторых, определить наиболее оптимальный порядок выполнения этих этапов

в целях, например, сокращения сроков выполнения всего комплекса работ.