Гельруд Я.Д. Линейное программирование. Учебно-методический комплекс
Подождите немного. Документ загружается.
129
входят несколько задач, содержащих в своих частичных циклах одни и те же
т городов, например город 1 – город 2 – город 3 и город 1 – город 3 – город 2.
В этом случае вычисления оценок на шаге 2 повторяются.)
Применение этого алгоритма к примеру табл. 6.1 также проведите
самостоятельно.
П
П
П
Р
Р
Р
А
А
А
К
К
К
Т
Т
Т
И
И
И
К
К
К
У
У
У
М
М
М
Тема 3
1. а) решите приведенную в разд. 3.1 систему уравнений (3.1.2) и (3.1.3)
относительно x
1
и x
3
. Результат проверьте с помощью (3.1.14) и (3.1.15);
б) подставьте в формулу для целевой функции полученные в п. а)
выражения для x
1
и x
3
. Результат сравните с выражением (3.1.15),
приведенным в разд. 3.1.
В упражнениях 2–4 за основу берется модель, рассмотренная в разд. 3.2, с
несколько измененными данными.
2. Какую из переменных следует включить в базис на первой симплекс-
итерации, если подлежащая максимизации целевая функция имеет вид
а) 14x
1
+ 5x
2
+ 9x
3
+ 11x
4
? в) 4x
1
+ 5x
2
– 9x
3
+ 11x
4
?
б) 4x
1
+ 5x
2
+ 9x
3
+ 8x
4
? r) –4x
1
– 5x
2
– 9x
3
– 11x
4
?
3. Пусть на первой итерации в базис вошла переменная x
4
. Какая переменная
подлежит при этом исключению из базиса, и каким будет новое значение x
4
,
если:
а) в правой части уравнения, соответствующего строке 2, стоит число 20?
12?
б) в правой части уравнения, соответствующего строке 3, стоит число 300?
75?
в) коэффициент при x
4
в строке 3 равен 20? 24? –15?
г) коэффициент при x
4
в строке 2 равен 24?
д) в правых частях уравнений в строках 1, 2 и 3 стоят соответственно числа
40, 60 и 20, а коэффициенты при x
4
в указанных строках равны соответственно
–5, 10 и 2?
4. Пусть на первой итерации в базис вошла переменная x
4
. Какими будут
новые значения базисных переменных, если:
126
а) вместо x
7
из базиса исключить x
5
?
б) вместо x
7
из базиса исключить x
6
?
Являются ли значения, полученные в п. а) и б), допустимыми? Дайте
соответствующие пояснения.
В упражнениях 5–14 за основу берется модель, рассмотренная в разд. 3.2.
Данная модель варьируется путем изменения различных количественных
характеристик. В каждом случае требуется найти оптимальное решение и
соответствующее значение целевой функции. Каждую задачу, прежде всего,
нужно тщательно продумать, поскольку может оказаться, что для получения
решения вовсе не обязательно воспроизводить весь вычислительный процесс,
изложенный в разд. 3.2.
5. Найдите оптимальное решение, если подлежащая максимизации целевая
функция имеет вид
а) 4x
1
+
7
33
x
2
+ 9x
3
+ 10x
4
;
б) 5x
1
+ 5x
2
+ 9x
3
+ 11x
4
;
в) 5x
1
+
7
33
x
2
+ 9x
3
+ 10x
4
.
6. Найдите оптимальное решение, если:
а) в правой части уравнения в строке 2 стоит число 140;
б) в правой части уравнения в строке 2 стоит число 60;
в) в правой части уравнения в строке 1 стоит число 12;
г) в правой части уравнения в строке 1 стоит число 10;
д) в правой части уравнения в строке 1 стоит число 20.
7. Найдите оптимальное решение, предположив, что подлежащая
максимизации целевая функция имеет вид 5x
1
+ 5x
2
+ 9x
3
+ 11x
4
, а в правой
части уравнения в строке 1 стоит число 20.
8. Найдите оптимальное решение, если первое ограничение (до введения в
рассмотрение свободной переменной) имеет вид 2x
1
+ 2x
2
+ 2x
3
+ 2x
4
≤ 30.
127
9. Найдите оптимальное решение, если:
а) коэффициент при x
2
в строке 3 равен 10;
б) коэффициент при x
4
в строке 3 равен 20;
в) коэффициент при x
2
в строке 2 равен 4;
г) коэффициент при x
4
в строке 2 равен 1;
д) коэффициент при x
1
в строке 2 равен 10;
е) коэффициент при x
3
в строке 2 равен 6.
10. Найдите оптимальное решение, если в строках 0, 1, 2 и 3:
а) коэффициенты при x
1
равны соответственно 40, 10, 70 и 30;
б) коэффициенты при x
2
равны соответственно 20, 4, 20 и 20;
в) коэффициенты при x
3
равны соответственно 90, 10, 30 и 100.
11. Решите задачу в предположении, что имеет место дополнительное
требование x
4
= 4.
12. а) Рассмотрим переменную x
8
, заданную соотношением (3.2.10) в разд.
3.2. Вычислите коэффициенты при x
8
на каждой из симплекс-итераций [см.
(3.2.2) – (3.2.7) в разд. 3.2].
б) Проверьте справедливость соотношения (3.2.12) из разд. 3.2, если
переменная x
8
на четвертой итерации включена в базис.
в) Пусть в соотношении (3.2.13) w = 0,5. Требуется найти оптимальные
значения для x
1
, x
3
, x
6
и x
8
, а также убедиться, что эти значения удовлетворяют
исходным ограничениям и дают для значения целевой функции число, равное
695
/
7
.
13. Рассмотрим переменную x
8
, заданную соотношением (3.2.10) в разд. 3.2.
Требуется выяснить, будет ли решение улучшено в результате включения на
четвертой итерации переменной x
8
в базис, если;
а) коэффициент при x
8
в строке 2 положить равным 8 вместо 9;
б) коэффициент при x
8
в строке 2 положить равным 10 вместо 9;
в) коэффициент при x
8
в строке 3 положить равным 1 вместо 0,2;
г) коэффициент при x
8
в строке 3 положить равным 0,1 вместо 0,2.
128
14. Предположим, что модель, рассмотренная в разд. 3.2, «расширена» за
счет новой переменной z. Пусть на четвертой итерации коэффициенты при z в
каждом из уравнений системы (3.2.7) равны –1. Каким будет оптимальное
решение? Требуется показать, что имеет место решение, для которого целевая
функция принимает значение, равное 100.
15. Рассмотрите модель, представленную соотношениями (3.3.7) – (3.3.10)
в разд. 3.3. В каждом из приведенных ниже пунктов требуется применить
метод больших штрафов с М = 10 и найти исходную систему уравнений,
аналогичную (3.3.13). Рассмотрите следующие варианты:
а) ограничение для x
2
имеет вид x
2
≥ 2;
б) вместо (3.3.8) имеет место ограничение 5x
1
+ 6x
2
= 56;
в) вместо (3.3.8) имеет место ограничение –5x
1
+ 6x
2
= 16.
16. Пусть для принятой системы ограничений пробный базис, построенный
только из свободных переменных, определяет некоторое допустимое решение.
Какая переменная вводится в базис на первой симплекс-итерации, если
подлежащая минимизации целевая функция имеет вид:
а) 4x
1
+ 5x
2
– 9x
3
+ 11x
4
?
б) –4x
1
+ 5x
2
– 9x
3
+ 11x
4
?
в) –4x
1
– 5x
2
– 9x
3
– 11x
4
?
г) 4x
1
+ 5x
2
+ 9x
3
+ 11x
4
?
д) Пусть ответ на поставленный вопрос для каждого из этих четырех
пунктов получен. Требуется определить, какая свободная переменная в
каждом из указанных случаев выпадает из базиса при условии, что входящие в
модель ограничения задаются строками 1, 2 и 3 системы уравнений (3.2.1),
приведенной в разд. 3.2.
17. С помощью симплексного метода
максимизировать 5x
1
+ 6x
2
при ограничениях
0.2x
1
+ 0.3x
2
≤ l.8,
129
0.2x
1
+ 0.1x
2
≤ 12,
0.3x
1
+ 0.3x
2
≤ 2.4,
x
1
≥0, x
2
≥0.
18. С помощью симплексного метода решите следующую задачу:
максимизировать 15x
1
+ 6x
2
+ 9x
3
+ 2x
4
при ограничениях
2x
1
+ x
2
+ 5x
3
+ 0.6x
4
≤ 10,
3x
1
+ x
2
+ 3x
3
+ 0.25x
4
≤ 12,
7x
1
+ x
4
≤ 35,
x
j
≥0 (j=1, 2, 3, 4).
(Условие: для нахождения оптимального решения должно быть выполнено не
более трех итераций.)
19. а) Используя симплексный метод,
максимизировать 30x
1
+ 23x
2
+ 29x
3
при ограничениях
6x
1
+ 5x
2
+ 3x
3
≤ 26,
4x
1
+ 2x
2
+ 5x
3
≤ 7,
x
j
≥0 (j=1, 2, 3).
(Условие: для нахождения оптимального решения должно быть выполнено не
более трех итераций.)
б) Решите задачу, сформулированную в п. а), заменив число 26 в правой
части первого неравенства на 31, а число 7 в правой части второго неравенства
на 20. (Условие: оптимальное решение должно быть получено с
использованием не более трех итераций.)
20. С помощью симплексного метода
максимизировать 60x
1
+ 26x
2
+ 15x
3
+ 4.75x
4
при ограничениях
20x
1
+ 9x
2
+ 6x
3
+ 1x
4
≤ 20,
130
10x
1
+ 4x
2
+ 2x
3
+ 1x
4
≤ 10,
x
j
≥0 (j = 1, 2, 3, 4).
(Условие: число итераций, приводящее к оптимальному решению, должно
быть не больше пяти.) При всех ли итерациях значение целевой функции
возрастает? Является ли оптимальное решение единственным?
21. Альтернативные оптимальные решения:
а) решите симплексным методом следующую задачу:
максимизировать x
1
+ x
2
при ограничениях
x
1
+ x
2
≤ 3,
x
1
≤ 2,
x
2
≤ 2,
x
1
≥0, x
2
≥0;
б) положите коэффициенты при x
1
равными 10 вместо 1 как в ограничениях,
так и в выражении для целевой функции. Найдите решение для
видоизмененной таким образом модели с помощью симплексного метода;
в) положите коэффициенты при x
2
равными 10 вместо 1 как в ограничениях,
так и в выражении для целевой функции. Найдите решение для
видоизмененной таким образом модели с помощью симплексного метода;
г) объясните, исходя из каких соображений в пунктах а) – в) можно сделать
вывод о существовании альтернативных оптимальных решений. Используя
формулы, аналогичные (3.2.13) из разд. 3.2, приведите выражения для всех
оптимальных решений.
22. Неограниченное оптимальное решение. Пусть заданы ограничения
x
1
– x
2
≤ 3,
–x
1
+ x
2
≤ 2,
x
1
≥0, x
2
≥0.
Используйте симплексный метод для решения следующих задач:
131
а) максимизировать x
1
;
б) максимизировать x
2
;
в) максимизировать x
1
+ x
2
;
г) для каждого из пунктов а) – в) укажите допустимое решение, при котором
значение целевой функции равняется 100.
23. Рассмотрите ограничения:
–10x
1
– 15x
2
≥ –150,
5x
1
+ 10x
2
≥ 50,
x
1
– x
2
≥ 0,
x
1
≥0, x
2
≥0.
Требуется определить исходный базис, используя метод больших штрафов
при М = 10, а также найти симплексным методом оптимальное решение
следующих задач:
а) максимизировать x
1
+ x
2
; г) максимизировать –2x
1
+ x
2
;
б) минимизировать x
1
+ x
2
; д) максимизировать –x
1
– 3x
2
;
в) максимизировать x
1
+ 3x
2
; е) максимизировать –x
1
– 2x
2
.
Установите, в каких случаях оптимальное решение единственно, и найдите
альтернативные оптимальные решения, когда единственность не имеет места.
(Замечание: в первое ограничение искусственную переменную вводить не
следует.)
24. Рассмотрите ограничения:
–x
1
+ x
2
≤ 1,
6x
1
+ 4x
2
≥ 24,
x
1
≥0, x
2
≥0.
Требуется найти исходный базис, используя метод больших штрафов при
М= 10, а также получить симплексным методом оптимальное решение
следующих задач:
а) минимизировать x
1
; г) максимизировать –x
1
+ 2x
2
;
132
б) минимизировать x
1
+ x
2
; д) максимизировать x
1
– 2x
2
;
в) максимизировать x
1
+ x
2
; е) максимизировать –3x
1
– 2x
2
.
Установите, в каких случаях оптимальное решение единственно, и найдите
альтернативные оптимальные решения, когда единственность не имеет места.
25. Решите задачу 24, положив x
1
≤5.
26. Решите задачу 24, положив x
2
≤4.
27. Рассмотрим простую задачу, не имеющую допустимых решений:
максимизировать x
1
+ x
2
при наличии ограничений
–x
1
+ x
2
≤ –1,
x
1
– x
2
≤ –1,
x
1
≥0, x
2
≥0.
Используйте для решения данной задачи метод больших штрафов и покажите,
к чему это приводит. Убедитесь, что условие (3.3.4), сформулированное в
разд. 3.3, не может быть удовлетворено ни при каких значениях М.
29. Решите задачу:
максимизировать x
1
– x
3
при ограничениях
5x
1
+ 3x
2
+ x
3
= 40,
x
1
+ x
2
+ 4x
3
= 10,
x
j
≥0 (j = 1, 2, 3).
Используя метод больших штрафов, найдите оптимальное решение при
условии, что приведенная выше модель дополнена ограничением вида
а) 6x
1
+ 4x
2
+ 5x
3
= 50;
б) 6x
1
+ 4x
2
+ x
3
= 50.
Тема 4
В упражнениях 1–7 за основу берется модель, рассмотренная в разд. 3.2.
Исходная система уравнений (I) и система уравнений на этапе
133
заключительной итерации (F) приведены в начале разд. 4.1. Тщательный
анализ сформулированных ниже задач во многих случаях позволит найти
требуемое решение, минуя целый ряд вычислений, предусмотренных
симплексным алгоритмом.
1. а) пусть коэффициент при х
2
в первоначальном выражении для целевой
функции равен 4
6
/
7
(вместо 5). Требуется вычислить коэффициент при х
2
в
строке 0 на каждой симплекс-итерации, а также показать, что после
выполнения заключительной итерации коэффициент при х
2
в строке 0
принимает значение
2
/
7
(
3
/
7
–
l
/
7
);
б) рассмотрите упражнение пункта а), положив коэффициент при х
2
в
первоначальном выражении для целевой функции равным 5
1
/
7
(вместо 5);
в) пусть коэффициент при х
4
в первоначальном выражении для целевой
функции равен 10 (вместо 11). Требуется вычислить коэффициент при х
4
в
строке 0 на каждой симплекс-итерации и, в частности, показать, что после
выполнения заключительной итерации этот коэффициент равен
4
/
7
(
11
/
7
– 1);
г) рассмотрите упражнение пункта в), положив коэффициент при х
4
в
первоначальном выражении для целевой функции равным 12(вместо 11);
д) пусть коэффициент при х
3
в первоначальном выражении для целевой
функции равен 9 + δ. В каком интервале значений δ базисное решение,
соответствующее (F), остается оптимальным? Какую переменную следует
включить в базис в том случае, когда значение δ лежит вне найденного
интервала (слева от предельного значения; справа от предельного значения)?
е) пусть коэффициент при свободной переменной х
6
в первоначальном
выражении для целевой функции равен δ. Ответьте на вопросы, поставленные
в пункте д).
2. Остается ли базисное решение, соответствующее (F), оптимальным, если
подлежащая максимизации целевая функция (в ее первоначальной записи)
имеет вид
а) 6x
1
+ 5x
2
+ 9x
3
+ 12x
4
?
134