Файл: Н.Ю. Коломарова Решение задач линейного целочисленного программирования методом гомори.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 01.06.2024
Просмотров: 46
Скачиваний: 0
|
|
|
|
|
12 |
|
|
|
|
11. max L = 2x1 + 7x2 |
|
|
12. max L = 8x1 + 11x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
3х1 + 8х2 ≤ |
23 |
|
|
11х1 + 2х2 ≤ |
25 |
|
|
|
|
3х1 + 11х2 ≤ |
31 |
|
|
3х1 + 8х2 ≤ |
12 |
|
|
|
|
13. max L = 4x1 + 3x2 |
|
|
14. min L = 5x1 - 3x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
-6х1 + 5х2 ≤ |
14 |
|
|
-6х1 + 8х2 ≤ |
11 |
|
|
|
|
3х1 + х2 ≤ |
17 |
|
|
-7х1 + х2 ≤ |
5 |
|
|
|
|
-7х1 + 3х2 ≥ |
-44 |
|
|
7х1 - 3х2 ≤ |
13 |
|
|
|
|
15. max L = 5x1 - 3x2 |
|
|
16. min L = 2x1 - 9x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
-6х1 + 8х2 ≤ |
11 |
|
|
-3х1 + 7х2 ≤ |
10 |
|
|
|
|
-7х1 + х2 ≤ |
5 |
|
|
3х1 + х2 ≤ |
5 |
|
|
|
|
7х1 - 3х2 ≤ |
13 |
|
|
5х1 - 7х2 ≤ |
13 |
|
|
|
|
17. max L = 2x1 + 4x2 - 4x3 |
18. min L = -3x1 + 2x2 + 5x3 |
|
|||||||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
2х1 + 7х2 + 5x3 ≤ |
9 |
|
9х1 - 4х2 + x3 ≤ |
16 |
|
||||
7х1 + х2 + 3x3 ≤ |
11 |
-5х1 + х2 + 3x3 ≤ |
9 |
|
|
||||
19. max L = x1 - 3x2 - x3 + 2x4 |
20. max L = 2x1 - x2 + 6x4 |
|
|
||||||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
2х1 |
+ x3 - 3x4 ≥ |
12 |
3х1 + 2x2 + |
|
3x4 ≤ |
16 |
|||
3х1 - х2 + |
x4 ≤ |
20 |
-2х2 + 4х3 + 7x4 ≤ |
18 |
|||||
21. max L = x1 + 10x2 |
|
|
22. min L = -7x1 - x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
3х1 + 4х2 ≤ |
23 |
|
|
5х1 + 2х2 ≤ |
24 |
|
|
|
|
-х1 + 2х2 = 4 |
|
|
12х1 - 7х2 ≤ |
15 |
|
|
|
||
2х1 + 3х2 ≤ |
14 |
|
|
6х1 + 8х2 ≤ |
9 |
|
|
|
|
23. max L = 3x1 + 2x2 + 2x3 |
24. max L = -4x1 + x2 |
|
|
|
|||||
при ограничениях |
|
|
при ограничениях |
|
|
|
|||
|
4х2 + 3x3 ≤ |
7 |
|
-7х1 + 13х2 + 3x3 ≤ |
7 |
|
|||
6х1 + 5х2 + x3 = 12 |
х1 - 6х2 + 7x3 ≤ |
-9 |
|
||||||
|
|
|
|
|
13 |
|
|
|
|
|
25. max L = -10x1 - 14x2 - 21x3 |
|
26. max L = 4x1 + 3x2 + 8x3 |
|
|
||||||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
2х1 + 2х2 + 7x3 ≥ |
14 |
|
21х1 - 17х2 + 19x3 ≤ |
77 |
|
|||||
8х1 + 11х2 + 9x3 ≥ |
12 |
|
6х1 + 4х2 + 3x3 ≤ |
29 |
|
|||||
9х1 + 6х2 + 3x3 ≥ |
10 |
|
10х1 |
+ 11x3 ≤ |
65 |
|
||||
27. max L = 2x1 + 3x2 + 4x3 |
|
28. max L = x1 - 5x2 + x3 |
|
|
|
|||||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
х1 + 5х2 + 13x3 = 37 |
|
4х1 + х2 - 6x3 ≤ |
41 |
|
|
|||||
-9х1 + 7х2 + 4x3 ≤ |
20 |
|
-2х1 |
- x3 ≤ |
2 |
|
|
|||
-х1 + 8х2 |
|
≥ |
8 |
|
3х1 + 2х2 + 7x3 = 34 |
|
|
|||
29. max L = 5x1 + 8x2 |
|
|
|
30. max L = x1 + 8x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
-8х1 + 12x2 ≤ |
40 |
|
|
4х1 - 3х2 ≤ |
12 |
|
|
|
||
13х1 - 9х2 ≤ |
37 |
|
|
-5х1 + 7х2 ≤ |
34 |
|
|
|
||
31. min L = 19x1 + 21x2 |
|
|
32. max L = 2x1 + 5x2 |
|
|
|
||||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
2х1 + 5x2 ≥ |
20 |
|
|
х1 + х2 ≤ |
6 |
|
|
|
||
4х1 + х2 ≥ |
20 |
|
|
4х1 + 11х2 ≤ |
44 |
|
|
|
||
33. min L = 10x1 - 111x2 |
|
|
34. max L = 8x1 + 19x2 + 7x3 |
|
||||||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
-х1 + 10x2 ≤ |
40 |
|
|
х1 + 3х2 + 3x3 ≤ |
50 |
|
|
|||
х1 + х2 ≤ |
20 |
|
|
3х1 + 4х2 + x3 ≤ |
25 |
|
|
|||
35. min L = -4x1 - 5x2 - 9x3 - 11x4 |
36. max L = 3x1 + 2x2 + 8x3 + 7x4 |
|||||||||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
х1 + х2 + x3 + x4 ≤ |
15 |
2х1 + х2 + 5x3 + 8x4 ≤ |
10 |
|||||||
7х1 + 5х2 + |
3x3 + 2x4 ≤ |
120 |
9х1 + 3х2 + 4x3 + |
2x4 ≤ |
21 |
|||||
3х1 + 5x2 + 10x3 + 15x4 ≤ |
100 |
3х1 + 8x2 + 4x3 + 11x4 ≤ |
46 |
|||||||
37. max L = 2x1 + 3x2 |
|
|
|
38. max L = -2x1 + 3x2 |
|
|
|
|||
при ограничениях |
|
|
при ограничениях |
|
|
|
||||
х1 + 19х2 ≤ |
30 |
|
|
4х1 + х2 ≤ |
8 |
|
|
|
||
2х1 + х2 ≤ |
20 |
|
|
-5х1 + 6х2 ≤ |
7 |
|
|
|
||
|
|
14 |
|
39. min L = 6x1 - 2x2 |
40. min L = 3x1 + 4x2 |
|
|
при ограничениях |
при ограничениях |
||
2х1 - 6х2 ≤ |
-39 |
2х1 + 19х2 ≥ |
24 |
7х1 + 3х2 ≥ |
24 |
13х1 + 12х2 ≥ |
50 |
-2х1 + 5x2 ≤ |
33 |
х1 - 5x2 ≤ |
1 |
41. min L = 6x1 + x2 |
42. max L = x1 + 32x2 |
||
при ограничениях |
при ограничениях |
||
3х1 - х2 = 9 |
2х1 - 3х2 ≥ |
10 |
|
-х1 + 4х2 ≥ |
18 |
5х1 - 9х2 ≤ |
16 |
2х1 + 3x2 ≤ |
31 |
-х1 + 6x2 ≤ |
42 |
43.max L = 4,4x1 + 2,7x2 + 3,2x3 + 2,8x4 + 3,5x5 + 3,9x6
при ограничениях
80х1 + 62х2 + 92x3 + 82x4 + 65x5 + 90x6 ≤ 800 95х1 + 90х2 + 96x3 + 110x4 + 120x5 + 80x6 ≤ 600
44.max L = 5x1 + 2x2 - 3x3 + 2x4 + 3x5 - 3x6
при ограничениях
5х1 + 6х2 + 4x3 + 2x4 - 3x5 + 5x6 = 11
5х1 + 5х2 + 7x3 + |
3x5 + 5x6 = 10 |
|
2х1 + 2х2 + 2x3 + |
3x5 |
= 4 |
45.max L = 4x1 + 7x2 - x3 + 2x4
при ограничениях
х1 + х2 + x3 + x4 = 15
4х1 - х2 + 8x3 |
≤ |
14 |
3х2 + 4x3 |
≤ |
9 |
4.КОНТРОЛЬНЫЕ ВОПРОСЫ
1.Может ли задача линейного целочисленного программирования иметь несколько решений?
2.Может ли ограничение Гомори быть записано следующим обра-
зом: 1/5x5 - 7/8x6 ≥ 1/3?
15
3.Среди ограничений задачи линейного целочисленного програм-
мирования есть такие: x1 + x2 + x3 ≥ 10 и x1 + x2 + x3 ≤ 20. Дайте экономическую интерпретацию данных ограничений.
4.На основании чего мы можем говорить, что задача с ограничениями Гомори не имеет ни одного плана?
5.В каких случаях задача линейного целочисленного программирования неразрешима?
6.В задаче линейного целочисленного программирования переменные принимают лишь 2 значения: 0 или 1. Какой экономический смысл данного решения? Приведите примеры.
7.Отвечает ли требованиям, предъявляемым к ограничениям Го-
мори, дополнительное ограничение в виде |
∑ |
x j ≥ 1? |
|
j базису |
|
8. Каков максимальный размер симплексных таблиц при использовании метода Гомори?
СПИСОК ЛИТЕРАТУРЫ
1.Тынкевич М.А., Ветрова Г.С., Бияков О.А. Экономикоматематические методы (исследование операций). –Кемерово : КузГТУ, 1997. –176 с.
2.Акулич И.Л. Математическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец. вузов. – М.: Высш.
шк., 1986.- 319 с.
Составитель Наталья Юрьевна Коломарова
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ГОМОРИ
Методические указания и задания к практическим занятиям по курсу
«Экономико-математические методы» для студентов экономических специальностей
Редактор З.М.Савина
ЛР № 020313 от 23.12.96
Подписано в печать 29.12.99. Формат 60х84/16.
Бумага офсетная. Отпечатано на ризографе. Уч.-изд.л. 1,0. Тираж 200 экз. Заказ .
Кузбасский государственный технический университет. 650026, Кемерово, ул. Весенняя, 28.
Типография Кузбасского государственного технического университета. 650099, Кемерово, ул. Д.Бедного, 4А.