Математика 44

<

092913 0129 441 Математика 44 Задача 1

Вариант 4

Решить графически задачу ЛП.

092913 0129 442 Математика 44

Решение задачи.

Построим область ограниченную условиями. Для начало построим прямые

092913 0129 443 Математика 44

 

Область, удовлетворяющая условия задачи закрашена серым цветом.

092913 0129 444 Математика 44

При перемещение линии уровня вверх видим, что максимальное значение целевой функции достигается в т.B. Найдем т.B решая систему уравнений

092913 0129 445 Математика 44

Построим линии уровня. Линией уровня функции называется множество точек из ее области определения, в которых функция принимает одно и то же фиксированное значение. Градиентом функции 092913 0129 446 Математика 44называется вектор 092913 0129 447 Математика 44указывающий направление наиболее быстро возрастания функции.

Решение которое будет 092913 0129 448 Математика 44 Тогда 092913 0129 449 Математика 44. Значение целевой функции будет 092913 0129 4410 Математика 44

Ответ: 092913 0129 4411 Математика 44

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 2.

Вариант 3.

 

Решить стандартную задачу ЛП


092913 0129 4412 Математика 44

симплекс-методом.

 

Решение задачи.

092913 0129 4413 Математика 44

Приведем задачу каноническому виду.

092913 0129 4414 Математика 44

092913 0129 4415 Математика 44

Здесь 092913 0129 4416 Математика 44достаточно большое число.

 

Б.п. 

092913 0129 4417 Математика 44

092913 0129 4418 Математика 44

092913 0129 4419 Математика 44

092913 0129 4420 Математика 44

092913 0129 4421 Математика 44

092913 0129 4422 Математика 44

092913 0129 4423 Математика 44

092913 0129 4424 Математика 44

092913 0129 4425 Математика 44

2 

4 

5 

1 

0 

0 

0 

50 

092913 0129 4426 Математика 44

3 

2 

5 

0 

-1 

0 

1 

20 

092913 0129 4427 Математика 44

5

6

6

0

0

1

0

40

индексная строка

-3

-5

-6

0

0

0

M

0

 

Базисное решение 092913 0129 4428 Математика 44
092913 0129 4429 Математика 44не оптимально, так как в индексной строке есть отрицательные элементы -3;-5;-6. Добиваемся оптимальности решения.

Выбираем ведущий столбец. Столбец, где максимальный по модулю отрицательный элемент в индексной строке. Это столбец 092913 0129 4430 Математика 44 Выбираем ведущую строку из 092913 0129 4431 Математика 44. Базисная переменная 092913 0129 4432 Математика 44 заменяется на 092913 0129 4433 Математика 44. Добиваемся того чтобы все элементы в ведущем столбце, кроме разрешающего элемента были равны 0. Для этого используем правило прямоугольников.


092913 0129 4434 Математика 44


092913 0129 4435 Математика 44

где 092913 0129 4436 Математика 44— новый элемент, 092913 0129 4437 Математика 44— старый элемент, 092913 0129 4438 Математика 44-разрешающий элемент, A и B-элементы построения прямоугольника в недостающих в двух вершинах и расположены на другой диагонали.

 

Например: найдем элементы первой строки


092913 0129 4439 Математика 44

Аналогично вычисляются все остальные элементы новой симплекс таблицы.

Б.п. 

092913 0129 4440 Математика 44

092913 0129 4441 Математика 44

092913 0129 4442 Математика 44

092913 0129 4443 Математика 44

092913 0129 4444 Математика 44

092913 0129 4445 Математика 44

092913 0129 4446 Математика 44

092913 0129 4447 Математика 44

092913 0129 4448 Математика 44

-1

2

0

1 

1

0 

-1

30

092913 0129 4449 Математика 44

092913 0129 4450 Математика 44

092913 0129 4451 Математика 44

1

0 

092913 0129 4452 Математика 44

0 

092913 0129 4453 Математика 44

4

092913 0129 4454 Математика 44

092913 0129 4455 Математика 44

092913 0129 4456 Математика 44

0

0 

092913 0129 4457 Математика 44

1 

092913 0129 4458 Математика 44

16

индексная строка

092913 0129 4459 Математика 44

092913 0129 4460 Математика 44

0

0 

092913 0129 4461 Математика 44

0 

092913 0129 4462 Математика 44

24

 

Базисное решение 092913 0129 4463 Математика 44
092913 0129 4464 Математика 44не оптимально, так как в индексной строке есть отрицательные элементы 092913 0129 4465 Математика 44;092913 0129 4466 Математика 44.

