Основы исследования операций том 1 - Вагнер Г

200 ГЛАВА 5

4. Пусть в первоначальном выражении для целевой функции коэффициент при xt равен 4 -f- 6j, а коэффициент при х3 равен 9 -j- 63.

а) С помощью приема, который был использован при выводе соотношений (5), а затем (6) в разд. 5.2, найдите неравенства для 6t и 63, определяющие интервалы вариаций 6t и 63, при которых базисное решение, соответствующее (F), продолжает оставаться оптимальным.

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

в) Пусть коэффициенты при х^ и х$ в первоначальном выражении для целевой функции равны соответственно ct и с3. Как и в предыдущем случае, изобразите графически область изменения с\ и с3, такую, что для любой точки, лежащей внутри этой области, базисное реше-

ний (I) равна 100 (вместо 120). Требуется вычислить значения констант в правых частях всех строк на каждой симплекс-итерации и, в частности, убедиться, что после заключительной итерации константа в правой части строки 2 принимает значение 185/у (325/7 — 20).

б) Рассмотрите упражнение п. а), положив константу в строке 2 системы уравнений (I) равной 120 — 325/7 (вместо 120).

в) Пусть константа в правой части строки 1 системы уравнений (I) равна 11 (вместо 15). Требуется вычислить значения констант в правых частях всех строк на каждой симплекс-итерации и убедиться в том, что базисное решение, соответствующее (F), является по-прежнему оптимальным.

г) Рассмотрите упражнение п. в), положив константу в строке 1 системы уравнений (I) равной 20 (вместо 15).

д) Пусть константа в правой части строки 1 системы уравне-

6. Остается ли базисное решение, соответствующее (F), допустимым, если константы в правых частях строк 1, 2 и 3 принимают соответственно значения

а) 20, 110 и 130? б) 25, 75 и 215?

в) 15, 30 и 185? г) 18, 150 и 40? д) 22, 150 и 80?

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

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 201

если базисное решение, соответствующее (F), остается допустимым. [В противном случае докажите, что базис на этапе (F) оказывается недопустимым.]

7. Пусть в правых частях строк 1 и 3 имеем соответственно

15 + 6i и 100 + 63.

а) Требуется найти неравенства для 64 и 63, определяющие интер-

валы вариаций 6t и 63, при которых базисное решение, соответствующее (F), остается допустимым.

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

в) Пусть в правых частях строк 1 и 3 имеем соответственно bt и Ъ$. Как и в предыдущем случае, изобразите графически область изменения bi и Ьз, такую, что для любой точки, лежащей внутри этой области, базисное решение, соответствующее (F), остается допустимым.

г) Рассмотрите упражнение п. в), положив значение константы

вправой части строки 2 равной

1)121;

2) 119.

В упражнениях 8—11 за основу берется модель распределения ресурсов, рассмотренная в разд. 4.4. Эти упражнения служат для закрепления материала, изложенного в разд. 5.5.

8. Требуется сформулировать двойственную задачу при усло-

1, 6 и —8, а в выражении для целевой функции вместо коэффициента 5 стоит коэффициент —3;

д) вводится дополнительная переменная z, коэффициенты при которой в строках 1, 2 и 3 равны соответственно 1, 1 и 18;коэффициент при z в выражении для целевой функции берется равным 13;

е) имеет место дополнительное ограничение 4a;j + 7z2 — 5х3 — 6а;4 ^ 50;

ж) имеют место все модификации исходной модели, указанные

вп. а) — е);

3)требуется найти два допустимых решения и соответствующие

значения целевой функции для двойственной задачи, представленной соотношениями (1) и (2) в разд. 5.5.

9. Повторите все симплекс-итерации, выполненные в разд. 4.4. а) Чему равны пробные значения переменных двойственной зада-

чи на каждом этапе итерационного процесса?

двойственной задачи перестает быть допустимым? Какие значения принимает при этом целевая функция двойственной задачи?

ции, рассмотренной в разд. 4.4, равен 9 + 6. Определите верхний предел значений б, при котором базисное решение, соответствующее (F) (разд. 5.1), перестает быть оптимальным. При этом следует воспользоваться тем ограничением соответствующей двойственной

