Оптимальное решение двойственной задачи

Используя теоремы двойственности можно записать оптимальное решение двойственной задачи, не решая ее отдельно, а используя только решение исходной задачи, найденное симплексным методом.

Для этого необходимо установить соответствие между переменными исходной задачи и двойственной. В общем случае:

Задача I (исходная)
Первоначальные переменные	Балансовые переменные
х 1	х 2	…	хп	хп +1	хп +2	…	хп + т
↕	↕	↕	↕	↕	↕	↕	↕
ут +1	ут +2	…	ут + п	у 1	у 2	…	ут
Балансовые переменные	Первоначальные переменные
Задача II (двойственная)

 

Пусть при решении исходной задачи получили:

Х _опт.= (х ₁*, х ₂*, …, х_п+т *),

F _max + с ₁* х ₁ + с ₂* х ₂ +…+ с_п+т * х_п+т = F *.

Для двойственной задачи оптимальное решение будит иметь вид

Y _опт. = (у ₁*, у ₂*, …, у_{т +п}*),

Z _min = Z *+ b ₁* y ₁ + b ₂* y ₂ +…+ b_т+п * y_т+n.

При этом выполняются равенства:

Z *= F *,

у 1*	у 2*	…	ут*	ут +1*	ут +2*	…	ут + п *
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀	׀׀	׀׀
сп +1*	сп +2*	…	сп + т *	с 1*	с 2*	…	сп*

и

b 1*	b *	…	bт*	bт +1*	bт +2*	…	bт + п *
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀	׀׀	׀׀
xп +1*	xп +2*	…	xп + т *	x 1*	x 2*	…	xп*

 

Рассмотрим применение этой теоремы на примере задачи об использовании ресурсов.

Пример. Найти с помощью теорем двойственности оптимум Z _min и оптимальное решение Y _опт. двойственной задачи для задачи об использовании ресурсов.

Решение. Установим соответствие между переменными исходной и двойственной задач.

Решая задачу об использовании ресурсов симплексным методом, мы имели две (п = 2) первоначальные переменные х ₁, х ₂ и четыре (т = 4) балансовые переменные х ₃, х ₄, х ₅ и х ₆. Ранее мы сформулировали двойственную задачу:

при ограничениях

и условии неотрицательности .

Как видим, в двойственной задаче присутствуют четыре (т = 4) первоначальные переменные у ₁, у ₂, у ₃ и у ₄. Для преобразования ограничительных неравенств в равенства (при решении двойственной задачи симплексным методом) потребуется ввести две (п = 2) балансовые переменные у ₅ и у ₆.

Тогда соответствие между переменными можно записать так:

х 1	х 2		х 3	х 4	х 5	х 6
↕	↕		↕	↕	↕	↕
у 5	у 6		у 1	у 2	у 3	у 4

На последнем шаге решения исходной задачи симплексным методом, мы получили Х _опт.= (6, 4, 0, 0, 1, 3) и F _max + 0,8 х ₃ + 0,6 х ₄ = 24. Для двойственной задачи оптимальное решение будет иметь вид Y _опт. = (у ₁*, у ₂*, у ₃*, у ₄*, у ₅*, у ₆*) и Z _min = Z * +b ₁* y ₁ + b ₂* y ₂ + b ₃* y ₃ + b ₄* y ₄ + b ₅* y ₅ + b ₆* y ₆.

Используя теорему двойственности, можем записать:

Z *= F * = 24,

у 1*	у 2*	у 3*	у 4*	у 5*	у 6*
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀
с3 *	с 4*	с 5*	с 6*	с 1*	с 2*
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀
0,8	0,6

и

b 1*	b 2*	b 3*	b 4*	b 5*	b 6*
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀
x 3*	x 4*	x 5*	x 6*	x 1*	x 2*
׀׀	׀׀	׀׀	׀׀	׀׀	׀׀

Таким образом,

Y _опт.= (0,8; 0,6; 0, 0, 0, 0),

Z _min = 24 +0 · y ₁ + 0 · y ₂ + 1· y ₃ +3· y ₄ +6· y ₅ + 4· y ₆ = 24 + y ₃ +3 y ₄ +6 y ₅ + 4 y ₆.

 

Вывод. Оптимальное решение двойственной задачи будет иметь вид

Y _опт. = (0,8; 0,6; 0; 0; 0; 0),

Z _min= 24 + y ₃ +3 y ₄ +6 y ₅ + 4 y ₆.

 

Литература

 

7. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб.-справоч. Пособие/ под ред. проф. Н.Ш.Кремера. – М.: Высшее образование, 2009