Далее продолжаем снова всю процедуру. Только 092913 0129 4467 Математика 44 полностью удаляем, так как он вышел из базисной переменной. Получаем новую симплекс таблицу. Теперь базисной переменной будет 092913 0129 4468 Математика 44. Ведущая строка 092913 0129 4469 Математика 44

Б.п. 

092913 0129 4470 Математика 44

092913 0129 4471 Математика 44

092913 0129 4472 Математика 44

092913 0129 4473 Математика 44

092913 0129 4474 Математика 44

092913 0129 4475 Математика 44

092913 0129 4476 Математика 44

092913 0129 4477 Математика 44

092913 0129 4478 Математика 44

0 

0 

1 

092913 0129 4479 Математика 44

092913 0129 4480 Математика 44

092913 0129 4481 Математика 44

092913 0129 4482 Математика 44

092913 0129 4483 Математика 44

0

1 

0 

092913 0129 4484 Математика 44

092913 0129 4485 Математика 44

092913 0129 4486 Математика 44

092913 0129 4487 Математика 44

092913 0129 4488 Математика 44

1

0 

0 

092913 0129 4489 Математика 44

092913 0129 4490 Математика 44

092913 0129 4491 Математика 44

индексная строка 

092913 0129 4492 Математика 44

0

0 

0 

092913 0129 4493 Математика 44

092913 0129 4494 Математика 44

092913 0129 4495 Математика 44

 

Базисное решение 092913 0129 4496 Математика 44
092913 0129 4497 Математика 44не оптимально, так как в индексной строке есть отрицательные элементы 092913 0129 4498 Математика 44.

Продолжаем процедуру заново. Получаем новую симплекс таблицу. Теперь базисной переменной вместо 092913 0129 4499 Математика 44 будет 092913 0129 44100 Математика 44. Ведущая строка 092913 0129 44101 Математика 44.

Б.п.

092913 0129 44102 Математика 44

092913 0129 44103 Математика 44

092913 0129 44104 Математика 44

092913 0129 44105 Математика 44

092913 0129 44106 Математика 44

092913 0129 44107 Математика 44

092913 0129 44108 Математика 44

092913 0129 44109 Математика 44

092913 0129 44110 Математика 44

-1

0 

1 

0

092913 0129 44111 Математика 44

092913 0129 44112 Математика 44

092913 0129 44113 Математика 44

092913 0129 44114 Математика 44

1 

1 

0 

0

092913 0129 44115 Математика 44

092913 0129 44116 Математика 44

092913 0129 44117 Математика 44

092913 0129 44118 Математика 44

3 

0 

0 

1 

092913 0129 44119 Математика 44

092913 0129 44120 Математика 44

индексная строка 

2

1

0 

0 

0

1

40

 

Базисное решение 092913 0129 44121 Математика 44
092913 0129 44122 Математика 44 оптимально. Отбрасывая временные переменные получаем решение исходной задачи 092913 0129 44123 Математика 44
092913 0129 44124 Математика 44

Ответ: 092913 0129 44125 Математика 44
092913 0129 44126 Математика 44.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3.

Вариант 2.

 

Решить ТЗ, заданную своей таблицей, методом потенциалов.

 

1 

6 

5 

3 

422 

4 

9 

2 

7 

195 

5 

8 

3 

4 

513 

114 

306 

483 

227 

 

 

Решение задачи.

 

092913 0129 44127 Математика 44

092913 0129 44128 Математика 44

092913 0129 44129 Математика 44

092913 0129 44130 Математика 44

мощность поставщиков 

092913 0129 44131 Математика 44

1 

6 

5 

3 

422 

092913 0129 44132 Математика 44

4 

9 

2 

7 

195 

092913 0129 44133 Математика 44

5 

8 

3 

4 

513 

<

мощность потребителей 

114 

306 

483 

227 

 

 

092913 0129 44134 Математика 44, 092913 0129 44135 Математика 44.

Так как 092913 0129 44136 Математика 44 то такая задача является закрытого типа.

