Решение. Расположение компьютеров и количество известно заранее, значит, длину кабеля для соединения их между собой тоже будем считать известной

Расположение компьютеров и количество известно заранее, значит, длину кабеля для соединения их между собой тоже будем считать известной. Тогда перед нами стоит задача обойти все компьютеры с минимальными затратами на кабель. Исходя из заданной топологии (кольцо) задачу можно свести к задаче коммивояжера (обойти все пункты назначение по 1 разу, таким образом что бы длинна пройденного пути была минимальна). Данная задача относится к целочисленному программированию.

Описание переменных

-булева переменная. 1 – компьютер I соединен с компьютером J кабелем

0 – компьютер I не соединен с компьютером J кабелем

-длина кабеля, требуемая для соединения I компьютера с J

Критерий

Необходимо чтобы в каждый узел (компьютер) входило не более одного кабеля (в соответствии с топологией)

Необходимо чтобы из каждого узла (компьютер) выходило не более одного кабеля (в соответствии с топологией)

Необходимо добавить условия для исключения колец длиной меньше чем N, для того чтобы не получились отдельные кольца.

Например, для исключения колец длиной 2 узла необходимы условия

…

В общем виде это можно записать так

n – исключаемая длина кольца принимает значения от 2 до , где N количество узлов в сети, - целая часть вещественного числа

k – принимает значение от 1 до N-n

В итоге имеем модель

Задача может решаться любым методом целочисленного программирования, например, методом ветвей и границ или аддитивным методом.

3. Дан отрезок длиной L. Необходимо разбить его на п отрезков так, чтобы произведение их длин было максимальным. Предложить метод решения.

Составим модель

Критерий запишем на основании условий задачи

Получили задачу нелинейного программирования, класс задачи геометрическое программирование, т.к. целевая функция имеет вид позинома.

Решать можно методом штрафных функций (поиск условного экстремума функции).

4. Дана платежная матрицы игры 2-х лиц с нулевой суммой (платежи имеют смысл убытков для игрока Л). Построить математическую модель игрока А.

 

 

Стратегии игрока А	Стратегии игрока В
В 1	В 2	В 3	В 4
А 1	-5		-2
А2			-1
А 3				-2

Это состязательная задача. Антогонистичская игра (цели противоположны).

Такая игра имеет решение в области смешанных решений. Пусть X=(x ₁, x _2, x ₃) – распределение вероятностей на стратегии игрока А. Тогда согласно принципу гарантированного результата, этот игрок будет выбирать такое поведение (распределение Х^*), которое минимизирует наибольший ожидаемый проигрыш

(U_ij имеют смысл проигрышей игрока А), т.е.

Обозначим через n максимальный ожидаемый проигрыш (цена игры), т.е.

n =

n =

Отсюда видно, что n не меньше каждого ожидаемого проигрыша, и т.к. цель минимальный проигрыш, то приходим к эквивалентной задаче

L= n ®min

при ограничениях

т.е.

£ n,

£ n,

£ n,

£ n,

 

Окончательный вид модели:

L= n ®min

£ 0,

£ 0,

£ 0,

£ 0,

Задача решается симплекс-методом.

РЕШЕНИЕ НЕ ОБЯЗАТЕЛЬНО!

Решение: Приведем модель к каноническому виду:

L= - n ®max

+ x ₄£ 0,

+ x ₅£ 0,

+ x ₆£ 0,

+ x ₇£ 0,

x ₁+ x ₂+ x ₃+ x ₈=1

L= - n - 100 x ₈®max

 

Табл. 0									-100	-1
i	C i	Баз	A0	A1	A2	A3	A4	A5	A6	A7	A8	Av	q
		A4		-5								-1	-
		A5										-1	-
		A6		-2	-1							-1	-
		A7				-2						-1
	-100	A8
		Dj	-100	-100	-100	-100
	z	-100	-100	-100	-100					-100

 