8. Данко П.Е. Высшая математика в упражнениях и задачах. В 2 ч. Ч. 2: Учеб. пособие для вузов / П.Е.Данко, А.Г.Попова, Т.Я.Кожевникова. – 6-е изд. – М.: ООО «Издательство Оникс»: ООО Издательство «Мир и Оразование», 2006

9. Конюховский П.В. Математические методы исследования операций в экономике: Учебное пособие. – СПб.: Питер, 2002

 

 

Расчетно-графические задания

для студентов очной формы обучения

Расчетно-графическое задание № 1

Элементы векторной алгебры, линейной алгебры

и аналитической геометрии

Задача 1.

1-10. Применяя метод Гаусса исключения неизвестных, решить систему линейных уравнений. Сделать проверку полученного решения.

 

1. 2.

 

3. 4.

 

5. 6.

 

7. 8.

 

9. 10.

Задача 2.

11-20. Даны векторы в некотором базисе. Показать, что векторы образуют базис, и найти координаты вектора в этом базисе. Систему линейных уравнений решить методом Крамера.

 

11.	(7,3,0),	(4,1,1),	(-7,1,12),	(-1,5,10).
12.	(2,0,3),	(-9,2,10),	(-4,2,10),	(-1,-2,-10).
13.	(1,2,2),	(5,-2,-7),	(0,5,-1),	(-2,6,-6).
14.	(-2,3,1),	(2,6,7),	(4,-1,0),	(6,-3,-5).
15.	(1,3,1),	(1,-8,2),	(0,-5,3),	(3,-8,2).
16.	(2,5,-1),	(-1,2,-6),	(-2,1,1),	(-11,-5,-1).
17.	(-1,4,3),	(5,0,1),	(-1,4,4),	(-7,8,7).
18.	(3,3,2),	(1,2,3),	(1,-1,4),	(4,-1,7).
19.	(-2,-1,1),	(2,3,0),	(-4,2,3),	(-10,-9,3).
20.	(1,5,1),	(-2,5,4),	(3,-1,2),	(4,19,9).

Задача 3.

21-30. Даны вершины А ₁(х₁, у₁, z₁), А ₂(х₂, у₂, z₂), А ₃(х₃, у₃, z₃),
А ₄(х₄, у₄, z₄), пирамиды. Построить пирамиду в декартовой и ортонормированной системе координат и найти:

1) длину ребра А ₁ А ₂;

2) угол между ребрами А ₁ А ₂ и А ₁ А ₄;

3) уравнение грани А ₁ А ₂ А ₃ и ее площадь;

4) уравнения высоты, опущенной из вершины А ₄ на грань А ₁ А ₂ А ₃.

 

21.	А 1(3,-2,8),	А 2(-1,3,2),	А 3(2,0,-1),	А 4(4,-2,3).
22.	А 1(2,-1,8),	А 2(3,4,4),	А 3(2,-1,2),	А 4(6,-1,6).
23.	А 1(8,5,0),	А 2(-3,7,-5),	А 3(-4,1,3),	А 4(-2,1,-4).
24.	А 1(0,1,-1),	А 2(3,-4,4),	А 3(6,-5,3),	А 4(5,2,-1).
25.	А 1(3,2,-3),	А 2(3,-1,-1),	А 3(0,2,-2),	А 4(1,-2,3).
26.	А 1(0,6,-1),	А 2(3,0,5),	А 3(4,-1,0),	А 4(2,1,-4).
27.	А 1(2,-3,2),	А 2(0,5,4),	А 3(5,6,1),	А 4(-2,-2,3).
28.	А 1(6,-2,0),	А 2(6,2,-1),	А 3(2,-1,4),	А 4(-2,7,4).
29.	А 1(1,4,-2),	А 2(-3,0,3),	А 3(8,0,1),	А 4(1,-4,3).
30.	А 1(1,8,2),	А 2(4,-1,2),	А 3(-1,5,3),	А 4(3,3,-3).

 

Задача 4.

31-40. Составить уравнение множества точек, для каждой из которых выполняется следующее условие:

31. Сумма квадратов расстояний до точек А (1,1) и В (-3,3) равна 20.

32. Сумма квадратов расстояний до точек А (3,0), В (0,4) и
С (-1,-1) равна 28.

33. Сумма квадратов расстояний до точек А (3,-3), В (-1,1),
С (-1,0) и D (2,-4) равна 58.

34. Квадрат расстояния до точки А (0,3) на 3 больше квадрата расстояния до оси абсцисс.

35. Сумма расстояний до точек А (6,0) и О (0,0) равна 10.

36. Квадрат расстояния до точки А (2,0) на 16 больше квадрата расстояния до оси координат.

