Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
Теоретическая часть:
Когда формулируется задача целочисленного линейного программирования?
Почему решение задачи целочисленного линейного программирования нельзя получить из решения задачи линейного программирования округлением до целого?
Что такое целая часть числа?
Что такое дробная часть числа?
Как формулируется условие отсечения нецелочисленного решения?
Каков порядок решения задачи целочисленного линейного программирования методом Гомори?
Практическая часть:
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Практическая работа №14
Динамическое программирование.
Теоретическая часть:
Что лежит в основе метода ДП?
Что такое рекуррентное соотношение?
Как формулируется задача оптимального распределения инвестиций?
Запишите функциональные уравнения Беллмана, используемые на каждом шаге управления в задаче оптимального распределения инвестиций.
Практическая часть:
1. Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения gi(xi) (i = 1…4) дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в таблице. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.
Выделенные средства хi, млн. ден ед. |
Предприятие |
|||
№ 1 |
№ 2 |
№ 3 |
№ 4 |
|
Получаемый доход, млн. ден. ед. |
||||
g1(xi) |
g2(xi) |
g3(xi) |
g4(xi) |
|
20 |
9 |
11 |
16 |
13 |
40 |
18 |
19 |
32 |
27 |
60 |
24 |
30 |
40 |
44 |
2. Имеются 4 предприятия, между которыми распределяется 100 тыс. ден. ед. Значения прироста выпуска продукции на предприятиях в зависимости от выделенной суммы приведены в таблице. Составить план распределения средств, максимизирующий общий прирост выпуска продукции.
2.1
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
9 |
11 |
16 |
13 |
40 |
18 |
19 |
32 |
27 |
60 |
24 |
30 |
40 |
44 |
80 |
38 |
44 |
57 |
69 |
100 |
50 |
59 |
70 |
73 |
2.2
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
7 |
9 |
17 |
16 |
40 |
29 |
19 |
27 |
30 |
60 |
37 |
28 |
37 |
42 |
80 |
41 |
37 |
48 |
65 |
100 |
59 |
46 |
66 |
81 |
2.3
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
11 |
13 |
10 |
10 |
40 |
21 |
20 |
22 |
27 |
60 |
40 |
42 |
34 |
33 |
80 |
54 |
45 |
55 |
57 |
100 |
62 |
61 |
60 |
69 |
2.4
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
12 |
16 |
9 |
15 |
40 |
26 |
21 |
17 |
25 |
60 |
40 |
36 |
35 |
51 |
80 |
60 |
49 |
51 |
62 |
100 |
72 |
63 |
65 |
76 |
2.5
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
9 |
8 |
12 |
7 |
40 |
18 |
19 |
25 |
15 |
60 |
29 |
30 |
51 |
52 |
80 |
41 |
47 |
58 |
59 |
100 |
60 |
58 |
69 |
60 |
2.6
Средства хi,тыс.ден.ед. |
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Прирост,тыс.ден.ед. |
||||
q1(x) |
q2(x) |
q3(x) |
q4(x) |
|
20 |
14 |
12 |
13 |
33 |
40 |
24 |
30 |
25 |
33 |
60 |
37 |
42 |
45 |
46 |
80 |
45 |
58 |
62 |
60 |
100 |
58 |
71 |
70 |
68 |