a) Покажите, что оптимальное базисное решение содержит обе переменные х1 и хг, и что интервалы допустимости для правых частей ограничений, полученные при условии их независимости, имеют вид -3 < D, < 6 и -3 <D2 < 6.

b) Предположим, что правые части ограничений одновременно увеличиваются на величину Д > 0. Сначала докажите, что базисное решение остается допустимым для всех Д > 0. Далее покажите, что достаточное правило допустимости дает правильный ответ только тогда, когда 0 < Д < 3, не дает ответа при 3 < Д < 6, и не применимо - когда Д > 6.

9. Покажите, что достаточное правило допустимости из упражнения 7 является следствием неравенства

Обратная матрица \( Вектор правых частей

оптимального решения

ограничении исходной задачи)

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

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

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

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

Пример 4.5.3

Предположим, что фабрика игрушек TOYCO изменила конструкцию выпускаемых моделей, и теперь для их производства необходима четвертая сборочная операция. Ежедневный фонд рабочего времени этой операции составляет 500 минут. Время выполнения этой операции при сборке одной игрушки различных видов составляет соответственно 3, 1 и 1 минуту. В результате получаем новое ограничение: Зх, + х2 + + лг3<500. Это ограничение является избыточным, поскольку оно удовлетворяется при текущем оптимальном решении хг - 0, х, = 100 и хг = 230. Таким образом, текущее оптимальное решение остается неизменным.

Теперь предположим, что в модели фабрики игрушек TOYCO время выполнения новой четвертой операции составляет соответственно 3, 3 и 1 минуту при сборке одной игрушки каждого вида. В этом случае четвертое ограничение Зх, 4- Ъхг + + х3< 500 не будет избыточным, и текущее оптимальное решение ему не удовлетворяет. Мы должны ввести новое ограничение в симплекс-таблицу, где представлено текущее оптимальное решение.

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

Новая х7-строка = старая х.-строка - [3 х (х2-строка) + 1 х (х3-строка)] В результате получим новую симплекс-таблицу.

С помощью двойственного симплекс-метода находим новое оптимальное решение х, = 0, х2 = 90, х3 = 230 и z = 1330 долл. (проверьте!).

УПРАЖНЕНИЯ 4.5.3

1. Пусть в модели фабрики игрушек TOYCO время выполнения четвертой операции составляет соответственно 4, 1 и 2 минуты при сборке одной игрушки каждого вида. Найдите оптимальное решение задачи, предполагая, что фонд рабочего времени четвертой операции составляет а) 570 минут, Ь) 548 минут.

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

Примените описанную процедуру к следующей задаче ЛП.

Максимизировать z = 5х, + 6х2 + Зх3

при ограничениях

5х, + 5х2 + Зх3 < 50, х, + хг - хг < 20, 7х, + 6х2 - 9х3 < 90, 5х, + 5х2 + 5х3 < 35, 12х, + 6х2<90, х2 - 9х3 < 20,

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

В этом разделе рассмотрим два фактора, которые могут изменить оптимальность текущего решения.

1. Изменение коэффициентов целевой функции.

2. Добавление в модель нового вида производственной деятельности (т.е. добавление новой переменной).

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

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

1. С использованием методов 1 и 2 из раздела 4.2.3 вычисляются значения двойственных переменных.

2. На основе значений двойственных переменных по формуле 2 из раздела 4.2.4 вычисляются коэффициенты z-строки.

При этом возможны два варианта.

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

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

Пример 4.5.4

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

максимизировать z = 2х1 + Зхг + Ахг

Таким образом,

новые коэффициенты при базисных переменныхх2, х3 их, = (3, 4, 0).

По формулам метода 1 из раздела 4.2.3 вычислим значения двойственных переменных.

( \ 2

(Л..Л) =(ЗЛ0)

3-Л,о

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