37. Сумма квадратов расстояний до сторон прямоугольника, образованного прямыми х=0, у=0, х-4=0, у-2=0, равна 20.

38. Расстояние до точки А (0,3) равно расстоянию до оси абсцисс.

39. Разность расстояний до точек А (0,10) и О (0,0) равна 8.

40. Расстояние до точки А (2,0) равно расстоянию до оси ординат.

 

Расчетно-графическое задание № 2

Дифференциальное исчисление функций одной переменной.

Применение дифференциального исчисления

для исследования функций и построения их графиков

 

Задача 1.

41-50. Найти пределы:

41. а) б) в)

42. а) б) в)

43. а) б) в)

44. а) б) в)

45. а) б) в)

46. а) б) в)

47. а) б) в)

48. а) б) в)

49. а) б) в)

50. а) б) в)

Задача 2.

51-60. Задана функция y=f(x). Найти все точки разрыва функции, если они существуют. Построить график функции.

 

51. 52.

 

53. 54.

 

55. 56.

 

57. 58.

 

59. 60.

Задача 3.

61-70. Найти производные следующих функций:

61.

 

62.

 

63.

 

64.

 

65.

 

66.

 

67.

 

68.

 

69.

 

70.

 

Задача 4.

71-80. Вычислить приближенно , заменяя приращение функции ее дифференциалом.

71. 72. 73. 74. 75.

76. 77. 78. 79. 80.

 

 

Задача 5.

81-90. Заданные функции исследовать методами дифференциального исчисления. На основании результатов исследований построить графики функций.

81. 82.

 

83. 84.

 

85. 86. .

 

87. 88.

 

89. 90.

 

Расчетно-графическое задание № 3

Неопределенный интеграл

Определенный интеграл

 

Задача 1.

91-100. Найти интегралы. Результаты проверить дифференцированием.

 

91.

 

92.

 

93.

94.

 

95.

 

96.

 

97.

98.

 

99.

 

100.

 

Задача 2.

101-110. Найти площадь фигуры, ограниченной заданными линиями. Сделать рисунок.

101. у=х ³, у= 4 х. 102. у= 4 -х ², у= -2 x

103. у=х ², , у= 2 х. 104. у= 2 х ², у= .

105. , 106. у= , у= 4 х ^3/2.

107. у= 3-2 х, у=х ². 108. у= 2 -х ², у= х ².

109. у= , . 110. у=х ³, у=-х ².

Задача 3.

111-120. Вычислить несобственный интеграл или доказать его расходимость.

111. . 112. 113. . 114. .

115. . 116. 117. . 118. .

119. . 120 .

Расчетно-графическое задание № 4

Функции нескольких переменных.

Ряды.

Обыкновенные дифференциальные уравнения

 

Задача 1.

121-130. Задана функция . Найти:

а) наименьшее и наибольшее значение функции в ограниченной области Д;

б) вектор – градиент функции в точке А. Область Д и вектор изобразить на чертеже.

 

121. ; а) Д: ; б) .

122. ; а) Д: ; б)

123. ; а) Д: ; б) .

124. ; а) Д: ; б) .

125. ; а) Д: ; б) .

126. ; а) Д: ; б) .

127. ; а) Д: ; б) .

128. ; а) Д: ; б) .

129. ; а) Д: ; б) .

130. ; а) Д: ; б) .

 

Задача 2.

131-140. Исследовать на сходимость данный ряд.

131. . 132. . 133. .

134. . 135. . 136. .

137. . 138. . 139. .

140. .

 

Задача 3.

141-150. Найти область сходимости данного ряда.

141. . 142. . 143. . 144. .

145. . 146. . 147. . 148.

149. . 150. .

 

Задача 4.

151-160. Найти общее решение дифференциального уравнения.

151. . 152. .

153. 154. .

155. . 156. .

157. . 158. .

159. . 160. .

Задача 5.

161-170. Найти частное решение дифференциального уравнения, удовлетворяющее заданным начальным условиям.

161. , , .

162. , , .

163. , . .

164. , , .

165. , , .

166. , , .

167. , , .

168. , , .

169. , , .

170. , , .

 

Расчетно-графическое задание № 5

Теория вероятностей и математическая статистика

Задача 1

1–10. 1. Подбрасываются две игральные кости. Требуется: 1) описать множество элементарных случайных событий, 2) найти вероятности событий А ={выпадение двух «шестерок»}, В = {выпадение хотя бы одной «шестерки»}, С = {выпадение одной «шестерки»}.

2. В контейнере находятся 40 телевизоров, среди которых 5 имеют скрытые дефекты. Найти вероятность того, что 3 наудачу выбранных телевизора не будут иметь дефектов.