Составляем начальный план. Для этого выбираем из таблицы тарифы минимальный элемент, им является элемент 1 в ячейке (1;1), впишем в нее значение 092913 0129 44137 Математика 44. Видим, что первом столбце все потребители выбраны. Вычеркиваем все ячейки первого столбца. Количество поставщиков в 1 строке стало 422-114=308. Далее продолжаем процесс, выбираем минимальный элемент из оставшихся элементов таблицы тарифов. Это элемент 2 в ячейке (2;3), впишем в нее значение 092913 0129 44138 Математика 44. Вычеркиваем все ячейки строки 2, так как все поставщики выбраны. Количество потребителей в 3 столбце стало 483-195=288. Из оставшихся ячеек таблицы тарифов минимальный элемент. Это элемент 3 в ячейке (1;4), впишем в нее значение 092913 0129 44139 Математика 44. Вычеркиваем все ячейки 4 столбца. Количество поставщиков в 1 строке стало 308-227=81. Минимальным из оставшихся ячеек будет 3 в ячейке (3;4) пишем в нее 092913 0129 44140 Математика 44. Вычеркиваем оставшиеся ячейки в 3 столбце. Количество поставщиков 3 строке стало 513-288=225. Минимальным из оставшихся ячеек будет 6 в ячейке (1;2) пишем в нее 092913 0129 44141 Математика 44. Вычеркиваем оставшиеся ячейки в 1 строке. Количество потребителей 2 столбце 306-81=225. В оставшейся ячейке пишем 092913 0129 44142 Математика 44

 

092913 0129 44143 Математика 44092913 0129 44144 Математика 44

092913 0129 44145 Математика 44

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n — 1 = 6. Следовательно, опорный план является невырожденным. Проверяем его на оптимальность. План является оптимальным если 092913 0129 44146 Математика 44 составим матрицу косвенных стоимостей.

092913 0129 44147 Математика 44


092913 0129 44148 Математика 44

092913 0129 44149 Математика 44

1 

6 

1 

3 

0 

1 

6 

1 

3 

1 

2 

7 

2 

4 

2 

3 

8 

3 

5 

 

092913 0129 44150 Математика 44 Полагая 092913 0129 44151 Математика 44. Получим 092913 0129 44152 Математика 44.

 

Так как в клетке (3;4) число больше чем в исходной таблице 092913 0129 44153 Математика 44, то полученный опорный план не оптимальный.

Составим новый опорный план. Для этого в предыдущий опорный план в ячейку (3;4) впишем новый груз +092913 0129 44154 Математика 44, а в остальных вершинах многоугольника чередующиеся знаки —092913 0129 44155 Математика 44, +092913 0129 44156 Математика 44, —092913 0129 44157 Математика 44.

092913 0129 44158 Математика 44 Новый тариф 092913 0129 44159 Математика 44 определяем из системы неравенств 092913 0129 44160 Математика 44, 092913 0129 44161 Математика 44должен быть максимальным удовлетворяющий системе. Получим 092913 0129 44162 Математика 44, тогда новый опорный план будет

092913 0129 44163 Математика 44

 

 

 

 

 

 

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

092913 0129 44164 Математика 44


092913 0129 44165 Математика 44

092913 0129 44166 Математика 44

1 

6 

2 

3 

0 

1 

6 

2 

3 

0 

1 

6 

2 

3 

1 

2 

7 

3 

4 

 

092913 0129 44167 Математика 44 Полагая 092913 0129 44168 Математика 44. Получим 092913 0129 44169 Математика 44.

Признак оптимальности выполнен. Значит опорный план оптимальный.

092913 0129 44170 Математика 44

Стоимость перевозок 092913 0129 44171 Математика 44.

 

Ответ:

092913 0129 44172 Математика 44

092913 0129 44173 Математика 44

 

Задача 4.

Вариант 2.

 

Предприятие (игрок A)
планирует выпуск продукции на квартал, рассматривая несколько различных вариантов своей деятельности (стратегии 092913 0129 44174 Математика 44)
Конкурирующее предприятие (игрок B)
может выбрать различные варианты поведения на рынке (стратегии 092913 0129 44175 Математика 44). Прогнозируемая прибыль предприятия A
за квартал в зависимости от сложившейся ситуации задаётся платёжной матрицей, определяющей соответствующую матричную игру (МИ). Требуется:

1) рассмотреть статистическую игру, заданную исходной платёжной матрицей, и определить оптимальные стратегии игрока A в соответствии с критерием Вальда, критерием Гурвица с показателем пессимизма 092913 0129 44176 Математика 44, критерием Сэвиджа и критерием Лапласа.

2)вычислить нижнюю и верхнюю цену игры, найти гарантирующие стратегии игроков A и В;

3)упростить платёжную матрицу путём отбрасывания доминируемых стратегий игроков A и В;

