Гельруд Я.Д. Линейное программирование. Учебно-методический комплекс
Подождите немного. Документ загружается.
б) 3
3
/
4
x
1
+ 5
2
/
7
x
2
+ 9x
3
+ 12
3
/
7
x
4
?
в) 3
1
/
2
x
1
+ 5x
2
+ 9x
3
+ 12x
4
?
г) 6
1
/
2
x
1
+ 5
2
/
7
x
2
+ 9x
3
+ 11x
4
?
д) 4x
1
+ 5
2
/
7
x
2
+ 8x
3
+ 12
3
/
7
x
4
?
е) 4x
1
+ 5x
2
+ 7
1
/
2
x
3
+ 12x
4
?
ж) 4x
1
+ 5x
2
+ 13
1
/
2
x
3
+ 12x
4
?
з) 4x
1
+ 5
2
/
7
x
2
+ 13x
3
+ 12x
4
?
Для каждого из этих случаев определите, какую из переменных следует
включить в очередной базис, если базисное решение для (F) оказывается
неоптимальным.
3. Остается ли базисное решение, соответствующее (F), оптимальным, если
максимизируемая целевая функция (в ее первоначальной записи) имеет вид
а) 7x
1
+ 8x
2
+ 14x
3
+ 18x
4
?
б) 8x
1
+ 9x
2
+ 15x
3
+ 21x
4
?
в) 11x
1
+ 16x
2
+ 32x
3
+ 46x
4
?
г) 12x
1
+ 17x
2
+ 33x
3
+ 45x
4
?
д) 33x
1
+ 50x
2
+ 103x
3
+ 163x
4
?
Для каждого из этих случаев определите, какую из переменных следует
включить в очередной базис, если базисное решение, соответствующее (F),
оказывается неоптимальным.
4. Пусть в первоначальном выражении для целевой функции коэффициент
при x
1
равен 4 +δ
1
, а коэффициент при x
3
равен 9 + δ
3
:
а) с помощью приема, который был использован при выводе соотношений
(4.2.5), а затем (4.2.6) в разд. 4.2, найдите неравенства для δ
1
и δ
3
,
определяющие интервалы вариаций δ
1
и δ
3
, при которых базисное решение,
соответствующее (F), продолжает оставаться оптимальным;
б) изобразите графически область, определяемую неравенствами,
полученными в пункте а);
в) пусть коэффициенты при x
1
и x
3
в первоначальном выражении для
135
целевой функции равны соответственно с
1
и с
3
. Как и в предыдущем случае,
изобразите графически область изменения с
1
и с
3
, такую, что для любой точки,
лежащей внутри этой области, базисное решение, соответствующее (F),
является оптимальным.
5. а) пусть константа в правой части строки 2 системы уравнений (I) равна
100 (вместо 120). Требуется вычислить значения констант в правых частях
всех строк на каждой симплекс-итерации и, в частности, убедиться, что после
заключительной итерации константа в правой части строки 2 принимает
значение
185
/
7
(
325
/
7
– 20);
б) рассмотрите упражнение п. а), положив константу в строке 2 системы
уравнений (I) равной 120 –
325
/
7
(вместо 120);
в) пусть константа в правой части строки 1 системы уравнений (I) равна 11
(вместо 15). Требуется вычислить значения констант в правых частях всех
строк на каждой симплекс-итерации и убедиться в том, что базисное решение,
соответствующее (F), является по-прежнему оптимальным;
г) рассмотрите упражнение п. в), положив константу в строке 1 системы
уравнений (I) равной 20 (вместо 15);
д) пусть константа в правой части строки 1 системы уравнений (I) равна 15
+ δ. Покажите, что базисное решение, соответствующее (F), остается
допустимым, если –
5
/
10
≤ δ ≤
325
/
61
[см. соотношение (4.3.2) разд. 4.3];
е) пусть константа в правой части строки 3 системы уравнений (I) равна 100
+ δ. Для какого интервала значений δ базисное решение, соответствующее (F),
остается допустимым?
6. Остается ли базисное решение, соответствующее (F), допустимым, если
константы в правых частях строк 1, 2 и 3 принимают соответственно значения
а) 20, 110 и 130?
б) 25, 75 и 215?
в) 15, 30 и 185?
г) 18, 150 и 40?
136
д) 22, 150 и 80?
Для каждого из этих случаев определите оптимальные значения каждой
переменной и соответствующее значение целевой функции, если базисное
решение, соответствующее (F), остается допустимым. [В противном случае
докажите, что базис на этапе (F) оказывается недопустимым.]
7. Пусть в правых частях строк 1 и 3 имеем соответственно 15 + δ
1
и
100 + δ
3
:
а) требуется найти неравенства для δ
1
и δ
3
, определяющие интервалы
вариаций δ
1
и δ
3
, при которых базисное решение, соответствующее (F),
остается допустимым;
б) изобразите графически область, определяемую неравенствами,
полученными в пункте а);
в) пусть в правых частях строк 1 и 3 имеем соответственно b
1
и b
3
. Как и в
предыдущем случае, изобразите графически область изменения b
1
и b
3
, такую,
что для любой точки, лежащей внутри этой области, базисное решение,
соответствующее (F), остается допустимым;
г) рассмотрите упражнение пункте в), положив значение константы в
правой части строки 2 равной
1) 121;
2) 119.
Тема 5
В упражнениях 1–4 за основу берется модель распределения ресурсов,
рассмотренная в разд. 3.2. Эти упражнения служат для закрепления материала,
изложенного в разд. 5.3.
1. Требуется сформулировать двойственную задачу при условии, что:
а) целевая функция (подлежащая максимизации) имеет вид
6x
1
+ 8x
2
+ 7x
3
+ 12x
4
;
б) в правых частях строк 1, 2 и 3 имеем соответственно 25, 80 и 150,
137
в) коэффициенты при x
3
в строках 1, 2, 3 равны соответственно 1, 4 и 9;
г) коэффициенты при x
2
в строках 1, 2, 3 равны соответственно 1, 6 и –8, а в
выражении для целевой функции вместо коэффициента 5 стоит коэффициент
–3;
д) вводится дополнительная переменная z, коэффициенты при которой в
строках 1, 2 и 3 равны соответственно 1, 1 и 18; коэффициент при z в
выражении для целевой функции берется равным 13;
е) имеет место дополнительное ограничение
4x
1
+ 7x
2
– 5x
3
– 6x
4
≤50;
ж) имеют место все модификации исходной модели, указанные в п. а) – е);
з) требуется найти два допустимых решения и соответствующие значения
целевой функции для двойственной задачи, представленной соотношениями
(5.3.1) и (5.3.2) в разд. 5.3.
2. Повторите все симплекс-итерации, выполненные в разд. 3.2:
а) чему равны пробные значения переменных двойственной задачи на каждом
этапе итерационного процесса?
б) возникают ли ситуации, когда соответствующее решение двойственной
задачи перестает быть допустимым? Какие значения принимает при этом
целевая функция двойственной задачи?
3. Найдите оптимальные значения переменных двойственной задачи,
предположив, что базисное решение, соответствующее (F) в разд. 4.1, является
оптимальным, а коэффициенты при x
1
и x
3
в выражении для целевой функции
равняются соответственно:
а) 7 и 14; г) 12 и 33;
б) 8 и 15; д) 33 и 103.
в) 11 и 32;
4. а) пусть коэффициент при x
4
в выражении для целевой функции,
рассмотренной в разд. 3.2, равен 9+δ. Определите верхний предел значений δ,
при котором базисное решение, соответствующее (F) (разд. 4.1), перестает
138
быть оптимальным. При этом следует воспользоваться тем ограничением
соответствующей двойственной задачи, которое связано с x
4
;
б) найдите оптимальное значение целевой функции исходной задачи, если в
правых частях строк 1, 2 и 3 имеем соответственно:
16, 120 и 100 15, 120 и 101 16, 120 и 101 14, 121 и 101
14, 120 и 100 15, 120 и 99 14, 120 и 99 16, 119 и 99:
в) пусть в правой части уравнения в строке 1 стоит 15 + δ. Может ли
значение целевой функции получить положительное приращение,
превышающее
13
/
7
δ при δ >
325
/
61
? Полученный результат оцените с
«экономической» точки зрения (интерпретация модели дана в гл. 1);
г) пусть коэффициент при x
2
в строке 3 равен 5 + δ. В каких пределах может
меняться δ, не нарушая оптимальности базисного решения, соответствующего
(F)?
д) пусть коэффициент при x
2
в строке 1 равен 1 + δ. В каких пределах может
меняться δ, не нарушая оптимальности базисного решения, соответствующего
(F)?
е) пусть в строки 1, 2 и 3 введена новая переменная z с коэффициентами 1, 1
и 18 соответственно. Чему равно наименьшее значение коэффициента при z в
выражении для целевой функции, для которого базисное решение,
соответствующее (F), продолжает оставаться оптимальным?
ж) рассмотрите упражнение п. е), предположив, что коэффициент при z в
строке 3 равен 16;
з) чему равны коэффициенты при z в строках 1, 2 и 3 на заключительной
итерации (F), если выполняются условия, сформулированные в п. е)? п. ж)?
и) пусть коэффициент при x
1
в строке 3 равен 3+δ. Как найти интервал, в
пределах которого может меняться δ, не нарушая оптимальности полученного
базиса для (F)?
5. возьмем за основу задачу, представленную соотношениями (5.5.1) и
139
(5.5.2) разд. 5.5:
а) какая переменная подлежит исключению из базиса на первой итерации,
если: 1) константа в правой части второго соотношения (5.5.2) равна 10
(вместо 8)? 2) константа в правой части первого соотношения равна 10 (вместо
5)? 3) константа в правой части первого соотношения равна 15 (вместо 5), а
константа в правой части второго соотношения равна 10 (вместо 8)?
б) пусть при первой итерации из базиса исключается x
5
. Требуется
определить, какая переменная вводится в очередной базис и чему равняется ее
новое значение, если коэффициенты при x
1
, x
2
и x
3
в выражении для целевой
функции равняются соответственно:
1, 0 и 2; 8, 8 и 8; 4, 1 и 3;
1
/
2
,
1
/
2
и
½
;
в) рассмотрите упражнение п. б), предположив дополнительно, что
коэффициент при x
2
во втором соотношении (5.5.2) равен 2 (вместо –2);
г) рассмотрите упражнение п. б), предположив, что коэффициент при x
3
во
втором соотношении (5.5.2) равен 2 (вместо 4);
д) как изменятся результаты, если при первой итерации из базиса
исключается x
4
, а не x
5
?
6. Проверьте, останется ли допустимым базисное решение,
соответствующее (F), если константу в правой части соотношения (5.6.1) разд.
5.6 положить равной:
а) 140;
б) 160;
в) 170.
В каждом случае найдите оптимальное решение.
7. Пусть константа в правой части соотношения, соответствующего строке
1 системы уравнений (I) (разд. 4.1), равна 5 (вместо 15). Требуется найти
оптимальное решение. Для этого следует воспользоваться двойственным
симплекс-алгоритмом, начав с рассмотрения системы уравнений (F),
видоизмененной с учетом указанного выше условия.
140
8. Рассмотрим следующую задачу:
максимизировать –2x
1
– 1x
2
+ 3x
3
– 2x
4
при ограничениях
1x
1
+ 3x
2
– 1x
3
+ 2x
4
≤7, (ресурс А),
–1x
1
– 2x
2
+ 4x
3
≤20 (ресурс В), (1)
–1x
1
– 4x
2
+ 3x
3
+ 8x
4
≤ 10 (ресурс С),
x
1
≥0, x
2
≥0, x
3
≥0, x
4
≥0.
Если ввести свободные переменные x
5
, x
6
и x
7
, то после выполнения
последней симплекс-итерации получим
1x
0
+
5
7
x
1
+
5
12
x
4
+
5
1
x
5
+
5
4
x
6
=11 (строка 0),
10
3
x
1
+1x
2
+
5
4
x
4
+
5
2
x
5
+
10
1
x
6
= 4 (строка 1), (2)
–
10
1
x
1
+1x
3
+
5
2
x
4
+
5
1
x
5
+
10
3
x
6
= 5 (строка 2),
2
1
x
1
+10x
4
+1x
5
–
2
1
x
6
+1x
7
= 11 (строка 3).
а) покажите, чему равняются оптимальные значения x
j
и соответствующее
значение целевой функции. Является ли оптимальное решение единственным?
б) определите, в каких пределах могут меняться коэффициенты при
небазисных переменных в выражении для целевой функции, не нарушая
оптимальности базиса, полученного в результате выполнения пункте а);
в) рассмотрите упражнение п. б) для случая, когда варьируются
коэффициенты при базисных переменных;
г) пусть коэффициенты при x
2
и x
3
в выражении для целевой функции
равняются соответственно –1 + δ
2
и 3 + δ
3
. Определите систему неравенств для
δ
2
и δ
3
, при выполнении которых базис, полученный в п. а), продолжает
оставаться оптимальным. Изобразите графически область изменения δ
2
и δ
3
,
определяемую упомянутыми выше неравенствами;
д) покажите, в каких интервалах могут меняться константы в правых частях
141
соотношений (1), не нарушая оптимальности базиса, полученного в результате
выполнения упражнения пункте а);
е) пусть в правых частях первых двух соотношений (1) имеем
соответственно 7 + δ
1
и 12 + δ
2
. Найдите неравенства для δ
1
и δ
2
, при
выполнении которых базис, полученный в п. а), продолжает оставаться
допустимым. Изобразите графически область изменения δ
1
и δ
2
, определяемую
этими неравенствами;
ж) сформулируйте для (1) двойственную задачу. Найдите оптимальные
значения переменных двойственной задачи и соответствующее значение
целевой функции для двойственной модели;
з) дайте экономическую интерпретацию переменных двойственной задачи и
поясните ее на численных примерах;
и) исходя из ограничений, полученных для двойственной модели,
определите, в каких интервалах могут меняться коэффициенты при
небазисных переменных в выражении для целевой функции исходной задачи,
не нарушая оптимальности решения, полученного в пункте а);
к) пусть вводятся новые управляемые переменные x
8
и x
9
. Допустим, что
коэффициенты при x
8
в соотношениях (1) равны соответственно 5, –3 и 1, а
коэффициент при x
8
в выражении для целевой функции равен 2. Пусть
коэффициенты при x
9
в соотношениях (1) равны соответственно –2, 10 и 12, а
коэффициент при x
9
в выражении для целевой функции равен –4. Можно ли
при этом улучшить решение, полученное в п. а)? Если можно, то покажите,
каким образом это достигается. Если нельзя, покажите, что произойдет при
включении в базис переменной x
9
;
л) вычислите коэффициенты при x
8
и x
9
в уравнениях (2);
м) пусть коэффициент при x
1
в первом соотношении (1) равен 1 + δ.
Определите, в каких пределах можно изменять δ, не нарушая оптимальности
решения, полученного в пункте а);
142
н) пусть коэффициент при x
1
во втором соотношении (1) равен –1 + δ.
Определите, в каких пределах можно изменять δ, не нарушая оптимальности
решения, полученного в пункте а);
о) рассмотрите упражнения п. м) и н) для случая, когда варьируется
коэффициент при x
4
.
9. Рассмотрите следующую задачу:
максимизировать –10x
1
+ 24x
2
+ 20x
3
+ 20x
4
+ 25x
5
(1)
при наличии ограничений
–1x
1
+ 1x
2
+ 2x
3
+ 3x
4
+ 5x
5
≤ 19,
–1x
1
+ 4x
2
+ 3x
3
+ 2x
4
+ 1x
5
≤ 57, (2)
x
j
≥0 (j =1, 2, 3, 4, 5):
а) сформулируйте двойственную задачу и покажите, что одним из
допустимых ее решений является следующее:
у
1
=4, у
2
= 5;
б) воспользуйтесь результатами, полученными в пункте а), и найдите
оптимальное решение как исходной, так и двойственной задачи;
в) Введите в п. б) дополнительное ограничение x
1
+ x
2
+ x
3
+x
4
+x
5
≤20.
Найдите оптимальные решения исходной и двойственной задач.
10. Рассмотрите следующую задачу:
максимизировать –1x
1
+ 7x
2
– 5x
3
+ 14x
4
,
если
3x
1
+ 4x
2
+ 5x
3
+ 6x
4
≤ 24,
–1x
1
+ 1x
2
– 2x
3
+ 2x
4
≤ 4,
x
j
≥0 (j=1, 2, 3, 4):
а) сформулируйте двойственную задачу и покажите, что одним из ее
допустимых решений является следующее:
у
1
=1, у
2
= 4;
143
б) найдите оптимальное решение как исходной, так и двойственной задачи,
используя результаты, полученные в пункте а);
в) введите в пункте б) дополнительное ограничение x
1
+ x
2
+ x
3
+ x
4
+ x
5
≤ 8 и
найдите оптимальные решения исходной и двойственной задач.
11. В каждом из приведенных ниже упражнений а) – в) используйте
двойственный симплекс-алгоритм для нахождения оптимального решения
соответствующей двойственной задачи. Рассмотрите задачи,
сформулированные в упражнениях:
а) 18 темы 3;
б) 19 а) темы 3;
в) 19 б) темы 3.
В каждом случае требуется показать, каким образом находится оптимальное
решение исходной задачи, если известна система уравнений для двойственной
задачи на последней итерации.
В каждом случае проведите сравнение пробных решений двойственной
задачи, получаемых с помощью двойственного симплекс-алгоритма, с
соответствующими пробными решениями исходной задачи, получаемыми
обычным симплексным методом (тема 3).
12. а) с помощью двойственного симплекс-алгоритма найдите решение
задачи, представленной соотношениями (5.3.1) и (5.3.2) разд. 5.3;
б) рассмотрим систему уравнений (I), приведенную в начале разд. 4.1.
Введем в базис переменную x
4
, исключив из него x
5
. Требуется доказать, что
получающиеся при этом пробные значения переменных двойственной задачи
являются допустимыми. Являются ли допустимыми базисные переменные
исходной задачи? В случае положительного ответа покажите, как выглядят
оптимальные решения исходной и двойственной задач. Если ответ окажется
отрицательным, найдите оптимальные решения исходной и двойственной
задач, воспользовавшись двойственным симплекс-алгоритмом.
13. Рассмотрите задачу, сформулированную в упражнении 10. Требуется
144