comp2009
.pdf
1. Практикум по курсу пользователя персонального компьютера "
Математическая постановка задачи
Найти минимум или максимум целевой функции
|
n |
|
f = c0 + ∑ cj xj |
|
j =1 |
при ограничениях |
|
n |
|
∑ aij xj |
bi , i = 1,...,m, xj ≥ 0, j = 1,...,n, |
j 1 |
|
где с0, сj, aij, bi — действительные числа;— любой из знаков =, ≠, ≤, ≥.
Для рассмотренного примера математическая формулировка задачи может выглядеть следующим образом:
минимизировать функцию Р = –2Х1 – 4Х2 при ограничениях 3Х1 + 4Х2 ≤ 1700, 2Х1 + 5Х2 ≤ 1600, Х1, Х2 ≥ 0.
Методика выполнения заданий
В MS Excel постановка задачи примера (рис. 1.50) формулируется следующим образом:
Рис. 1.50
61
"Компьютерный практикум по информатике и программированию
•установить целевую ячейку G16, равной максимальному значению, изменяя ячейки В15:E15;
•ограничения: В15:E15 >= 0; L7<=F7; L8<=F8.
Задание.
Планируются мероприятия по продлению сроков гарантии и снятию установок с эксплуатации. Первоначальное число этих установок составляет a1, a2, …, an, где i = 1, 2, …, n — порядковые номера территориальных подразделений.
Требуется, чтобы общее число установок, гарантийные сроки эксплуатации которых должны быть увеличены, было не менее заданного числа b1. Известны затраты на продление гарантийного срока установки каждого из территориальных подразделений. Они не одинаковы в связи
ссущественным различием местных условий, удалённостью районов и рядом других причин и равны c1, c2, …, cn. Ожидаемые затраты на снятие
сэксплуатации установки каждого территориального подразделения
составляют d1, d2, …, dn. Затраты на продление гарантии и снятие с эксплуатации не должны превышать соответственно величин b2 и b3. Каждая установка должна оказаться либо в числе тех, срок службы которых продлён, либо в числе снятых с эксплуатации.
Обозначим x1, x2, …, xn — число установок, сроки гарантии которых будут увеличены. Тогда принятие решения в рассматриваемой ситуации должно быть сопряжено с выполнением следующих ограничений:
x1 + x2 +…+ xn ≥ b1, c1x1 + c2x2 +…+ cnxn ≤ b2,
или
d1(a1 – x1) + d2(a2 – x2) +…+ dn(an – xn) ≤ b3, x1 ≤ a1; x2 ≤ a2; x3 ≤ a3
n |
|
n |
|
∑ xi |
≥ b1 ; |
∑ ci xi |
≤ b2 ; |
i=1 |
|
i=1 |
|
n |
|
n |
|
∑ di xi ≥ b3' |
= ∑ di ai − b3 ; |
||
i=1 |
|
i=1 |
|
xi ≥ 0, xi ≤ ai , i = 1,2,...,n.
Обозначим P1, P2, …, Pn — ожидаемый эффект (прибыль) от продолжения эксплуатации каждой из n видов установок. Тогда целевая функция примет вид:
62
1. Практикум по курсу пользователя персонального компьютера "
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
f = p1x1 + p2 x2 + ... + pn xn |
= ∑ pi xi . |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
Варианты заданий |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№ |
a1 |
a2 |
a3 |
b1 |
c1 |
c2 |
c3 |
b2 |
d1 |
d2 |
d3 |
b3 |
p1 |
p2 |
p3 |
1 |
3 |
4 |
2 |
2 |
4 |
2 |
1 |
12 |
3 |
0 |
1 |
9 |
–0,1 |
0,1 |
0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
10 |
9 |
4 |
12 |
3 |
2 |
1 |
20 |
1 |
5 |
1 |
15 |
–0,2 |
0,1 |
–0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
8 |
3 |
0 |
5 |
2 |
1 |
0 |
9 |
1 |
2 |
0 |
10 |
0,2 |
0,3 |
0 |
4 |
11 |
9 |
7 |
18 |
1 |
1 |
2 |
30 |
1 |
3 |
3 |
20 |
0,1 |
0,7 |
0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
9 |
8 |
0 |
7 |
1 |
1 |
0 |
30 |
1 |
4 |
0 |
24 |
0,3 |
0,4 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
7 |
20 |
3 |
12 |
3 |
2 |
1 |
30 |
1 |
5,1 |
1 |
45 |
0,2 |
0,1 |
-0,3 |
7 |
3 |
7 |
0 |
6 |
3 |
1 |
0 |
6,5 |
0 |
0 |
0 |
10 |
0,1 |
0,1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
4 |
11 |
5 |
12 |
3,2 |
2 |
1 |
24 |
1 |
5 |
1 |
15 |
0,2 |
-0,1 |
0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
7 |
3 |
0 |
5 |
2 |
1 |
0 |
8,7 |
1 |
2 |
0 |
4 |
0,2 |
0,3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
5 |
12 |
0 |
10 |
3 |
2 |
0 |
140 |
1 |
8,3 |
0 |
48 |
0,5 |
0,8 |
0 |
11 |
12 |
4 |
13 |
18 |
1 |
0 |
18 |
52 |
0 |
0 |
0 |
10 |
0,3 |
-0,1 |
0,5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
12 |
9 |
11 |
14 |
0 |
1 |
1,2 |
38 |
0 |
0 |
3,1 |
7,8 |
–0,2 |
0,3 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
7 |
12 |
9 |
10 |
1 |
1,3 |
0 |
30 |
1 |
4 |
0 |
53 |
0,3 |
0,4 |
0 |
14 |
12 |
5 |
4 |
6 |
3 |
10 |
0 |
46 |
1 |
11 |
0 |
20 |
0,1 |
0,2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
21 |
15 |
0 |
9 |
8 |
5 |
0 |
98 |
5 |
2 |
0 |
90 |
0,5 |
0,4 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
3 |
4 |
2 |
2 |
4 |
2 |
1 |
18 |
3 |
0 |
1 |
9 |
–0,1 |
0,1 |
0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
3 |
1 |
2 |
2 |
3 |
2 |
1 |
20 |
1 |
5 |
1 |
7 |
–0,4 |
0,1 |
–0,3 |
18 |
6 |
4 |
7 |
5 |
2 |
1 |
3 |
9 |
1 |
1 |
2 |
17 |
0,2 |
0,3 |
0,1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
12 |
11 |
2 |
18 |
1 |
1 |
2 |
30 |
1 |
3 |
3 |
49 |
0,12 |
0,7 |
0,18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
20 |
14 |
13 |
21 |
1 |
1 |
0 |
40 |
1 |
4 |
0 |
74 |
0,3 |
0,4 |
0 |
21 |
3 |
2 |
7 |
8 |
3 |
2 |
1 |
22 |
1 |
5,1 |
1 |
14,8 |
–0,2 |
0,1 |
–0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
9 |
3 |
0 |
6 |
0 |
1 |
3 |
6,5 |
1 |
1 |
0 |
10 |
0,1 |
0,1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
8 |
9 |
3 |
12 |
1 |
2 |
3,1 |
20 |
1 |
5 |
1 |
15 |
0,2 |
–0,1 |
0,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
24 |
9 |
7 |
0 |
5 |
0 |
1 |
2 |
8,7 |
1 |
2 |
0 |
7 |
0,2 |
0,3 |
0 |
25 |
5 |
7 |
0 |
8 |
3 |
4 |
1 |
40 |
1 |
8,3 |
0 |
51 |
0,5 |
0,8 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
26 |
5 |
4 |
8 |
11 |
1 |
2 |
16 |
45 |
0 |
0 |
0 |
0 |
0,3 |
–0,1 |
0,5 |
63
" Компьютерный практикум по информатике и программированию
№ |
a1 |
a2 |
a3 |
b1 |
c1 |
c2 |
c3 |
b2 |
d1 |
d2 |
d3 |
b3 |
p1 |
p2 |
p3 |
27 |
2 |
3 |
8 |
7 |
1 |
1 |
1,2 |
18 |
0 |
0 |
3,1 |
9,8 |
–0,2 |
0,3 |
0 |
28 |
3 |
5 |
0 |
4 |
0 |
1,3 |
1 |
5 |
1 |
4 |
0 |
8 |
0,3 |
0,4 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
29 |
7 |
9 |
0 |
6 |
1 |
10 |
2 |
26 |
1 |
11 |
0 |
90 |
0,1 |
0,2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
12 |
5 |
0 |
12 |
8 |
8 |
4 |
104 |
5 |
0 |
0 |
32 |
0,5 |
0,4 |
0 |
1.4.8. Команда Поиск решения. Транспортная задача
Постановка задачи
Имеется m исходных пунктов, на которых сосредоточен однородный продукт (уголь на m шахтах, зерно на m элеваторах, вооружение на m складах, информация в m пунктах). Известно количество продукта ai на каждом пункте (i = 1...m). Имеется n конечных пунктов (пунктов назначения), в которые должен быть доставлен продукт в количестве bj (j = 1...n) на каждый пункт. Известна также стоимость cij доставки ед. груза по маршруту Ai–Bj.
Задача заключается в определении такого плана доставки грузов, при котором либо вывозятся все ресурсы из исходных пунктов, либо удовлетворяются потребности всех пунктов назначения и при котором суммарные затраты на транспортировку минимальны.
Задача может быть представлена в виде графа (рис. 1.51). Рассмотрим линейную транспортную задачу (ЛТЗ) с m=2, n=3.
Рис. 1.51
64
1. Практикум по курсу пользователя персонального компьютера "
Над стрелками — стоимости, которые обычно зависят от средств транспортирования, расстояния, тарифов, других факторов. Очевидно, что число маршрутов примера = 6, а в общем случае = m × n.
Математическая постановка задачи
Обозначим переменной xij объем перевозок по маршруту Ai–Bj. Тогда ограничения могут быть сформулированы следующим образом:
• из любого исходного пункта не может быть вывезено больше продукта, чем в нем имеется:
n
∑ xij ≤ ai , i = 1...m;
j=1
•в любой пункт назначения не может быть доставлено количество продукта, превышающее потребности этого пункта:
m
∑ xij ≤ bj , j = 1...n;
i=1
• перевозки осуществляются только из исходных пунктов в пункты назначения: xij ≥ 0, i = 1...m, j = 1...n.
Целевая функция имеет вид
m |
n |
F = ∑ ∑ cij xij |
|
i=1 |
j=1 |
и подлежит минимизации.
Методика выполнения задания
Рассмотрим выполнение задания на примере. Пусть имеется 4 исходных пункта со следующими запасами продукта (например, в тоннах): a1 = 15; a2 = 10; a3 = 25; a4 = 30 (ячейки С5:С8 на рис. 1.52); имеется также
6 пунктов назначения с потребностями: b1 = 10; b2 = 15; b3 = 5; b4 = 35; b5 = 5; b6 = 10 (ячейки D4:I4). Стоимость перевозки единицы груза по маршруту Ai–Bj представлена матрицей стоимостей (ячейки D5:I8 на рис. 1.52).
На рис. 1.53 представлены матрица перевозок и вспомогательная матрица для расчёта целевой функции, а также формулы, внесённые в соответствующие ячейки.
Постановка задачи примера (указание на целевую ячейку и формулировка условий) показана на рис. 1.54.
65
" Компьютерный практикум по информатике и программированию
Рис. 1.52
Рис. 1.53
Рис. 1.54
66
1. Практикум по курсу пользователя персонального компьютера "
Перед запуском поиска решения необходимо установить в разделе
«Параметры» признак «Линейная модель» (рис. 1.55).
Рис. 1.55
На рис. 1.56 показан результат поиска решения (F=115).
Рис. 1.56
67
" Компьютерный практикум по информатике и программированию
Варианты задач
№ |
ai |
bj |
|
|
Cij |
|
|
|
10 |
5 |
3 |
2 |
|
3 |
1 |
|
|
|
|
|
|
|
|
1 |
5 |
7 |
4 |
1 |
|
4 |
2 |
|
|
|
|
|
|
|
|
10 |
11 |
1 |
4 |
|
2 |
1 |
|
|
|
||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
12 |
7 |
8 |
|
5 |
2 |
|
|
|
|
|
|
|
|
2 |
13 |
11 |
1 |
3 |
|
7 |
6 |
21 |
10 |
3 |
2 |
|
4 |
1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
3 |
2 |
4 |
|
3 |
1 |
3 |
6 |
4 |
1 |
5 |
|
2 |
4 |
|
|
|
|
|
|
|
|
3 |
5 |
5 |
1 |
|
3 |
3 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
13 |
7 |
3 |
7 |
|
8 |
1 |
|
|
|
|
|
|
|
|
4 |
70 |
8 |
2 |
5 |
|
6 |
7 |
|
|
|
|
|
|
|
|
5 |
17 |
1 |
4 |
|
3 |
2 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
56 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
12 |
4 |
3 |
|
2 |
1 |
|
|
|
|
|
|
|
|
5 |
40 |
11 |
5 |
7 |
|
4 |
2 |
|
|
|
|
|
|
|
|
15 |
10 |
4 |
1 |
|
5 |
7 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
40 |
14 |
5 |
2 |
|
4 |
1 |
|
|
|
|
|
|
|
|
6 |
25 |
15 |
6 |
1 |
|
5 |
8 |
|
|
|
|
|
|
|
|
10 |
18 |
7 |
3 |
|
2 |
9 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
28 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
15 |
4 |
2 |
|
3 |
1 |
|
|
|
|
|
|
|
|
7 |
35 |
20 |
3 |
4 |
|
5 |
2 |
20 |
5 |
5 |
1 |
|
7 |
3 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
68
1. Практикум по курсу пользователя персонального компьютера "
№ |
ai |
bj |
|
|
Cij |
|
|
|
100 |
45 |
1 |
2 |
|
5 |
3 |
8 |
105 |
75 |
2 |
3 |
|
6 |
8 |
35 |
20 |
1 |
4 |
|
7 |
1 |
|
|
|
||||||
|
|
100 |
|
|
|
|
|
|
70 |
100 |
4 |
3 |
|
5 |
4 |
9 |
65 |
20 |
6 |
4 |
|
1 |
5 |
45 |
15 |
2 |
1 |
|
7 |
4 |
|
|
|
||||||
|
|
45 |
|
|
|
|
|
|
35 |
47 |
5 |
3 |
|
2 |
4 |
10 |
10 |
5 |
2 |
4 |
|
1 |
5 |
85 |
8 |
3 |
1 |
|
3 |
6 |
|
|
|
||||||
|
|
70 |
|
|
|
|
|
|
5 |
5 |
3 |
2 |
|
3 |
1 |
11 |
10 |
2 |
4 |
1 |
|
4 |
2 |
10 |
11 |
1 |
4 |
|
2 |
1 |
|
|
|
||||||
|
|
7 |
|
|
|
|
|
|
15 |
10 |
7 |
8 |
|
5 |
2 |
12 |
13 |
13 |
1 |
3 |
|
7 |
6 |
23 |
10 |
3 |
2 |
|
4 |
1 |
|
|
|
||||||
|
|
18 |
|
|
|
|
|
|
11 |
5 |
2 |
4 |
|
3 |
1 |
13 |
6 |
2 |
1 |
5 |
|
2 |
4 |
4 |
5 |
5 |
1 |
|
3 |
3 |
|
|
|
||||||
|
|
9 |
|
|
|
|
|
|
13 |
7 |
3 |
7 |
|
8 |
1 |
14 |
67 |
6 |
2 |
5 |
|
6 |
7 |
8 |
17 |
1 |
4 |
|
3 |
2 |
|
|
|
||||||
|
|
58 |
|
|
|
|
|
|
28 |
12 |
4 |
3 |
|
2 |
1 |
|
|
|
|
|
|
|
|
15 |
40 |
11 |
5 |
7 |
|
4 |
2 |
17 |
9 |
4 |
1 |
|
5 |
7 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
69
" Компьютерный практикум по информатике и программированию
№ |
ai |
bj |
|
|
Cij |
|
|
|
35 |
14 |
5 |
2 |
|
4 |
1 |
|
|
|
|
|
|
|
|
16 |
25 |
15 |
6 |
1 |
|
5 |
8 |
|
|
|
|
|
|
|
|
15 |
17 |
7 |
3 |
|
2 |
9 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
29 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
15 |
4 |
2 |
|
3 |
1 |
|
|
|
|
|
|
|
|
17 |
35 |
20 |
3 |
4 |
|
5 |
2 |
|
|
|
|
|
|
|
|
23 |
6 |
5 |
1 |
|
7 |
3 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
39 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
98 |
45 |
1 |
2 |
|
5 |
3 |
|
|
|
|
|
|
|
|
18 |
105 |
75 |
2 |
3 |
|
6 |
8 |
|
|
|
|
|
|
|
|
37 |
24 |
1 |
4 |
|
7 |
1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
96 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
70 |
90 |
4 |
3 |
|
5 |
4 |
|
|
|
|
|
|
|
|
19 |
63 |
30 |
6 |
4 |
|
1 |
5 |
|
|
|
|
|
|
|
|
47 |
15 |
2 |
1 |
|
7 |
4 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
45 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30 |
47 |
5 |
3 |
|
2 |
4 |
|
|
|
|
|
|
|
|
20 |
15 |
5 |
6 |
4 |
|
1 |
5 |
|
|
|
|
|
|
|
|
85 |
9 |
3 |
1 |
|
3 |
6 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
69 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
6 |
3 |
2 |
|
3 |
1 |
|
|
|
|
|
|
|
|
21 |
7 |
7 |
4 |
1 |
|
4 |
2 |
|
|
|
|
|
|
|
|
8 |
12 |
1 |
4 |
|
2 |
1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
12 |
7 |
8 |
|
5 |
2 |
|
|
|
|
|
|
|
|
22 |
9 |
10 |
1 |
3 |
|
7 |
6 |
|
|
|
|
|
|
|
|
25 |
11 |
3 |
2 |
|
4 |
1 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
70