Шпаргалка по "Программированию"

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₁₁x₁+a₁₂x₂+…a_1nx_n <=b₁

………………………………..

a_m1x₁+a_m2x₂+…..a_mnx_n<=b_m

x_1,………x_n>=0

C(x) = C₁ x₁+C₂x₂+…….C_nx_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₁₁x₁+a₁₂x₂+…a_1nx_n=b₁

………………………………..

a_m1x₁+a_m2x₂+…..a_mnx_n=b_m

x_1,………x_n>=0

C(x) = C₁ x₁+C₂x₂+…….C_nx_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. Приведенная форма  системы линейных уравнений и  ее роль в решении задачи  ЛП.

Общая форма записи приведенной  формы ур-ний:

W – множество свободных индексов

d- множество базисных индексов.

Привед-я форма (выбор  базисных переменных) приводит либо к  нахождению базисного плана (вырожд-го или невырож-го) или к такому решению, которое не является планом.

19. Определение носителя  допустимого плана.

X D, xj>=0, j=1…n, d(x)={j: xj>0, j=1,…,n} - носитель допустимого плана.

20. Как определяется  носитель псевдоплана.

Х=(x₁,…,x_n) - псевдоплан, d(x)={i: xi≠0, i=1,…,n} - носитель псевдоплана.

21. Что общего между  планом и псевдопланом канонической модели ЛП.

Компоненты плана  удовлетворяют ограничениям канонической задачи Ax=b.

22. Чем отличаются базисный  план и псевдоплан.

Базисный план Х* =(x*₁,…,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. Определение базисного  плана.

X=(x₁,…,x_n) D – допустимый план канонической задачи, Ax=b, x>=0, (C,x)=>max. Если /d/<=m – кол-во положит-ных компонент плана X => X – базисный план.

26. Напишите формулу  для вычисления двойственных  оценок, объясните смысл входящих в эту формулу величин.

1. или Δj = (С_σ,Aj) - Сj, где С_σ – коэффициент при базисных переменных в ц. ф-ции, Аj – j-й столбец с/т ?системы?, Сj - коэф. ц. ф. при j-ой неизвестной.
2. y*=(A^-1_s)*C_s, C_s - коэффициент ц.ф., A^-1_s - матрица, составленная из столбцов 1-вой с-мы и столбцов, составленных из базисных векторов последней с/таблицы

27. Сформулируйте признак  оптимальности базисного плана.

Ax=b

x>=0                  (1)  Ax¹b=>A’x=b’ – приведенная форма

c(x)=>max

X⁰ = (x⁰₁,…,x⁰_n) – базисный план (1).

Если Δj= то X⁰ – оптимальный план.

28. Что такое суперпсевдоплан.

Ax=b

x>=0                  (1)

c(x)=>max

Х*=(x*₁,…,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 столбце должно быть a_ik>0; в столбце А₀ все числа a_i0 должны быть >0.

32. Как должна выглядеть  с/таблица перед применением двойственного  с/метода.

В столбце А₀ д. б. хотя бы одно отриц. число a_i0<0 (т.е. в А₀ записан суперпсевдоплан) и в последн. строке Δj>0.

33. Что означает факт  невозможности преобразование с/таблицы  с помощью алгоритма с/метода.

1. Найден оптимальный план, 2.) Д – неограниченный многогранник, т.е. С(х) неограничена на Д.

34. Что означает факт невозможности преобразование с/таблицы с помощью алгоритма двойственного с/метода.

а) найден оптимальный  план. б) D = Æ

35. В каком случае  преобразование с/таблицы с помощью  с/метода оказываектся невозможным.

Х^k – базисный план, полученный с/методом на k-той итерации Δk = minΔj<0, j = 1…n, если min a_ik<=0, i σ_k => ЗЛП неразрешима.

36. В каком случае  преобразование с/таблицы с помощью  двойственного с/метода оказывается  невозможным.

Х⁰ – суперпсевдоплан, х⁰_r – отрицательная компонента Х⁰ , х⁰_r<0, r σ (х⁰_r=a_ro). Если все a_rj>=0, j=1….n => ЗЛП неразрешима.

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

Y³0

B(y)=>max

42. Сколько ограничений  и неизвестных в двойственной  задаче.

Ограничений столько, сколько  переменных в прямой (исходной) задаче (n).

Неизвестных столько, сколько ограничений  в прямой (исходной) задаче (m).

43. Сколько ограничений-равенств  в прямой задаче ЛП, если все переменные двойственной задачи неотрицательны.

Ограничений – равенств в прямой задаче нет.

44. Известен план прямой задачи  и план двойственно задачи. Что  можно сказать о разрешимости  этих задач; аргументируйте ответ.

Если одна из пары двойственных задач разрешима, то разрешима и другая (имеет оптимальный план). Причем Х* - оптимальный план , Y* - оптимальный план => C(X*)=B(Y*)

45. Пусть Х – план  прямой задачи, а У – план  двойственной задачи. Что следует  из равенства С(Х) = В(Y)?

Эти планы – оптимальны.

46. Пусть выполняется  равенство С(Х) = В(Y), причем известно, что Х – неоптимальный план прямо задачи; что можно сказать о векторе Y?

Такая ситуация невозможна по теореме  об оптимальных планах.

47. Сформулируйте первую  теорему двойственности (терему разрешимости).

Ax£b

x³0                      (1)

(C,x)=>max

А^тY³C

Y³0                      (2)

(B,Y)=>min

Если одна из задач дв. пары разрешима, то др. задача разрешима, причем значение целевых функций на оптимальных  планах прямой и двойственной задач совпадают, если Х* - оптимальный план (1), Y* - оптимальный план (2), то С(Х*)=С(Y*).

Если С(х) одной из пары двойственных задач неограниченна на Д, то Д  другой задачи – пусто.

48. Сформулируйте теорему  о планах двойственных задач.

Ax£b

x³0                      (1)

(C,x)=>max

А^тY³C

Y³0                      (2)

(B,Y)=>min

D₁ – допустимое мн-во (1), D₂ - допустимое мн-во (2)

Если X D₁, Y D₂ => C(X)<В(Y).

49. Приведите формулировку  теоремы равновесия.

Чтобы допустимые планы задач (1) и (2) были оптимальны необходимо и достаточно, чтобы выполнялись следующие соотношения: х* и y* - opt планы задач дв. пары ó x_j* [ ] = 0, j=1…..n, y*_j [ ] = 0, i=1….m.

 

 

 

 

50. Дайте экономическую интерпретацию равенства Х(А^т – С) =

C_j – цена j-го товара