3. Аудитор проверяет три счета. Вероятность правильного оформления счета равна 0,9. Найти вероятности событий А = {правильно оформлены три счета}, В = {правильно оформлены два счета}, С = {правильно оформлен один счет}, D = {правильно оформлен хотя бы один счет}.

4. Инвестор наудачу приобретает акции 2-х фондов из 10. Среди 10 фондов 4 невыгодные. Найти вероятности событий А = {инвестор вкладывает деньги в выгодные фонды}, В = {инвестор вкладывает деньги в невыгодные фонды}, С ={инвестор вкладывает деньги хотя бы в один выгодный фонд}.

5. В каждом из двух ящиков содержатся 6 черных и 4 белых шара. Из первого ящика наудачу переложили во второй ящик 1 шар. Найти вероятность того, что два наугад взятые шара из второго ящика будут белыми.

6. На склад поступают однотипные детали с двух заводов – №1 и №2. Завод №1 поставляет 30% деталей, из которых 10% имеют низкое качество. Завод №2 производит детали, из которых 80% имеют высокое качество. Найти вероятность того, что наугад взятая со склада деталь будет высокого качества.

7. Из 3-х урн наудачу извлекается один шар в соответствие с правилом: при подбрасывании игральной кости если выпадает 1 очко, то выбирается урна 1; если выпадает 2, 3 или 4 очка, то выбирается урна 2; если выпадает 5 или 6 очков, то урна 3. В урне 1 находится 10 шаров, из них 2 красных, в урне 2 – 15 шаров, из них 3 красных, в урне 3 – 20 шаров, из них 10 красных. Найти вероятности событий А = {будет извлечен красных шар}, В = {извлеченный красный шар принадлежит урне 1}.

8. В магазине представлена обувь 3-х фабрик: 30% обуви поставила фабрика 1, 25% – фабрика 2, остальную обувь – фабрика 3. Покупатель выбирает обувь наудачу. Процент возврата обуви, изготовленной фабрикой 1 – 3%, фабрикой 2 – 1%, фабрикой 3 – 0,5%. Найти вероятности событий А = {обувь покупателем не будет возвращена}, В = {невозвращенная обувь изготовлена фабрикой 3}.

9. Автомат изготавливает однотипные детали, 5% произведенной продукции оказывается бракованной. Найти вероятность того, что из четырех последовательно изготовленных деталей будут бракованными не более двух.

10. Вероятность поражения стрелком мишени при одном выстреле равна 0,8. Найти вероятность того, что при пяти последовательных выстрелах будет не менее четырех попаданий.

 

Задача 2

11–16. Задана плотность распределения вероятностей непрерывной случайной величины Х. Требуется:

1) определить коэффициент А;

2) найти функцию распределения ;

3) схематично построить графики и ;

4) найти математическое ожидание и дисперсию Х;

5) найти вероятность того, что Х примет значение из интервала .

11. 12.

 

13. 14.

 

15. 16.

 

17–20. Задана функция распределения непрерывной случайной величины Х. Требуется:

1) найти плотность распределения вероятностей ;

2) определить коэффициент А;

3) схематично простроить графики и ;

4) найти математическое ожидание и дисперсию Х;

5) найти вероятность того, что Х примет значение из интервала .

17. 18.

19. 20.

.

 

Задача 3

21–30. Заданы математическое ожидание и среднее квадратическое отклонение нормально распределенной случайной величины Х. Требуется:

1) написать плотность распределения вероятностей и схематично построить ее график;

2) найти вероятность того, что Х примет значение из интервала .

 

21.	,	,	,	.	22.	,	,	,	.
23.	,	,	,	.	24.	,	,	,	.
25.	,	,	,	.	26.	,	,	,	.
27.	,	,	,	.	28.	,	,	,	.
29.	,	,	,	.	30.	,	,	,	.

Задача 4

31–40. Производится некоторый опыт, в котором случайное событие А может появиться с вероятностью p. Опыт повторяют в неизменных условиях n раз.

31. . Определить вероятность того, что в 900 опытах событие А произойдет от 250 до 320 раз.

32. . Определить вероятность того, что относительная частота появления события А отклонится от не более, чем на 0,05.

33. . Определить вероятность того, что в 1000 опытах событие А произойдет не менее чем 580 раз.

34. . Определить вероятность того, что в 700 опытах событие А произойдет в меньшинстве опытов.

35. . Определить вероятность того, что в 900 опытах событие А произойдет в большинстве опытов.

36. . Определить вероятность того, что в 800 опытах относительная частота появления события А отклонится от вероятности не более, чем на 0,05.

37. . Найти, какое отклонение относительной частоты появления события А от