4)найти оптимальную смешанную стратегию игрока А
и цену игры графическим методом;

для определения оптимальной смешанной стратегии игрока В
составить стандартную задачу ЛП, решить её симплекс-методом, найти оптимальную смешанную стратегию и вычислить цену игры.

 

092913 0129 44177 Математика 44

092913 0129 44178 Математика 44

092913 0129 44179 Математика 44

092913 0129 44180 Математика 44

092913 0129 44181 Математика 44

092913 0129 44182 Математика 44

-1 

-2 

-6 

-2 

-5 

092913 0129 44183 Математика 44

-4 

-3 

-2 

-3 

-1 

092913 0129 44184 Математика 44

0 

-2 

0 

-1 

0 

092913 0129 44185 Математика 44

-3 

-1 

-2 

-1 

-1 

Показатель пессимизма 092913 0129 44186 Математика 44

Решение задачи.

1)

Критерий Вальда.

Выбирается 092913 0129 44187 Математика 44

092913 0129 44188 Математика 44

 

-1 

-2 

-6 

-2 

-5 

-4 

-3 

-2 

-3 

-1 

0 

-2 

0 

-1 

0 

-3

-1 

-2 

-1 

-1 

 

092913 0129 44189 Математика 44, 092913 0129 44190 Математика 44.

Ответ: согласно критерию Вальда, при данных условиях для игрока A оптимальным будет стратегия 092913 0129 44191 Математика 44.

Критерий Гурвица с показателем пессимизма 092913 0129 44192 Математика 44

092913 0129 44193 Математика 44

 

092913 0129 44194 Математика 44

092913 0129 44195 Математика 44

092913 0129 44196 Математика 44

092913 0129 44197 Математика 44

-1 

-6 

092913 0129 44198 Математика 44

092913 0129 44199 Математика 44

-1 

-4 

092913 0129 44200 Математика 44

092913 0129 44201 Математика 44

0 

-2 

092913 0129 44202 Математика 44

092913 0129 44203 Математика 44

-1 

-3 

092913 0129 44204 Математика 44

092913 0129 44205 Математика 44

Ответ: согласно критерию Гурвица с показателем пессимизма 092913 0129 44206 Математика 44, при данных условиях для игрока A оптимальным будет стратегия 092913 0129 44207 Математика 44.

 

Критерий Сэвиджа.

Строить матрица R – риска, элементы находятся 092913 0129 44208 Математика 44

092913 0129 44209 Математика 44

 

092913 0129 44210 Математика 44

092913 0129 44211 Математика 44 , 092913 0129 44212 Математика 44

Ответ : согласно критерию Сэвиджа, при данных условиях для игрока A оптимальным будет стратегия 092913 0129 44213 Математика 44.

Критерий Лапласа.

092913 0129 44214 Математика 44

092913 0129 44215 Математика 44, 092913 0129 44216 Математика 44

Ответ: согласно критерию Лапласа, при данных условиях для игрока A оптимальным будет стратегия 092913 0129 44217 Математика 44.

2)

092913 0129 44218 Математика 44-нижняя цена игры. 092913 0129 44219 Математика 44.

092913 0129 44220 Математика 44-верхняя цена игры 092913 0129 44221 Математика 44

092913 0129 44222 Математика 44, 092913 0129 44223 Математика 44

 

092913 0129 44224 Математика 44, 092913 0129 44225 Математика 44

Ответ: 092913 0129 44226 Математика 44, 092913 0129 44227 Математика 44 следовательно гарантирующих стратегий для игроков A и B нет.

3)

Элементы 1 строки меньше либо равны соответствующим элементам 3 строки. Значит 1 строка является доминируемой, т.е. 1 стратегией игроку A пользоваться заведомо невыгодно. Следовательно, 1 строку можно исключить. Аналогично элементы 2 строки меньше либо равны соответствующим элементам 4 строки. Значит 2 строка является доминируемой и ей игроку A пользоваться заведомо невыгодно. Следовательно, 2 строку можно исключить. Больше сравниваемых строк нет. Получим следующую матрицу.

 

092913 0129 44228 Математика 44

Элементы 3 и 5 столбца больше либо равно соответствующим элементам 1 столбца. Столбцы 3 и 5 являются доминируемой, т.е этими стратегиями игроку B пользоваться заведомо невыгодно. Следовательно, 3 и 5 столбцы можно исключить. Аналогично элементы 4 столбца больше либо равно соответствующим элементам 2 столбца. Столбец 4 являются доминируемой, т.е этими стратегиями игроку B пользоваться заведомо невыгодно. Следовательно, 4 столбец можно исключить. Получим следующую матрицу.

