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

x_mj – кол-во продукта, кот j-ый  поставщик недополучает

117. Дайте формулировку  признака оптимальности плана  перевозок.

x*=(x^*_ij) - баз-й невырожденный план перевозок.

пусть 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₁…U_m,V₁…V_n) – план двойственной задачи,

чтобы Х и У- оптим. Необх.выполнение след.усл.

1. x_ij (V_j-U_j-C_j)=0 i=1…m, j=1…n.

2.Ui  

Vj

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. При каких  значениях С₁₂ следующий план транспортной задачи оптимален:

А =23 /В =23	b1 = 10	b2 = 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-U1£C12, C12³15-0, C12³15

127. Что является исходными  данными задачи о назначениях.

m кандидатов на n должностей. Матрица затрат назначения С= (Сij) –( затраты на то чтобы  i-го кандидата подготовить на j-ю должность (i,j=1,…,n)). Необходимо  минимизировать затраты на это  назначение.

128. Каков смысл неизвестных  в модели ЛП, соответствующей задаче о назначениях.

X=(x_ij)  может принимать значения 1, если  на j-ю должность назначен i-й кандидат, и 0 в противном случае.

129. Дайте содержательную  интерпретацию ограничения 

задачи о назначениях.

Таким ограничением описывается условие назначения на каждую должность одного (i-го) кандидата.

130. Дайте содержательную  интерпретацию ограничения 

задачи о  назначениях

Каждая работа может  быть выполнена только одним кандидатом

131. Напишите целевую  функцию экономико-математической  модели задачи о назначениях.

132. Дайте матричную  интерпретацию плана назначения.

должно удовлетворять  j=1…n   x_ij = (0,1)

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-a_i; где a_i=min(C_ij), i=1…n

C’=(C_ij)’®C₁; C¹_ij =C’_ij -B_j, где B_j=min(C’_ij), j=1…n

143. Пусть нули редуцированной матрицы не находятся в общем положении. Опишите следующий шаг венгерского метода.

С помощью разрешенных  преобразований привести нули в общее  положение

1. выбираем C^R_ij=1 из невычеркнутых строк
2. вычитаем этот элемент из всех элементов C^R_ij
3. ко всем эл-там, которые нах-ся в невычеркнутых строках и столбцах добавим min C^R_ij

 

 

 

 

 

 

 

 

 

 

Блок вопросов по теме «Двухсеторная модель экономики  «Производство - рынок»

144. Дайте содержательную интерпретацию  элементов a_ij j-того столбца технологической матрицы А (как положительных, так и отрицательных).

a_ij j-того столбца

i=1  a₁₁ a₁₂…a_1n

………………….

i=m  a_m1 a_m2…a_mn

        j=1   j=2….j=n

Пусть j=1

            a_i1>0

a_i1=

           -a_i1<0

a_i1>0 – произ-ся произ-вом i-e продукты в количестве a_i1 посредством 1-вой технологии с ед. инт-ю

-a_i1<0 - протр-ся произ-вом i-e продукты в количестве /a_i1/ при использовании 1-вой технологии с ед. инт-ю

145. Дайте содержательную интерпретацию  элементов a_ij i -той строки технологической матрицы А (как положительных, так и отрицательных).

i a₁₁ a₁₂…a_1n

………………….

a_m1 a_m2…a_mn                                            

Пусть i=1

a_1j =    (система)    a_1j >0 – произ-ся  произ-вом 1-ый продукт в количестве a_1j посредством j-ых технологии с ед. инт-ю

             - a_1j <0 - протр-ся  произ-вом 1-ый продукт в количестве / a_1j / при использовании j-ых технологии с ед. инт-ю

146. Что означает тот факт, что  все элементы некоторой строки  технологической матрицы А положительны или отрицательны.

a_ij <0 j = 1….n => i-ый продукт является “чистым ресурсом”, т.е. все отрасли его потребляют

a_ij >0 j = 1….n => i-ый продукт произ-тся всеми отраслями

147. Каков содержательный смысл  компонент векторов b = (b₁, b₂, …, b_m) и c = (c₁, c₂,….., c_n) в задаче “производство – рынок”.

b = (b₁, b₂, …, b_m) => b_i =  (с-ма)    b_i >0 – кол-во i-го продукта, кот-ое явл-тся минимально необходимым для выживания экономики

 b_i <0 – i-ый продукт явл-тся ресурсом / b_i / - запас этого рес-са в секторе произ-ва

c = (c₁, c₂,….., c_n) – затраты, связанные с использованием j-ой технологии

148. Запишите  платежную функцию L (x,y) в двух  различных формах.

L (x,y) = (Y, Ax-b)-(C,X)

L (x,y) = (A^т Y-C,X)-(b,y)

149. Каков  смысл аргументов х и у платежной  функции.

X – производственный план производства

Y – цены на ресурсы, продукты

 

 

 

 

 

 

150. С помощью  платежной функции запишите математическую  модель задачи, в решении которой  заинтересован сектор “рынок”.

y(y)=maxL(x,y)    miny(y)=min(max(L(x,y))) – рынок

        X³0               Y³0          X³0

L(x,y) – максимальная эффективность  производства

151. С помощью платежной функции  запишите математическую модель  задачи, в решении которой заинтересован  сектор “производство”.

j(x)= minL(x,y)    maxj(x)=max(min(L(x,y))) – произ-во

         Y³0                  X³0        Y³0 L (x,y) – min гарантированный доход произ-ва

152. Какая модель  ЛП используется сектором “производство”  для нахождения оптимального  производственного плана.

Ax>=b

x>=O           производство

C(x)=>min

153. Какая модель ЛП используется  сектором “рынок” для нахождения  оптимальных цен.

A^тy<=C

Y>=0                       рынок 

B(y)=(b,y)=>min

154. Что понимается под равновесным  состоянием в двухсекторной модели  “производство – рынок”.

Оптимальная стратегия произ-ва и рынка (X*,Y*) является решением пары двойственных задач

Ax>=b

x>=0           производство

C(x)=>min

A^тy<=C

Y>=0                       рынок

B(y)=(b,y)=>max

Обеспечивает  такое равновесное состояние  двухсекторной экономики, при которой  ни рынку, ни произ-ву невыгодно уходить от оптимальной стратегии.

155. Используя платежную функцию,  дайте математическую формулировку  состояния равновесия в двухсекторной  экономике типа “производство  – рынок”

L(X,Y*)<=L(X*,Y*)<=L(X*,Y)

             (1)                 (2)

1. Если пр-во выберет х вместо х*, то в условиях наилучшего поведения рынка пр-во теряет прибыль
2. Если y отклоняется от у*, то уменьшится доход рынка, след-но (х*, у*) – состояние равновесия

156. Как практически найти состяние  равновесия в двухсеторной модели “производство – рынок”.

Решить

Ax>=b

x>=0           производство

C(x)=>min                                            =>(X*,Y*)

A^тy<=C

Y>=0                       рынок 

B(y)=(b,y)=>min

157. Может  ли двухсекторная экономика, описываемая  моделью “производство – рынок”, иметь несколько состояний равновесия.