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

 

Сумм стоимость ресурсов на j изделие

51. Дайте экономическую интерпретацию равенства У (b – AX)=0

 

 

 

 

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

1. Номенклатура (состав) выпускаемых продуктов, которые входят в план

производства;

2. Перечень дефицитных и избыточных ресурсов;
3. В задачах производ-го планир-я встречаются ограничения такого вида: d_i<=x_i<=D_i, d_i>=0, d_i<D_i

x_i³d_i

x_i£D_i

Отсюда -x_i£-d_i, x_i£D_i т.е. указся продукты, которые входят в план пр-ва с указанием, является ли это кол-во = d_i, = D_i или x_i ( d_i, D_i).

53. Каким образом формализуется  понятие структуры плана в  теории ЛП.

Математическим эквивалентом структуры плана является носитель плана.

54. Сколько оптимальных  базисных планов с одинаковой  структурой может быть у задачи  ЛП.

Много.

55. Сколько интервалов  устойчивости ассоциируется с  оптимальным планом.

Для каждого вида ресурса  может быть свой интервал устойчивости.

56. Дайте определение интервала устойчивости.

Интервал изменения  количества ресурсов, кот. не влияет на структуру opt плана (Δb_k < Δbn < Δb_k )

57. В чем практическое  значение интервала устойчивости.

Определяет интервал изменения ресурсов, не влияющий на структуру opt плана.

58. Сколько интервалов оптимальности ассоциируется с оптимальным планом.

Для каждого коэф. ц.ф. свой план.

59. Дайте определение  интервала оптимальности.

Если для каждого C_jÎ[C_j^min , C_j^max] оптимальный план ЗЛП неопределен, то данный интервал наз-ся интервалом оптимальности.

60. В чем практическое  значение интервала оптимальности.

Определяет интервал изменения коэффициентов целевой  функции - цены (С_k), кот. не повлияет (не изменит) на opt план (изменится лишь доход С(х))

61. Какие ресурсы в  теории ЛП называются дефицитными, а какие – избыточными.

x_n+i, i=1…m, если x_n+i = 0 => i-тый ресурс - дефицитный, x_n+i>0, => i-тый ресурс - избыточный

62. Как вычисляется  нижняя граница интервала устойчивости  для избыточного ресурса (а  верхняя грница?).

Δb_k/ниж=-x*_n+k, Δb_k/верх=∞; [b_k+ Δb_k/ниж; b_k+Δb_k/верх] – интервал устойчивости

63. Как вычисляется  верхняя граница интервала оптимальности  для коэффициента при небазисной  переменной оптимального плана  (а нижняя?).

 

64. Дайте качественную экономическую хар-к двойственных оценок.

Двойственные оценки показывают во сколько раз изменится  значение ц. ф. в результате изменения i-того ресурса на единицу.

65. Дайте количественную  хар-ку двойственных оценок как  меры дефицитности ресурсов.

Δ_n+k=0 => k-й ресурс избыточен

Δ_n+k>0 => k-й ресурс дефицитен

66. Верно ли, что интервалы  разрешимости модели ЛП с параметром  и двойственно к ней совпадают,  ответ обоснуйте.

Верно, это следует  из 1-й теоремы двойственности.

67. Дайте определение  решающей функции для модели ЛП с параметром в ограничениях.

φ(t), где tЄ(-∞;+∞), φ(t)=maxC(x,t)=C(x*(t)), xЄD(t)

68. Дайте определение  решающей функции для модели  ЛП с параметром в целевой  функции.

y(t), tЄ(-∞;+∞),y(t)=maxC(x,t)=C(x*,t), xЄD

69. Что необходимо сделать, чтобы вычислить значение решающей функции в некоторой фиксированной точке.

1. Необходимо конкретное значение параметра t
2. Решить ЗЛП
3. Найти значение целевой ф-ции на оптимальном плане

70. Перечислите св-ва  решающей функции в модели  ЛП с параметром в ограничениях.

Непрерывна, ?кус.-лин?. (линейна на любом интервале устойчивости), вогнута

71. Перечислите св-ва  решающей функции в модели  с параметром в целевой функции.

Непрерывна, кус. лин., выпукла

72. Что значит решить  задачу линейного программирования  с параметром в ограничениях.

1. Найти интервал разрешимости Т
2. Найти разбиение Т на интервалы устойчивости
3. Найти оптимальный план для всех tЄТ

73. Укажите область  определения решающей функции.

Этот интервал такой, что при всех t из этого интервала решающая ф-ция разрешима φ(t) t Є T

74. Чем отличается обычная  с/таблица от с/таблицы, предназначенной  для решения задачи ЛП с  параметром в целвой функции.

В столбце для вычисления коэф-тов цел. ф-и при базис.перем. указ. знач. параметра t в строке, где вычисляются двойств.оценки Δj(t)= Δj’+ Δj’’t. C(x*t)=Cj’+C’’t

 

 

75. Что значит решить  задачу ЛП с параметром в  целевой функции.