092913 0129 44229 Математика 44

Ответ: 092913 0129 44230 Математика 44.

4)

Прибавим ко всем элементам матрицы 092913 0129 44231 Математика 44 элемент 092913 0129 44232 Математика 44, чтобы все элементы матрицы были положительными. Тогда оптимальная смешанная стратегия не изменится, а цена игры увеличится на 092913 0129 44233 Математика 44. Пусть 092913 0129 44234 Математика 44

092913 0129 44235 Математика 44.

Построим прямые

092913 0129 44236 Математика 44,

092913 0129 44237 Математика 44

 

092913 0129 44238 Математика 44

Найдем т. M решим уравнение 092913 0129 44239 Математика 44

092913 0129 44240 Математика 44. 092913 0129 44241 Математика 44

Тогда 092913 0129 44242 Математика 44. 092913 0129 44243 Математика 44

Ответ: оптимальная смешанная стратегия игрока A равна 092913 0129 44244 Математика 44, цена игры

092913 0129 44245 Математика 44.

5)

092913 0129 44246 Математика 44

092913 0129 44247 Математика 44

Приведем к каноническую виду

092913 0129 44248 Математика 44

092913 0129 44249 Математика 44

Б.п.

092913 0129 44250 Математика 44

092913 0129 44251 Математика 44

092913 0129 44252 Математика 44

092913 0129 44253 Математика 44

С.ч.

092913 0129 44254 Математика 44

4

2

1

0

1

092913 0129 44255 Математика 44

1

3

0

1

1

индексная

строка 

-1

-1

0

0

0

 

 

 

 

 

 

092913 0129 44256 Математика 44

Б.п. 

092913 0129 44257 Математика 44

092913 0129 44258 Математика 44

092913 0129 44259 Математика 44

092913 0129 44260 Математика 44

С.ч. 

092913 0129 44261 Математика 44

1

092913 0129 44262 Математика 44

092913 0129 44263 Математика 44

0 

092913 0129 44264 Математика 44

092913 0129 44265 Математика 44

0

092913 0129 44266 Математика 44

092913 0129 44267 Математика 44

1 

092913 0129 44268 Математика 44

индексная

строка 

0

092913 0129 44269 Математика 44

092913 0129 44270 Математика 44

0 

092913 0129 44271 Математика 44

 

 

 

 

 

 

 

 

092913 0129 44272 Математика 44

Б.п. 

092913 0129 44273 Математика 44

092913 0129 44274 Математика 44

092913 0129 44275 Математика 44

092913 0129 44276 Математика 44

С.ч. 

092913 0129 44277 Математика 44

1 

0 

092913 0129 44278 Математика 44

092913 0129 44279 Математика 44

092913 0129 44280 Математика 44

092913 0129 44281 Математика 44

0 

1 

092913 0129 44282 Математика 44

092913 0129 44283 Математика 44

092913 0129 44284 Математика 44

индексная

строка 

0 

0 

092913 0129 44285 Математика 44

092913 0129 44286 Математика 44

092913 0129 44287 Математика 44

 

 

 

 

 

 

 

 

 

092913 0129 44288 Математика 44

092913 0129 44289 Математика 44

092913 0129 44290 Математика 44

092913 0129 44291 Математика 44

Ответ: оптимальная смешанная стратегия игрока A равна 092913 0129 44292 Математика 44, цена

игры 092913 0129 44293 Математика 44.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 5.

Вариант 3.

 

Задан взвешенный граф. Требуется найти кратчайший путь из вершины 092913 0129 44294 Математика 44в вершину 092913 0129 44295 Математика 44методом динамического программирования на графе.

092913 0129 44296 Математика 44

Решение задачи.

092913 0129 44297 Математика 44

092913 0129 44298 Математика 44

092913 0129 44299 Математика 44

092913 0129 44300 Математика 44

092913 0129 44301 Математика 44

092913 0129 44302 Математика 44

092913 0129 44303 Математика 44

092913 0129 44304 Математика 44Следовательно, кратчайший путь 092913 0129 44305 Математика 44 и он равен 14.

 

Ответ: путь 092913 0129 44306 Математика 44 длиной 14.

 

 

<

Комментирование закрыто.

MAXCACHE: 1.09MB/0.00175 sec

WordPress: 22.42MB | MySQL:118 | 4,226sec