задачи, если в правых частях строк 1, 2 и 3 имеем соответственно

Может ли значение целевой функции получить положительное приращение, превышающее 13/7б при 6 >> 325/6i? Полученный результат оцените с «экономической»точки зрения (интерпретация модели дана в гл. 2).

г) Пусть коэффициент при х-^ в строке 3 равен 5 -f- б. В каких пределах может меняться б, не нарушая оптимальности базисного решения, соответствующего (F)?

д) Пусть коэффициент при х2 в строке 1 равен 1 + б. В каких пределах может меняться б, не нарушая оптимальности базисного решения, соответствующего (F)?

е) Пусть в строки 1, 2 и 3 введена новая переменная z с коэффициентами 1, 1 и 18 соответственно. Чему равно наименьшее значение коэффициента при z в выражении для целевой функции, для которого базисное решение, соответствующее (F), продолжает оставаться оптимальным?

ж) Рассмотрите упражнение п. е), предположив, что коэффициент при z в строке 3 равен 16.

з) Чему равны коэффициенты при z в строках 1, 2 и 3 на заключительной итерации (F), если выполняются условия, сформулированные в п. е)? п. ж)?

и) Пусть коэффициент при xi в строке 3 равен 3 -)- б. Как найти интервал, в пределах которого может меняться б, не нарушая оптимальности полученного базиса для (F)?

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 203

а) Какая переменная подлежит исключению из базиса на первой итерации, если: 1) константа в правой части второго соотношения (2) равна 10 (вместо 8)? 2) константа в правой части первого соотношения равна 10 (вместо 5)? 3) константа в правой части первого соотношения равна 15 (вместо 5), а константа в правой части второго соотношения равна 10 (вместо 8)?

б) Пусть при первой итерации из базиса исключается х$. Требуется определить, какая переменная вводится в очередной базис и чему

1, 0 и 2; 8, 8 и 8; 4, 1 и 3; V2 , V2 и V2 .

в) Рассмотрите упражнение п. б), предположив дополнительно,

разд. 5.9 положить равной: а) 140; б) 160; в) 170.

Вкаждом случае найдите оптимальное решение.

14.Пусть константа в правой части соотношения, соответствую-

щего строке 1 системы уравнений (I) (разд. 5.1), равна 5 (вместо 15). Требуется найти оптимальное решение. Для этого следует воспользоваться двойственным симплекс-алгоритмом, начав с рассмотрения системы уравнений (F), видоизмененной с учетом указанного выше

условия.

15. Поясните значение следующих терминов:

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

скрытые доходы (скрытая прибыль); допустимое решение двойственной задачи; второстепенные ограничения;

переменные, значения которых ограничены сверху.

УПРАЖНЕНИЯ НА РАЗВИТИЕ ВЫЧИСЛИТЕЛЬНЫХ НАВЫКОВ

16. Рассмотрим следующую задачу: максимизировать — 2xt — 1ж2 + 3-г3 — 2ж4

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

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

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

г) Пусть коэффициенты при х2 и х3 в выражении для целевой функции равняются соответственно —1 -{- б2 и 3 + 63. Определит» систему неравенств для 62 и 63, при выполнении которых базис, полученный в п. а), продолжает оставаться оптимальным. Изобразите графически область изменения 62 и 63, определяемую упомянутыми выше неравенствами.

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

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 205

е) Пусть в правых частях первых двух соотношений (1) имеем соответственно 7 -(- 6t и 12 -f- б2. Найдите неравенства для б4 и б2, при выполнении которых базис, полученный в п. а), продолжает оставаться допустимым. Изобразите графически область изменения $1 и б2, определяемую этими неравенствами.

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

з) Дайте экономическую интерпретацию переменных двойственной задачи и поясните ее на численных примерах.

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

к) Пусть вводятся новые управляемые переменные х8 и х9. Допустим, что коэффициенты при х8 в соотношениях (1) равны соответственно о, —3 и 1, а коэффициент при х8 в выражении для целевой функции равен 2. Пусть коэффициенты при хд в соотношениях (1) равны соответственно —2, 10 и 12, а коэффициент при х9 в выражении для целевой функции равен —4. Можно ли при этом улучшить решение, полученное в п. а)? Если можно, то покажите, каким образом это достигается. Если нельзя, покажите, что произойдет при включении в базис переменной х9.