1. Найти интервал разрешимости
2. Найти разбиение Т на интервалы оптимальности
3. Найти оптимальный план для всех tЄТ

76. Чем отличается процесс  решения многокритериальной задачи ЛП от решения обычной задачи ЛП.

При решении ЗМЛО находится 1 или несколько допустимых планов, удовлетворяющих, по мнению ЛПР, т.е. в  решение включается субъектив. фактор мнения ЛПР

77. Дайте определение  эффективного (Парето-оптимального) решения.

Х* Є D – эффективное решение, если не существует yЄD такого, что f(х*)≤f(y), то х*- парето-оптимальный план.

78. Сколько Парето-оптимальных  планов может иметь многокритериальная  задача.

много

79. Что такое достижимое  множество.

x=(х₁… х_n) ЄD. f(x)=(f₁(x)…f_n(x) хар-ка качества доп.плана Є R_k . F={y=f(x),xЄD}, FC R_k

80. Какова геометрическя  интерпретация допустимого множества.

F- достижимое  мн-во, Д – допустимое мн-во+ рис-к!!!

81. Что такое линейная свертка критериев.

-линейная свертка критериев  f₁ f₂….f_k.

82. Как выбираются коэффициенты  свертки (коэффициенты важности  критериев).

Коэф-т важности α_k выбирает ЛПР. Чем больше важен критерий с № k для ЛПР, тем больше α_k

87. В чем смысл нормировки критериев.

Нормировка критериев  позволяет получить критерии, которые  измеряются числами одного порядка. После того, как проведена нормировка и рассматривается нормир.ф-я  свертки f^н(х), выбор α_k действительно соответствует важности критерия с точки зрения ЛПР

88. Напишите формулу  нормировки критериев.

, где f_К^min(max)= min(max)f_К(x), X^КЄD

89. Дайте определение  «идеальной» точки.

Идеальная точка f*_K(x)=(f*_1…. f*_K) C R_K , f*_K =max f_K(x), x Є D

90. Сколько компонент содержит «идеальная» точка.

Столько, сколько критериев  в ЗЛМО

91. Является ли «идеальная»  точка планом задачи ЛП.

Нет

 

 

 

 

 

92. Принадлежит ли «идеальная»  точка достижимому множеству.

Нет, хотя в принципе может, но это бывает очень редко 

93. Объясните сущность метода «идеальной» точки.

f*=(f₁^max… f_К^max ) Є R_К – идеальная точка. Не существует х Є D, f(x)=f*, то f* не принадлежит F. |f(x*)-f*|_F→min – это план при котором значение критерия отстоит как можно меньше от идеальной точки

94. Какая задача решается методом последовательных уступок.

Задача максимизации значения критерия, значение которого не достаточно велико для ЛПР

95. Какое допущение  относительно критериев необходимо  для применения метода последовательных  уступок.

Должны быть упорядочены  по степени важности

96. Для решения, каких  задач применяется целевое программирование.

Для построения математических моделей многокритериальной оптимизации

97. В чем выражаются  структурные особенности модели  целевого программирования.

1. |U_k - C_k(x)| =>min (max),

2. U_R -

3.непротиворечивость

98. Что такое «горизонт  планирования».

U_k – заранее определенный ур-нь, которого д. достигнуть k-тый критерий.

99. Кто и как определяет  «горизонты планирования».

ЛПР по своему усмотрению

100. В чем смысл целевой функции в модели целевого программирования.

В min штрафов за отклонение от горизонта планирования.

101. Является ли модель  целевого программирования канонической  моделью ЛП.

Да

102. Что является исходными  данными в транспортной задаче.

Потребности в пунктах назначения b₁… b_m , запасы в пунктах отправления a₁…a_n, кол-во поставок, кол-во потребителей матрица стоимости перевозок m=n.

103. В чем смысл уравнения  баланса А = В.

 все потребности  удовлетворены, все запасы из  пунктов отправления д.б. доставлены  потребителям.

104. В чем содержательный смысл  неизвестных в транспортной модели.

x_ij≥0 – кол-во товара, кот везет i-й поставщик j-му потребителю

105. Что такое план  транспортной задачи.

X= (x_ij) _i=1^m  _j=1ⁿ 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

	b1	..	bm
а1	C11	..	C1n
.	. . . .	..	…
аm	Cm1	..	Cmn

109. Что значит «план  порождает цикл».

В матрице существует замкнутый маршрут из горизонт. и  вертик. участков (возможно самопересечение) с поворотом на 90ْ в положит. перевозках.

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   , С_m+1,j = 0 (фиктивное положение перевозки).

114. Объясните  построение матричной модели, если  в транспортной задаче предложение  превышает спрос.

т.е.

вводим фиктивного потребителя  В_n+1, b_n+1 = A-B  , С_i,n+1= 0

115. Объясните  смысл переменной x_in в транспортной модели, если n-ный потребитель – фиктивный.

х_in – кол-во продукта, кот.i -ый поставщик не везет n потребителю, т.к.у него нет запасов

116. Объясните смысл переменной x_mj ,если m-ный потребитель – фиктивный.