Табл. 1									-100	-1
i	C i	Баз	A0	A1	A2	A3	A4	A5	A6	A7	A8	Av	q
		A4				-2						-6	-
		A5										-1
		A6										-3	-
		A1				-2						-1	-
	-100	A8			-6					-1			1/3
		Dj	-100			-300						-99
	z	-100			-300					-100	-100

 

Табл. 2

-100

-1

i

C i

Баз

A0

A1

A2

A3

A4

A5

A6

A7

A8

Av

q

A4

2/3

-20/3

-

A3

1/3

-1/3

-

A6

-3

-

A1

2/3

-5/3

-

-100

A8

-9

-1

-1

1/2

Dj

-100

-200

z

-100

-100

-200

Табл. 3

-100

-1

i

C i

Баз

A0

A1

A2

A3

A4

A5

A6

A7

A8

Av

q

A4

20/6

-16/6

10/6

20/6

A3

1/6

-1/2

1/6

-1/6

1/6

A6

3/2

-1/2

-3/2

1/2

3/2

A1

5/6

9/6

-1/6

1/6

5/6

-1

Av

1/2

-9/2

-1/2

-1/2

1/2

Dj

-1/2

9/2

1/2

1/2

199/2

z

-1/2

9/2

1/2

1/2

-1/2

-1

 

Так как все D_j > 0 (A₀ не рассматриваем), то мы нашли оптимальное решение.

 

Ответ: L=0, 5; x₁=5/6; x₂=0; x₃=1/6;

 

 

5. Имеется n различных приборов, каждый из которых может выдавать единиц информации/сек и весит m_i, кг. Допустимый вес научного контейнера G, кг. Как определить наилучший набор приборов? (Модель и метод).

характеризуется надежностью (ликвидность в днях) и доходностью (%). Известна номинальная и рыночная цена ценной бумаги каждого вида в у.е. Построить модель для определения оптимального варианта вложения свободных денег в пределах N у.е.

 

6. Дана сеть нефтепроводов, связывающая пункт добычи А с портом В. Известны пропускные способности каждой нитки (цифры у дуг). Одним из методов оптимизации определить максимальное количество нефти, которое можно поставлять в порт.

Данная задача «Задача о максимальном потоке» относится к транспортным задачам (транспортным сетям). Вопрос №7.

0 шаг

-Задаем начальный поток. В качестве начального можно взять нулевой поток. Значения начальных потоков даны за косой чертой. Z(0)=0. -Строим увеличивающую цепь (толстые линии). -Определяем приращение потока: q0= min (12-0, 4-0, 6-0, 2-0)=2. Увеличиваем поток дуг цепи на 2 (рисунок ниже), в результате получаем Z(1)=Z(0)+q0 = 0+2 = 2.

1шаг

q0 = min (12-2, 5-0, 10-0) = 5. Z(2) = Z(1)+q0 = 2+5 = 7.

2шаг

q0 = min (7-0, 8-0, 3-0) = 3. Z(3) = Z(2)+q0 = 7+3 = 10.

3шаг

q0 = min (7-3, 8-3, 4-0, 10-5)=4. Z(4) = Z(3)+q0 = 10+4 = 14.

 

4шаг

На данном шаге увеличивающую цепь построить нельзя, следовательно, достигнуто оптимальное решение: найден максимальный поток сети. Z(4) = 14 - максимальный поток, т.е. максимальное количество нефти. A = {t, 1, 2, 3, 5} P(A) = {1, 4; 3, s; 5, s; 5, 4} – min разрез сети d(A) = d14 + d3S + d5S + d54 = 5 + 2 + 3 + 4 = 14 – пропусканная способность min разреза

 

 

Построить модель для определения состава команды и распределения участников команды по этапам. Время, показанное кандидатами в предварительных пробах на этапах, приведено в таблице.

Решение

Наша задача сводится к тому, что необходимо минимизировать общее время команды.

Переменные принимают значения 0 или 1 (не бежит / бежит). Задача целочисленного программирования.

Критерий:

L = 7x₁₁+5x₁₂+8x₁₃+6x₁₄+7x₁₅+9x₁₆ +