л) Вычислите коэффициенты при х& и х9 в уравнениях (2).

м) Пусть коэффициент при х^ в первом соотношении (1) равен 1 -f- б- Определите, в каких пределах можно изменять б, не нарушая оптимальности решения, полученного в п. а).

н) Пусть коэффициент при xi во втором соотношении (1) равен

— 1 -f б. Определите, в каких пределах можно изменять б, не нарушая оптимальности решения, полученного в п. а).

о) Рассмотрите упражнения п. м) и н) для случая, когда варьируется коэффициент при х^.

17. В указанных ниже задачах а) — д) требуется:

найти оптимальные значения управляемых переменных и соответствуюпдее значение целевой функции;

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

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

сформулировать двойственную задачу; определить оптимальные значения переменных и соответствую-

щее значение целевой функции двойственной задачи;

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

Рассмотрите:

а) задачу, сформулированную в разд. 1.6 (см. также упражнение 18 в гл. 4);

18. Предположим, что после некоторой итерации при решении задачи линейного программирования получаются соотношения а) или б). Напомним, что х0 максимизируется, а ж4, х5, х$ — свободные переменные, соответствующие первому, второму и третьему ограничениям (для ресурса А, для ресурса В и для ресурса С). Требуется:

найти оптимальное решение и проверить, является ли оно единственным;

определить дополнительную выгоду, полученную за счет единичного приращения каждого ресурса;

найти оптимальные значения переменных соответствующей двойственной задачи;

дать физическую интерпретацию переменных двойственной задачи

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 20?

а) Сформулируйте двойственную задачу и покажите, что одним из допустимых ее решений является следующее:

3xi + 4.г2 + 5а:3 + 6а;4 < 24,

—1*1 + 1х2 - 2х3 + 2аг4 < 4, *, > 0 (; = 1, 2, 3, 4).

а) Сформулируйте двойственную задачу и покажите, что одним из ее допустимых решений является следующее:

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

в) Введите в упражнение п. б) дополнительное ограничение

*i + xz + %з + xk + ^s ^s 8 и найдите оптимальные решения исходной и двойственной задач.

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

вычислить соответствующие значения переменных и значение

208 ГЛАВА 5

с помощью метода больших штрафов. Найдите для этих моделей

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

В каждом случае требуется показать, каким образом находится

алгоритма, с соответствующими пробными решениями исходной задачи, получаемыми обычным симплексным методом (гл. 4).

25. а) С помощью двойственного симплекс-алгоритма найдите решение задачи, представленной соотношениями (1) и (2) разд. 5.5.

б) Рассмотрим систему уравнений (I), приведенную в начале разд. 5.1. Введем в базис переменную х4, исключив из него х5. Требуется доказать, что получающиеся при этом пробные значения переменных двойственной задачи являются допустимыми. Являются ли допустимыми базисные переменные исходной задачи? В случае положительного ответа покажите, как выглядят оптимальные решения исходной и двойственной задач. Если ответ окажется отрицательным, найдите оптимальные решения исходной и двойственной задач, воспользовавшись двойственным симплекс-алгоритмом.

26. Рассмотрите задачу, сформулированную в упражнении 16. Требуется выяснить, остается ли оптимальное решение упомя-

АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ И ДВОЙСТВЕННАЯ ЗАДАЧА 209

нутой выше задачи допустимым, если ввести дополнительное ограничение вида:

мальное решение двойственной задачи и определить оптимальное решение соответствующей исходной задачи (Примечание: для этого потребуется не более пяти итераций);

г) найти (с помощью симплексного алгоритма) оптимальное решение исходной задачи и вычислить затем оптимальное решение соответствующей двойственной задачи (Примечание: для этого потребуется не более пяти итераций);

д) найти оптимальные решения исходной и двойственной задач

вслучае, когда ri = 9 (вместо 8).

28.Решите сформулированные ниже задачи, используя прием,

рассмотренный в разд. 5.10:

а) максимизировать ба^ -|- 14;Г2 + 24г3 + 20;г4 при ограничениях

+ 4ж4 ^ 4, 1 (/ - 1, 2, 3, 4);