- •1. Объясните термин «Линейное программирование».
- •2. Перечислите основные предпосылки теории лп.
- •4 7. Сформулируйте первую теорему двойственности (терему разрешимости).
- •48. Сформулируйте теорему о планах двойственных задач.
- •49. Приведите формулировку теоремы равновесия.
- •Нет, хотя в принципе может, но это бывает очень редко
- •Блок вопросов по теме «Двухсеторная модель экономики «Производство - рынок»
1. Объясните термин «Линейное программирование».
Наука о методах исследования и отыскании макс. и мин. лин. функций, на неизвестные которых наложены лин. ограничения, т. о. ЗЛП относится к задачам на условный экстремум функции.
2. Перечислите основные предпосылки теории лп.
1939 – Канторович написал труд «Мат. Методы организации и планирования пр-ва», где впервые сформулир-л задачу ЛП и привел алгоритм реш-я, попытался оптимизир-ть пр-ный процесс, т.е. впервые пытался понять сколько, чего и по какой технологии произв-ть, в 1941 Хичкок и 1947 Купманс независимо др. от др-га сформулир-ли трансп-ную задачу, 1947 – Данциг придумал алгоритм с/метода, 1975 – Канторович и Купманс получили Ноб-ю премию за создания алгоритма ЛП.
3. Назовите основные составляющие экономико-математической модели ЛП.
Система функц – технологич лин-х огранич-ний: равенств, неравенств
i =1…m
Система логических ограничений xj>=0, j = 1…n
Наличие лин-ной ф-ции, которая максимизир-ся или минимизир-ся (целевая ф-ция).
C (x) max (min)
4. Какая модель ЛП называется стандартной, запишите эту модель в векторной форме.
Ax<=b: x>=0, C(x)=(C,x)=>max
5 . Запишите стандартную модель ЛП в алгебраической (подробной) форме.
a11, x1+a12x2+…a1nxn <=b1
………………………………..
am1x1+am2x2+…..amnxn<=bm
x1,………xn>=0
C(x) = C1 x1+C2x2+…….Cnxn =>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 11x1+a12x2+…a1nxn=b1
………………………………..
am1x1+am2x2+…..amnxn=bm
x1,………xn>=0
C(x) = C1 x1+C2x2+…….Cnxn =>max
12. Дайте определение допустимого множества стандартной задачи и его геометрическую интерпретацию.
D = { X=( x1,…xn: Ax<=b; x>=О} – допустимое мн-во станд-тной задачи + рис-к!!!
13. Каково соотношение между числом неизвестных и ограничений в канонической модели ЛП, аргументируйте ответ.
m<n. Если m>n – с-ма ур-ний Ax=b не имеет смысла, m=n – с-ма ур-ний имеет единств-е реш-е, след-но нет смысла искать max C(x)
14. Для чего в линейном программировании используются дополнительные переменные.
Для преобразования стандартной ЗЛП в каноническую.
15. Дайте содержательную интерпретацию дополнительных переменных.
Неиспользованное количество i-го ресурса при реализации производственного плана.
16. Какова роль градиента функции в графическом решении задачи ЛП.
Указывает скорость и направление роста значения ц. ф. при изменении переменных.
17. Может ли иметь решение задача ЛП, если ее допустимое множество неограниченно, дайте графическую интерпретацию ответа.
Нет.
С(х)>>M, т.е. С(х) неограниченна на Д + рис-к!!!
18. Приведенная форма системы линейных уравнений и ее роль в решении задачи ЛП.
Общая форма записи приведенной формы ур-ний:
W – множество свободных индексов
- множество базисных индексов.
Привед-я форма (выбор базисных переменных) приводит либо к нахождению базисного плана (вырожд-го или невырож-го) или к такому решению, которое не является планом.
19. Определение носителя допустимого плана.
X D, xj>=0, j=1…n, (x)={j: xj>0, j=1,…,n} - носитель допустимого плана.
20. Как определяется носитель псевдоплана.
Х=(x1,…,xn) - псевдоплан, (x)={i: xi≠0, i=1,…,n} - носитель псевдоплана.
21. Что общего между планом и псевдопланом канонической модели ЛП.
Компоненты плана удовлетворяют ограничениям канонической задачи Ax=b.
22. Чем отличаются базисный план и псевдоплан.
Базисный план Х* =(x*1,…,x*n) D – допустимый план канонической задачи Ах = b, x>=0, C(x)=>max, /σ*/<=m – кол-во ненулевых компонент. Компоненты базисного плана xj>=0. Компоненты псевдоплана м.б. любые, в том числе и отрицательные.
23. Смысл элементов технологической матрицы и многопродуктовой модели.
aij - кол-во i-го ресурса для производства j-го продукта (i=1,…,m; j=1,…,n).
24. Смысл элементов технологической матрицы в однопродуктовой модели производственного планирования.
aij - кол-во i-го ресурса для производства единицы продукта по технологии j (i=1,…,m; j=1,…,n).
25. Определение базисного плана.
X=(x1,…,xn) D – допустимый план канонической задачи, Ax=b, x>=0, (C,x)=>max. Если //<=m – кол-во положит-ных компонент плана X => X – базисный план.
26. Напишите формулу для вычисления двойственных оценок, объясните смысл входящих в эту формулу величин.
или Δj = (Сσ,Aj) - Сj, где Сσ – коэффициент при базисных переменных в ц. ф-ции, Аj - j-ый столбец с/т, Сj - коэф. ц. ф. при j-ой неизвестной.
y*=(A-1)C, C - коэффициент ц.ф., A-1 - матрица, составленная из столбцов 1-вой с-мы и столбцов, составленных из базисных векторов последней с/таблицы
27. Сформулируйте признак оптимальности базисного плана.
A x=b
x>=0 (1) Axb=>A’x=b’ – приведенная форма
c(x)=>max
X0 = (x01,…,x0n) – базисный план (1). Если Δj= то X0 – оптимальный план.
28. Что такое суперпсевдоплан.
Ax=b
x>=0 (1)
c(x)=>max
Х*=(x*1,…,x*n) – супер псевдоплан, если АХ* = b, /σ*/<=m, σ(x*)={i: x*i≠0, i=1,…,n} - носитель этого псевдоплана, и соответствующие двойственные оценки Δj= .
29. Сколько положительных компонент может быть в базисном плане.
Положительных компонент в базисном плане м. б. < m (число уравнений).
30. Почему не могут ровняться нулю все двойственные оценки, соответствующие дополнительным переменным оптимального плана.
Если все двойственные оценки Δj=0, то все ресурсы избыточны, а этого не может быть (AтyС y=0 => C=0 – ничего не производим).
31. Как должна выглядеть с/таблица перед применением с/метода.
В последней строке среди Δj, j=1…..n, д. б. Δj<0, а в соотв. min Δj столбце должно быть aik>0; в столбце А0 все числа ai0 должны быть >0.
32. Как должна выглядеть с/таблица перед применением двойственного с/метода.
В столбце А0 д. б. хотя бы одно отриц. число ai0<0 (т.е. в А0 записан суперпсевдоплан) и в последн. строке Δj>0.
33. Что означает факт невозможности преобразование с/таблицы с помощью алгоритма с/метода.
Найден оптимальный план, 2.) Д – неограниченный многогранник, т.е. С(х) неограничена на Д.
34. Что означает факт невозможности преобразование с/таблицы с помощью алгоритма двойственного с/метода.
а) найден оптимальный план. б) D =
35. В каком случае преобразование с/таблицы с помощью с/метода оказываектся невозможным.
Хk – базисный план, полученный с/методом на k-той итерации Δk = minΔj<0, j = 1…n, если min aik<=0, i σk => ЗЛП неразрешима.
36. В каком случае преобразование с/таблицы с помощью двойственного с/метода оказывается невозможным.
Х0 – суперпсевдоплан, х0r – отрицательная компонента Х0 , х0r<0, r σ (х0r=aro). Если все arj>=0, j=1….n => ЗЛП неразрешима.
37. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется с/метод.
Х – базисный план, Δk = minΔj<0, j = 1…n, k - результат 1-го шага алгоритма, aro/ark = min(aio/aik), aik>0, i σ, r - результат 2-го шага,=> ark - ведущий элемент
38. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется двойственный с/метод.
X – суперпсевдоплан. aro=min(aio), i σ, r – результат первого шага алгоритма, r σ, aro<0, ark=max(Δj/arj), arj <0, j=1...n, ark<0 kσ, т.к. arj <0
39. Верно ли, что двойственная задача к стандартной имеет канонический вид, а двойственная задача к канонической имеет стандартный вид.
Нет.
4 0. Напишите двойственную задачу к следующей задаче ЛП: AX=B, X>=0, C(X) MIN
АтY-C
B(y)=>min
4 1. Напишите двойственную задачу к следующей задаче ЛП: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?
Такая ситуация невозможна по теореме об оптимальных планах.