+12x₂₁+16x₂₂+17x₂₃+14x₂₄+11x₂₅+13x₂₆ +

+10000x₃₁+23x₃₂+20x₃₃+25x₃₄+21x₃₅+10000x₃₆ +

+3x₄₁+4x₄₂+10000x₄₃+6x₄₄+5x₄₅+4x₄₆® min

Первая цифра в индексе номер этапа. Вторая цифра - номер частника.

Для кандидата, не бегущего какой-то этап (x₃₁, x₃₆, x₄₃), время ставим большим числом, в нашем случае подставлено 10000.

Ограничения:

На каждом этапе должен бежать один человек.

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆ = 1

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆ = 1

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆ = 1

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆ = 1

Человек бежит только один этап или вообще не бежит.

x₁₁+x₂₂+x₃₁+x₄₁ £ 1

x₁₂+x₂₂+x₃₂+x₄₂ £ 1

x₁₃+x₂₃+x₃₃+x₄₃ £ 1

x₁₄+x₂₄+x₃₄+x₄₄ £ 1

x₁₅+x₂₅+x₃₅+x₄₅ £ 1

x₁₆+x₂₆+x₃₆+x₄₆ £ 1

Все x принимают значения либо 0, либо 1.

Задача решается методом ветвей и границ.

Правильный ответ (решено в Lindo):

1 этап – кандидат 2

2 этап – кандидат 5

3 этап – кандидат 3

4 этап – кандидат 1

время = 28

MIN 7 X11 + 5 X12 + 8 X13 + 6 X14 + 7 X15 + 9 X16 + 12 X21 + 16 X22 + 17 X23 + 14 X24 + 11 X25 + 13 X26 + 10000 X31 + 23 X32 + 20 X33 + 25 X34 + 21 X35 + 10000 X36 + 3 X41 + 4 X42 + 10000 X43 + 6 X44 + 5 X45 + 4 X46

SUBJECT TO

X11 + X12 + X13 + X14 + X15 + X16 = 1

X21 + X22 + X23 + X24 + X25 + X26 = 1

X31 + X32 + X33 + X34 + X35 + X36 = 1

X41 + X42 + X43 + X44 + X45 + X46 = 1

X12 + X22 + X32 + x42 < = 1

X13 + X23 + X33 + X43 < = 1

X14 + X24 + X34 + X44 < = 1

X15 + X25 + X35 + X45 < = 1

X16 + X26 + X36 + X46 < = 1

END

INT 20

LP OPTIMUM FOUND AT STEP 5

OBJECTIVE VALUE = 39.0000000

FIX ALL VARS.(16) WITH RC > 1.00000

NEW INTEGER SOLUTION OF 39.0000000 AT BRANCH 0 PIVOT 7

BOUND ON OPTIMUM: 39.00000

ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 7

LAST INTEGER SOLUTION IS THE BEST FOUND

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 39.00000

VARIABLE VALUE REDUCED COST

X11 0.000000 7.000000

X12 1.000000 5.000000

X13 0.000000 8.000000

X14 0.000000 6.000000

X15 0.000000 7.000000

X16 0.000000 9.000000

X21 0.000000 12.000000

X22 0.000000 16.000000

X23 0.000000 17.000000

X24 0.000000 14.000000

X25 1.000000 11.000000

X26 0.000000 13.000000

X31 0.000000 10000.000000

X32 0.000000 23.000000

X33 1.000000 20.000000

X34 0.000000 25.000000

X35 0.000000 21.000000

X36 0.000000 10000.000000

X41 1.000000 3.000000

X42 0.000000 4.000000

X43 0.000000 10000.000000

X44 0.000000 6.000000

X45 0.000000 5.000000

X46 0.000000 4.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 0.000000

3) 0.000000 0.000000

4) 0.000000 0.000000

5) 0.000000 0.000000

6) 0.000000 0.000000

7) 0.000000 0.000000

8) 1.000000 0.000000

9) 0.000000 0.000000

10) 1.000000 0.000000

NO. ITERATIONS= 7

BRANCHES= 0 DETERM.= 1.000E 0