Шпаргалки по Математическим методам в экономике
Подождите немного. Документ загружается.
1. Объясните термин «Линейное программирование».
Наука о методах исследования и отыскании макс. и мин. лин. функций, на неизвестные которых наложены лин. ограничения, т. о. ЗЛП относится к
задачам на условный экстремум функции.
2. Перечислите основные предпосылки теории ЛП.
1939 – Канторович написал труд «Мат. Методы организации и планирования пр-ва», где впервые сформулир-л задачу ЛП и привел алгоритм реш-я,
попытался оптимизир-ть пр-ный процесс, т.е. впервые пытался понять сколько, чего и по какой технологии произв-ть, в 1941 Хичкок и 1947
Купманс независимо др. от др-га сформулир-ли трансп-ную задачу, 1947 – Данциг придумал алгоритм с/метода, 1975 – Канторович и Купманс
получили Ноб-ю премию за создания алгоритма ЛП.
3. Назовите основные составляющие экономико-математической модели ЛП.
1) Система функц – технологич лин-х огранич-ний: равенств, неравенств
i=1…m
2) Система логических ограничений x
j
>=0, j = 1…n
3) Наличие лин-ной ф-ции, которая максимизир-ся или минимизир-ся (целевая ф-ция).
C(x) max (min)
4. Какая модель ЛП называется стандартной, запишите эту модель в векторной форме.
Ax<=b: x>=0, C(x)=(C,x)=>max
5. Запишите стандартную модель ЛП в алгебраической (подробной) форме.
a
11
, x
1
+a
12
x
2
+…a
1n
x
n
<=b
1
………………………………..
a
m1
x
1
+a
m2
x
2
+…..a
mn
x
n
<=b
m
x
1,………
x
n
>=0
C(x) = C
1
x
1
+C
2
x
2
+…….C
n
x
n
=>max
6. Каково соотношение между числом ограничений и неизвестных в стандартной модели ЛП.
m и n не связаны
7. Дайте определение оптимального плана задачи ЛП.
Пусть Х*D (т.е. Х*=( x*
1,…
x*
n
) >=О – компоненты все неотриц-ны). Если для любого х прин-щего D, (х Х*) С(х)<=C(X*) => X* - оптимальный
план
8. Может ли задача ЛП иметь бесконечное число оптимальных планов? Дайте геометрическю интерпретацию ответа.
Да. С(А)=С(В)=С(Х*), Х*[A,B] + рисунок!!!
9. Может ли задач ЛП иметь ровно 2 оптимальных плана?
Нет
10. Перечислите случаи, когда задача ЛП может не иметь решения.
1) Д=, 2) С(х) неограничена на мн-ве Д
11. Какая модель ЛП называется канонической. Запишите ее в векторной и алгебраической (подробной) форме.
Ах=b
x>=0
C(x)=(C,x)=>max
a
11
x
1
+a
12
x
2
+…a
1n
x
n
=b
1
………………………………..
a
m1
x
1
+a
m2
x
2
+…..a
mn
x
n
=b
m
x
1,………
x
n
>=0
C(x) = C
1
x
1
+C
2
x
2
+…….C
n
x
n
=>max
12. Дайте определение допустимого множества стандартной задачи и его геометрическую интерпретацию.
D = { X=( x
1,…
x
n
: Ax<=b; x>=О} – допустимое мн-во станд-тной задачи + рис-к!!!
13. Каково соотношение между числом неизвестных и ограничений в канонической модели ЛП, аргументируйте ответ.
m<n. Если m>n – с-ма ур-ний Ax=b не имеет смысла, m=n – с-ма ур-ний имеет единств-е реш-е, след-но нет смысла искать max C(x)
14. Для чего в линейном программировании используются дополнительные переменные.
Для преобразования стандартной ЗЛП в каноническую.
15. Дайте содержательную интерпретацию дополнительных переменных.
Неиспользованное количество i-го ресурса при реализации производственного плана.
16. Какова роль градиента функции в графическом решении задачи ЛП.
Указывает скорость и направление роста значения ц. ф. при изменении переменных.
17. Может ли иметь решение задача ЛП, если ее допустимое множество неограниченно, дайте графическую интерпретацию ответа.
Нет.
С(х)>>M, т.е. С(х) неограниченна на Д + рис-к!!!
18. Приведенная форма системы линейных уравнений и ее роль в решении задачи ЛП.
0,11,1
20,211,22
10,111,11
0
'...'
.............................
'...'
'...'
'
mnnmmmm
nnmm
nnmm
xxaxax
xxaxax
xxaxax
xxAxE
Развернутая(алгебраическая) форма
19. Определение носителя допустимого плана.
X
D, xj>=0, j=1…n, (x)={j: xj>0, j=1,…,n} - носитель допустимого плана.
20. Как определяется носитель псевдоплана.
Х=(x
1
,…,x
n
) - псевдоплан, (x)={i: xi≠0, i=1,…,n} - носитель псевдоплана.
21. Что общего между планом и псевдопланом канонической модели ЛП.
Компоненты плана удовлетворяют ограничениям канонической задачи Ax=b.
22. Чем отличаются базисный план и псевдоплан.
Базисный план Х* =(x*
1
,…,x*
n
)
D – допустимый план канонической задачи Ах = b, x>=0, C(x)=>max, /σ*/<=m – кол-во ненулевых компонент.
Компоненты базисного плана x
j
>=0. Компоненты псевдоплана м.б. любые, в том числе и отрицательные.
23. Смысл элементов технологической матрицы и многопродуктовой модели.
a
ij
- кол-во i-го ресурса для производства j-го продукта (i=1,…,m; j=1,…,n).
24. Смысл элементов технологической матрицы в однопродуктовой модели производственного планирования.
a
ij
- кол-во i-го ресурса для производства единицы продукта по технологии j (i=1,…,m; j=1,…,n).
25. Определение базисного плана.
1
,
1
n
j
ijij
bxa
План
o
X
, коорд.которого опред. по ф-ле
i
ix
x
io
i
,0
,
,
o
X
=(x1,x2,…xN)=(x10,x20,...xM0,0,0,..0)
26. Напишите формулу для вычисления двойственных оценок, объясните смысл входящих в эту формулу величин.
1)
njCaCj
jiji
i
,...,1,0'
или Δj = (С
σ
,Aj) - Сj, где С
σ
– коэффициент при базисных переменных в ц. ф-ции, Аj - j-ый
столбец с/т, Сj - коэф. ц. ф. при j-ой неизвестной.
2) y*=(A
-1
)C
, C
- коэффициент ц.ф., A
-1
- матрица, составленная из столбцов 1-вой с-мы и столбцов, составленных из базисных векторов
последней с/таблицы
27. Сформулируйте признак оптимальности базисного плана.
Ax=b
x>=0 (1) Axb=>A’x=b’ – приведенная форма
c(x)=>max
X
0
= (x
0
1
,…,x
0
n
) – базисный план (1). Если Δj=
njCaC
jiji
i
,...,1,0'
то X
0
– оптимальный план.
28. Что такое суперпсевдоплан.
Ax=b
x>=0 (1)
c(x)=>max
Х*=(x*
1
,…,x*
n
) – супер псевдоплан, если АХ* = b, /σ*/<=m, σ(x*)={i: x*i≠0, i=1,…,n} - носитель этого псевдоплана, и соответствующие
двойственные оценки Δj=
njCaC
jiji
i
,...,1,0'
.
29. Сколько положительных компонент может быть в базисном плане.
Положительных компонент в базисном плане м. б. < m (число уравнений).
30. Почему не могут ровняться нулю все двойственные оценки, соответствующие дополнительным переменным оптимального плана.
Если все двойственные оценки Δj=0, то все ресурсы избыточны, а этого не может быть (A
т
yС y=0 => C=0 – ничего не производим).
31. Как должна выглядеть с/таблица перед применением с/метода.
В последней строке среди Δj, j=1…..n, д. б. Δj<0, а в соотв. min Δj столбце должно быть a
ik
>0; в столбце А
0
все числа a
i0
должны быть >0.
32. Как должна выглядеть с/таблица перед применением двойственного с/метода.
В столбце А
0
д. б. хотя бы одно отриц. число a
i0
<0 (т.е. в А
0
записан суперпсевдоплан) и в последн. строке Δj>0.
33. Что означает факт невозможности преобразование с/таблицы с помощью алгоритма с/метода.
1.) Найден оптимальный план, 2.) Д – неограниченный многогранник, т.е. С(х) неограничена на Д.
34. Что означает факт невозможности преобразование с/таблицы с помощью алгоритма двойственного с/метода.
а) найден оптимальный план. б) D =
35. В каком случае преобразование с/таблицы с помощью с/метода оказываектся невозможным.
Х
k
– базисный план, полученный с/методом на k-той итерации Δk = minΔj<0, j = 1…n, если min a
ik
<=0, i
σ
k
, C(x)
=> ЗЛП неразрешима.
36. В каком случае преобразование с/таблицы с помощью двойственного с/метода оказывается невозможным.
Х
0
– суперпсевдоплан, х
0
r
– отрицательная компонента Х
0
, х
0
r
<0, r
σ (х
0
r
=a
ro
). Если все a
rj
>=0, j=1….n, D=
=> ЗЛП неразрешима.
37. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется с/метод.
Х – базисный план, Δk = minΔj<0, j = 1…n, k - результат 1-го шага алгоритма, a
ro
/a
rk
= min(a
io
/a
ik
), a
ik
>0, i
σ, r - результат 2-го шага,=> a
rk
-
ведущий элемент
38. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется двойственный с/метод.
X – суперпсевдоплан. a
ro
=min(a
io
), i
σ, r – результат первого шага алгоритма, r
σ, a
ro
<0, a
rk
=max(Δj/a
rj
), a
rj
<0, j=1...n, a
rk
<0 kσ, т.к. a
rj
<0
39. Верно ли, что двойственная задача к стандартной имеет канонический вид, а двойственная задача к канонической имеет стандартный вид.
Нет.
40. Напишите двойственную задачу к следующей задаче ЛП: AX=B, X>=0, C(X) MIN
А
т
Y-C
B(y)=>min
41. Напишите двойственную задачу к следующей задаче ЛП:AX>=B, C(X) MAX
-А
т
Y=C
Y0
B(y)=>max
42. Сколько ограничений и неизвестных в двойственной задаче.
Ограничений столько, сколько переменных в прямой (исходной) задаче (n).
Неизвестных столько, сколько ограничений в прямой (исходной) задаче (m).
43. Сколько ограничений-равенств в прямой задаче ЛП, если все переменные двойственной задачи неотрицательны.
Ограничений – равенств в прямой задаче нет.
44. Известен план прямой задачи и план двойственно задачи. Что можно сказать о разрешимости этих задач; аргументируйте ответ.
Если одна из пары двойственных задач разрешима, то разрешима и другая (имеет оптимальный план). Причем Х* - оптимальный план , Y* -
оптимальный план => C(X*)=B(Y*)
45. Пусть Х – план прямой задачи, а У – план двойственной задачи. Что следует из равенства С(Х) = В(Y)?
Эти планы – оптимальны.
46. Пусть выполняется равенство С(Х) = В(Y), причем известно, что Х – неоптимальный план прямо задачи; что можно сказать о векторе Y?
Такая ситуация невозможна по признаку оптимальности прямой и двойственной задач(Лемма2).
47. Сформулируйте первую теорему двойственности (терему разрешимости).
Axb
x0 (1)
(C,x)=>max
А
т
YC
Y0 (2)
(B,Y)=>min
Если одна из задач дв. пары разрешима, то др. задача разрешима, причем значение целевых функций на оптимальных планах прямой и
двойственной задач совпадают, если Х* - оптимальный план (1), Y* - оптимальный план (2), то С(Х*)=С(Y*).
Если С(х) одной из пары двойственных задач неограниченна на Д, то Д другой задачи – пусто.
48. Сформулируйте Лемму 1 о планах прямой и двойств. задач.
Axb
x0 (1)
(C,x)=>max
2
А
т
YC
Y0 (2)
(B,Y)=>min
D
1
– допустимое мн-во (1), D
2
- допустимое мн-во (2)
Если X
D
1
, Y
D
2
=> C(X)<В(Y).
49. Приведите формулировку теоремы равновесия(Вторая Т. двойствености).
Чтобы х* и y* были оптимальными планами задач (1) и (2) необходимо и достаточно, чтобы выполнялись следующие соотношения
x
j
* [
m
i
jiij
cya
1
*
] = 0, j=1…..n,
y*
j
[
n
j
ijij
bxa
1
*
] = 0, i=1….m.
50. Дайте экономическую интерпретацию равенства Х(А
т
– С) = 0
C
j
– цена j-го товара
51. Дайте экономическую интерпретацию равенства У (b – AX) = 0, входящего в формулировку теоремы равновесия.
n
j
i
j
ij
i
bxay
1
**
0)(
1.
полностьюсяиспольресурсbxaтоy
i
j
ij
i
__,0
**
2.
избыточенресурсbxaтоy
i
j
ij
i
_,0
**
52. Что фактически понимается под структурой производственного плана.
Номенклатура (состав) выпускаемых продуктов, которые входят в план производства; 2) Перечень дефицитных и избыточных ресурсов; 3)
Сведения о том, производится ли каждый продукт в наименьшем допустимом кол-ве, наиб. возможном или на промежуточном уровне
53. Каким образом формализуется понятие структуры плана в теории ЛП.
Математическим эквивалентом структуры плана является носитель плана.
54. Сколько оптимальных базисных планов с одинаковой структурой может быть у задачи ЛП.
Много.
)()(,)(),(,,
212121
xxносителиxxпланыxx
структура одинакова
55. Сколько интервалов устойчивости ассоциируется с оптимальным планом.
Для каждого вида ресурса может быть свой интервал устойчивости.(кажд. функциональному ограничению ЗЛП соотв.свой инт.устойчивости Sk,
k=1..m)
56. Дайте определение интервала устойчивости.
Интервал Sk опт.плана x* относительно k-го функц.ограничения ЗЛП
n
j
kjkj
bxa
1
, если для всех Δb
k
, удовлетворяющих уcловию Δb
k
min
< Δbk < Δb
k
max
, оптимальные планы ЗЛП имеют ту же саму структкру, что и план x*.
57. В чем практическое значение интервала устойчивости.
Определяет интервал изменения ресурсов, не влияющий на структуру opt плана.
58. Сколько интервалов оптимальности ассоциируется с оптимальным планом.
Для каждого коэф. ц.ф. свой план.(n интервалов оптимальности Pk, k=1..n)
59. Дайте определение интервала оптимальности(плана х* относит.k-го коэф. целевой ф-и).
Интервал Pk, если для всех значений
kkk
нов
k
PcсC
план х* останется опт.планом ЗЛП.
60. В чем практическое значение интервала оптимальности.
Определяет каковы границы колебания цен, в пределах кот.предприятие будет получать max доход при плане x*
61. Какие ресурсы в теории ЛП называются дефицитными, а какие – избыточными.
x
n+i
, i=1…m, если x
n+i
= 0 => i-тый ресурс - дефицитный, x
n+i
>0, => i-тый ресурс - избыточный
62. Как вычисляется нижняя граница интервала устойчивости для избыточного ресурса (а верхняя грница?).
Δb
p/ниж
=-x*
n+p
, Δb
p/верх
=∞; [b
p
+ Δb
p/ниж
; b
p
+Δb
p/верх
] – интервал устойчивости
n-число перемен., р- № переменной
62*.-//-дефицитного
kax
ppnkk
,0'*
,
63. Как вычисляется верхняя граница интервала оптимальности для коэффициента при небазисной переменной оптимального плана (а нижняя?).
],(
''
kkk
i
kkkkiki
i
нов
kiki
нов
k
сP
cсcaccac
63*.-//-при базисной
jлюбомприaесли
j
a
c
jлюбомприaесли
j
a
c
kj
kj
j
a
k
kj
kj
j
a
k
kj
kj
__0'_,
),
'
(
__0'_,
),
'
(
min
max
0'
max
0'
min
64. Дайте качественную экономическую хар-к двойственных оценок.
Двойственные оценки показывают во сколько раз изменится значение ц. ф. в результате изменения i-того ресурса на единицу.
65. Дайте количественную хар-ку двойственных оценок как меры дефицитности ресурсов.
Δ
n+k
=0 => k-й ресурс избыточен
3
m
i
i
ij
изделиетоеjнаресурсовтьстсуммарнаяya
1
*
_____
Δ
n+k
>0 => k-й ресурс дефицитен
66. Верно ли, что интервалы разрешимости модели ЛП с параметром и двойственно к ней совпадают, ответ обоснуйте.
Верно, это следует из 1-й теоремы двойственности.
67. Дайте определение решающей функции для модели ЛП с параметром в ограничениях.
(
),
Є(-∞;+∞),(
)=max(С,x), xЄD(
)
68. Дайте определение решающей функции для модели ЛП с параметром в целевой функции.
φ(
), где
Є(-∞;+∞), φ(
)=max(С(
)x), xЄD
69. Что необходимо сделать, чтобы вычислить значение решающей функции в некоторой фиксированной точке.
1. Необходимо конкретное значение параметра t
2. Решить ЗЛП
3. Найти значение целевой ф-ции на оптимальном плане
70. Перечислите св-ва решающей функции в модели ЛП с параметром в ограничениях.
Непрерывна, линейна на каждом интервале устойчивости, вогнута
71. Перечислите св-ва решающей функции в модели с параметром в целевой функции.
Непрерывна, линейна на каждом интервале устойчивости, выпукла
72. Что значит решить задачу линейного программирования с параметром в ограничениях.
1. Найти инт. Оптимальности(устойчивости)
2. Найти опт. Планы на этих инт.
3. Найти решающую ф-ю
73. Укажите область определения решающей функции.
Этот интервал такой, что при всех t из этого интервала решающая ф-ция разрешима φ(t) t Є T
74. Чем отличается обычная с/таблица от с/таблицы, предназначенной для решения задачи ЛП с параметром в целвой функции.
В столбце для вычисления коэф-тов цел. ф-и при базис.перем. указ. знач. параметра t в строке, где вычисляются двойств.оценки Δj(t)= Δj’+ Δj’’t.
C(x*t)=Cj’+C’’t
75. Что значит решить задачу ЛП с параметром в целевой функции.=72.
76. Чем отличается процесс решения многокритериальной задачи ЛП от решения обычной задачи ЛП.
При решении ЗМЛО находится 1 или несколько допустимых планов, удовлетворяющих, по мнению ЛПР, т.е. в решение включается субъектив.
фактор мнения ЛПР
77. Дайте определение эффективного (Парето-оптимального) решения.
Х* Є D – эффективное решение, если не существует xЄD такого, что f
j
(х*)≤f
j
(x), j=1..n, причем хотя бы для одного p f
p
(х)>f
p
(x*),то х*- парето-
оптимальный план.
78. Сколько Парето-оптимальных планов может иметь многокритериальная задача.
много
79. Что такое достижимое множество.
x=(х
1
… х
n
) ЄD. f(x)=(f
1
(x)…f
n
(x) хар-ка качества доп.плана Є R
k
. F={y=f(x),xЄD}, FC R
k
80. Какова геометрическя интерпретация допустимого множества.
Y- достижимое мн-во , Д – допустимое мн-во+ рис-к!!!
81. Что такое линейная свертка критериев.
Сведение имеющегося множества критериев к одному скалярному кр., отражающему комбинирован. общую цель системы
0
,max,)(')(
1
x
иAx
гдеxfaxf
m
k
k
н
k
a
k
>0-линейная свертка критериев f
1
f
2
….f
k
.
82. Как выбираются коэффициенты свертки (коэффициенты важности критериев).
Коэф-т важности α
k
выбирает ЛПР. Чем больше важен критерий с № k для ЛПР, тем больше α
k
87. В чем смысл нормировки критериев.
Нормировка критериев позволяет получить критерии, которые измеряются числами одного порядка. После того, как проведена нормировка и
рассматривается нормир.ф-я свертки f
н
(х), выбор α
k
действительно соответствует важности критерия с точки зрения ЛПР
88. Напишите формулу нормировки критериев.
)(),(
1
),()()(
min
max
1 1
1
xffxff
ff
pxfxfpxF
k
Dx
kk
Dx
k
N
k
N
k
kk
k
н
kkk
89. Дайте определение «идеальной» точки.
Идеальная точка f*
j
(x)=(f*
1….
f*
N
) в пространстве критериев , f*
j
=max f
j
(x), x Є D,j=1..n
90. Сколько компонент содержит «идеальная» точка.
Столько, сколько критериев в ЗЛМО
91. Является ли «идеальная» точка планом задачи ЛП.
Нет
92. Принадлежит ли «идеальная» точка достижимому множеству.
Нет, хотя в принципе может, но это бывает очень редко
93. Объясните сущность метода «идеальной» точки.
Суть метода: в множестве допустимых планов отыскивается точка, которая отражается в достижимое множество в точку, расстояние от
которой до идеальной точки F* минимально по всем критериям.
Dx
Nj
jj
xfF
min*max
1
- критерий равномерного сжатия.
Для приведения этого критерия к линейному виду, введем новую переменную:
Nj
jj
xfF
1
*max
.
Решение многокритериальной задачи сводится к нахождению оптимального плана следующей задачи:
4
0
0
,1,*
min
x
bAx
NjxfF
jj
94. Какая задача решается методом последовательных уступок.
Задача максимизации значения критерия, значение которого не достаточно велико для ЛПР
95. Какое допущение относительно критериев необходимо для применения метода последовательных уступок.
Должны быть упорядочены по степени важности
96. Для решения, каких задач применяется целевой программирование.
Для построения математических моделей многокритериальной оптимизации
97. В чем выражаются структурные особенности модели целевого программирования.
1. |U
k
- C
k
(x)|
=>min (max),
2. U
R
-
n
j
j
j
r
xa
1
3.непротиворечивость
98. Что такое «горизонт планирования».
U
k
– заранее определенный ур-нь, которого д. достигнуть k-тый критерий.
99. Кто и как определяет «горизонты планирования».
ЛПР по своему усмотрению
100. В чем смысл целевой функции в модели целевого программирования.
В min штрафов за отклонение от горизонта планирования.
101. Является ли модель целевого программирования канонической моделью ЛП.
Да
102. Что является исходными данными в транспортной задаче.
Потребности в пунктах назначения b
1
… b
m
, запасы в пунктах отправления a
1
…a
n
, кол-во поставок, кол-во потребителей матрица стоимости
перевозок m=n.
103. В чем смысл уравнения баланса А = В.
все потребности удовлетворены, все запасы из пунктов отправления д.б. доставлены потребителям.(запасы=потребности)
104. В чем содержательный смысл неизвестных в транспортной модели.
x
ij
≥0 – кол-во товара, кот везет i-й поставщик j-му потребителю(из Аi в Вj)
105. Что такое план транспортной задачи.
План перевозки однородного продукта из п.отправления в п.назначения
X= (x
ij
)
i=1
m
j=1
n
x
ij
≥0
106. Дайте содержательную интерпретацию ограничению:
сумма поставок от всех поставщиков должна удовлетворять потребности 1 потребителя полностью
107. В чем смысл следующих ограничений транспортной модели:
сумма всех товаров, которые вывозит потребителям i-тый поставщик
(свои запасы i-тый пост-шик распространит по всем потр-лям)
108. Что называется матричной моделью транспортной задачи.
1) a
i
i=1….m 3)c
ij
2) b
j
j=1… n 4)A=B
b
1
.. b
m
а
1
C
11
.. C
1n
. . . . . .. …
а
m
C
m1
.. C
mn
109. Что значит «план порождает цикл».
В матрице существует замкнутый маршрут вершины кот. нах. в ненулевых клетках матрицы перевозок, а звенья(ребра) // сторонам и столбцам
110. Дайте определение базисного допустимого(невырожденного) плана транспортной задачи.
X=(x
ij
) i=1..m, j=1..n Если ненулевых перевозок =n+m -1, нет цикла у x
ij
≥0 , то базис невыр.
111. Какой план транспортной задачи называется вырожденным.
X=(x
ij
) i=1..m, j=1..n Если ненулевых перевозок < n+m –1, то базис вырожд.
112. Роль фиктивно-положительных компонент плана транспортной модели.
Преобразование вырожденного плана в невырожденный
113. Объясните построение матричной модели, если в транспортной задаче имеет место дефицит продукта у поставщиков.
Вводим фиктивного поставщика A
m+1
, у которого кол-во продукта a
m+1
=B-A
A=B
1
1 1
m
i
n
j
ji
ba
, С
m+1,j
= 0 (фиктивное положение перевозки).
114. Объясните построение матричной модели, если в транспортной задаче предложение превышает спрос.
т.е.
n
j
j
m
i
i
ba
11
5
m
i
i
bx
1
1
1
n
j
ijij
ax
1
n
j
j
m
i
i
ba
11
вводим фиктивного потребителя В
n+1,
b
n+1
= A-B
m
i
n
j
ji
ba
1
1
1
, С
i,n+1
= 0
115. Объясните смысл переменной x
in
в транспортной модели, если n-ный потребитель – фиктивный.
х
in
– кол-во продукта, кот.i
-ый
поставщик не везет n потребителю, т.к.у него нет запасов
116. Объясните смысл переменной x
mj
,если m-ный потребитель – фиктивный.
x
mj
– кол-во продукта, кот j-ый
поставщик недополучает
117. Дайте формулировку признака оптимальности плана перевозок.
x*=(x
*
ij
)
n
j
m
i 11
,
- баз-й невырожденный план перевозок.
пусть U
i
и V
j
таковы, что x
ij
>0 V
j
-U
i
=C
ij
,
для любого x
ij
V
j
-U
i
≤C
ij
, =>x* -оптим. план перевозок.
Uи V
оптимальный план двойственной задачи
118. Сколько ограничений – равенств содержится в модели транспортной задачи.
m+n
119. Сколько неизвестных содержится в каждом ограничении двойственной модели к транспортной.
2
120. Сформулируйте теорему равновесия для пары двоственных задач, одна из которых – транспортная задача.
Х= (x
ij
) i=1..m, j=1…n - план прямой задачи.
Y=(U
1
…U
m
,V
1
…V
n
) – план двойственной задачи,
чтобы Х и У- оптим. Необх.выполнение след.усл.
1. x
ij
(V
j
-U
j
-C
j
)=0 i=1…m, j=1…n.
2.Ui
0)(
1
i
n
j
ij
ax
Vj
0)(
1
j
m
i
ij
bx
121. Какая задача решается методом северо-западного угла.
Транспортная задача.
122. Какая задача решается методом минимальной стоимости.
Транспортная задача.
123. Для чего при решении транспортной задачи используется метод потенциалов.
Для нахождения оптимального плана
124. Какие компоненты плана перевозок подлежат пересчету в результате применения метода потенциалов.
Пересчету подлежат следующие компоненты: первой выбирается пустая перевозка, такая что Δ
ij
=Cij-(Vj-Ui), а остальными компонентами являются
те, которые образуют цикл, начиная с первой определенной.
125. Вычислите потенциалы для какого-нибудь плана следующей транспортной задачи:
B1 B2 U1
A1
5
6
2
0 U1=0
A2
12
3
10
12 U2=-7
Vj V1=5 V2=3
V1-U1=5 U1=0 V1=5, U2=-7, V2=3 – это и есть потенциалы
V1-U2=12
V2-U2=10
126. При каких значениях С
12
следующий план транспортной задачи оптимален:
А =23 / В =23 b
1
= 10 b
2
= 13
а
1
= 7 9 / 7 ? / -
а
2
= 16 8 / 3 4 / 13
B1 B2
A1
9
7
x
0
A2
8
3
4
13
V1-U1=9
V1-U2=8
V2-U2=14
U1=0, V1=9, U2=1, U2=15, V2-U1C12, C1215-0, C1215
127. Что является исходными данными задачи о назначениях.
m кандидатов на n должностей. Матрица затрат назначения t= (tij) –( затраты времени на то чтобы i-го кандидата подготовить на j-ю должность
(i,j=1,…,n)). Необходимо минимизировать затраты на это назначение.
128. Каков смысл неизвестных в модели ЛП, соответствующей задаче о назначениях.
X=(x
ij
) может принимать значения 1, если на j-ю должность назначен i-й кандидат, и 0 в противном случае.
129. Дайте содержательную интерпретацию ограничения
6
a
1
= 6
a
2
=15
b
1
=9
b
2
=12
c
11
=5
c
22
=10
c
21
=12
c
12
=2
j
ij
x 1
задачи о назначениях
Таким ограничением описывается условие назначения на каждую должность одного (i-го) кандидата.
130. Дайте содержательную интерпретацию ограничения
задачи о назначениях
Каждая работа может быть выполнена только одним кандидатом
131. Напишите целевую функцию экономико-математической модели задачи о назначениях.
n
i
n
j
ijij
xtxС
1 1
min)(
132. Дайте матричную интерпретацию плана назначения.
i, j =1..n
133.Что общего между моделями транспортной задачи и задачи о назначениях?
1. кандидаты приблизит-но равны пост-кам
2. вакансии приблизи-но = потребителям
3. Сij в зад-чах о назнач-ях – это затраты на назнач-е i-го кандидата на j-тую долж-ть, а в трансп зад-че – затараты на перевозку ед-цы продукции
от пост-ка Аi к потр-лю Вj
4. Начальный план задачи о назнач-ях м. считать начальным планом трансп-й задачи
5. Если план не оптимален, то он неоптимален для обеих задач, и тогда для обеих задач м. применить метод потенциалов
6. Полная аналогия м/у матричной моделью тр. з-чи и з-чи о назгач-ях
134. Чем отличаются модели транспортной задачи и задачи о назначениях.
В задаче о назначениях переменная м. принимать значения 0 и 1, а в транспортной любое неотрицательное.
135. Дайте содержательную интерпретацию задачи о назначениях, если ее матрица затрат – прямоугольная.
Количество кандидатов не соответствует количеству должностей.
136. В чем смысл редукции матрицы затрат.
Необходимо получить новую матрицу затрат С
R
, у кот. в каждой строке, в каждом столбце есть, по крайней мере, один нулевой элемент.
137. Что является характерной особенностью редуцированной матрицы затрат.
(Квадратная.) Содержит в каждой строке, в каждом столбце есть, по крайней мере, один нулевой элемент.
138. Каково минимальное число нулевых элементов в редуцированной матрице.
Равно порядку матрицы.
139. Уточните смысл выражения «нули матрицы находятся в общем положении».
нули матрицы находятся в общем положении, если наименьшее число горизонт. или вертик. линий, вычеркивающих все нули из С
R
, равно порядку
матрицы С.(n)
140. Находятся ли в общем положении нули следующей матрицы:…………….
кол-во линий равно n
141. Проверка того, что нули матрицы затрат находятся в общем положении играет ключевую роль в решении задачи о назначениях. Почему?
Если нули в общем положении, то существует назначение с нулевыми затратами. Если нули не в общем положении, то плана назначений с 0-ми
затратами нет.
142. Какие преобразования над матрицей затрат являются допустимыми.
C’
ij
=C
ij
-
i
; где
i
=min(C
ij
), i=1…n
C’=(C
ij
)’C
1
; C
1
ij
=C’
ij
-B
j,
где B
j
=min(C’
ij
), j=1…n
143. Пусть нули редуцированной матрицы не находятся в общем положении. Опишите следующий шаг венгерского метода.
С помощью разрешенных преобразований привести нули в общее положение
1. выбираем C
R
ij
=min из невычеркнутых строк
2. вычитаем этот элемент из всех элементов C
R
ij
3. ко всем эл-там, которые нах-ся в невычеркнутых строках и столбцах добавим min C
R
ij
145. Методы решения МКЗ:
1. метод свертывания критериев
Суть метода: имеющееся множество критериев сводится к одному скалярному критерию, отражающему комбинированную цель системы.
Каждому критерию f
j
(x) приписываются весовые коэффициенты α
j
, определяющие предпочтения ЛПР.
Nj
j
N
j
j
,1,0,1
1
.
Свертка критериев представляет собой функцию следующего вида:
xfxF
j
N
j
j
1
В результате решение многокритериальной задачи сводится к решению следующей задачи:
0
max
1
x
bAx
xfxF
j
N
j
j
2. метод главного критерия
Суть метода: из множества имеющихся критериев выбирается наиболее важный для ЛПР, а остальные записываются в виде
дополнительных ограничений.
Пусть f
1
(x) – главный критерий, тогда решение многокритериальной задачи заменяется решением следующей задачи:
7
i
ij
x 1
0001
0010
1000
0100
0
1
x
x
ij
0
,2,
max
1
x
bAx
Njdxf
xf
jj
3. модифицированный метод идеальной точки
Суть метода: в множестве допустимых планов отыскивается точка, которая отражается в достижимое множество в точку, расстояние от
которой до идеальной точки F* минимально по всем критериям.
Dx
Nj
jj
xfF
min*max
1
- критерий равномерного сжатия.
Для приведения этого критерия к линейному виду, введем новую переменную:
Nj
jj
xfF
1
*max
.
Решение многокритериальной задачи сводится к нахождению оптимального плана следующей задачи:
0
0
,1,*
min
x
bAx
NjxfF
jj
4. метод последовательных уступок
Суть метода: все критерии ранжируются по степени важности для ЛПР. Последовательно решаются однокритериальные задачи в
установленном порядке с добавлением в каждую последующую задачу дополнительного ограничения на предыдущий критерий.
Для последнего по важности критерия задача будет выглядеть следующим образом:
0
1,1,*
max
x
bAx
NjhFxf
xf
jjj
N
5. метод группировки целевых функций
Суть метода: множество критериев, значения которых предварительно вычислены на некотором эффективном плане x
0
, разбивается на
три группы:
- значения критериев могут быть уменьшены по сравнению со значениями, полученными на x
0
(G
1
);
- значения критериев желательно увеличить (G
2
);
- значения критериев хотелось бы оставить на прежнем уровне (G
3
).
Далее отыскивается план уже в новой системе ограничений, который позволяет максимально увеличить значения критериев второй
группы.
0
0
,
,)(
,
max
3
0
2
0
1
0
s
x
Gfxfxf
Gfsxfxf
Gfxfxfp
bAx
s
mmm
lll
kkkk
8