Математика 46

<

092913 0133 461 Математика 46 Решить графически задачу ЛП.

092913 0133 462 Математика 46

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

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

092913 0133 463 Математика 46

 

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

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

 

092913 0133 466 Математика 46

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

092913 0133 467 Математика 46

Решение которое будет 092913 0133 468 Математика 46 Тогда 092913 0133 469 Математика 46. Значение целевой функции будет 092913 0133 4610 Математика 46

Ответ: 092913 0133 4611 Математика 46,092913 0133 4612 Математика 46

 

 

 

 

 

 

 

 

 

 

Задача 2.

Вариант 1.

 

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


092913 0133 4613 Математика 46

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

 

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

092913 0133 4614 Математика 46

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

092913 0133 4615 Математика 46

092913 0133 4616 Математика 46

Здесь 092913 0133 4617 Математика 46достаточно большое число.

 

Б.п. 

092913 0133 4618 Математика 46

092913 0133 4619 Математика 46

092913 0133 4620 Математика 46

092913 0133 4621 Математика 46

092913 0133 4622 Математика 46

092913 0133 4623 Математика 46

092913 0133 4624 Математика 46

092913 0133 4625 Математика 46

092913 0133 4626 Математика 46

2 

3

4

1 

0 

0 

0 

15

092913 0133 4627 Математика 46

1

4

5 

0 

1 

0 

0

18

092913 0133 4628 Математика 46

4

5

3

0

0

-1

1

10

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

-8

-7

-6

0

0

0

M

0

 

Базисное решение 092913 0133 4629 Математика 46
092913 0133 4630 Математика 46не оптимально, так как в индексной строке есть отрицательные элементы -8;-7;-6. Добиваемся оптимальности решения.

Выбираем ведущий столбец. Столбец, где максимальный по модулю отрицательный элемент в индексной строке. Это столбец 092913 0133 4631 Математика 46. Выбираем ведущую строку из 092913 0133 4632 Математика 46. Базисная переменная 092913 0133 4633 Математика 46 заменяется на 092913 0133 4634 Математика 46. Добиваемся того чтобы все элементы в ведущем столбце, кроме разрешающего элемента были равны 0. Для этого используем правило прямоугольников.


092913 0133 4635 Математика 46


092913 0133 4636 Математика 46

где 092913 0133 4637 Математика 46— новый элемент, 092913 0133 4638 Математика 46— старый элемент, 092913 0133 4639 Математика 46-разрешающий элемент, A и B-элементы построения прямоугольника в недостающих в двух вершинах и расположены на другой диагонали.

 

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


092913 0133 4640 Математика 46

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

Б.п. 

092913 0133 4641 Математика 46

092913 0133 4642 Математика 46

092913 0133 4643 Математика 46

092913 0133 4644 Математика 46

092913 0133 4645 Математика 46

092913 0133 4646 Математика 46

092913 0133 4647 Математика 46

092913 0133 4648 Математика 46

092913 0133 4649 Математика 46

0

092913 0133 4650 Математика 46

092913 0133 4651 Математика 46

1 

0

092913 0133 4652 Математика 46

092913 0133 4653 Математика 46

10

092913 0133 4654 Математика 46

0

092913 0133 4655 Математика 46

092913 0133 4656 Математика 46

0 

1

092913 0133 4657 Математика 46

092913 0133 4658 Математика 46

092913 0133 4659 Математика 46

092913 0133 4660 Математика 46

1

092913 0133 4661 Математика 46

092913 0133 4662 Математика 46

0 

0

092913 0133 4663 Математика 46

092913 0133 4664 Математика 46

092913 0133 4665 Математика 46

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

0

3

0

0 

0

-2

092913 0133 4666 Математика 46

20

 

Базисное решение 092913 0133 4667 Математика 46
092913 0133 4668 Математика 46не оптимально, так как в индексной строке есть отрицательный элемент -2.

Далее продолжаем снова всю процедуру. Только 092913 0133 4669 Математика 46 полностью удаляем, так как он вышел из базисной переменной. Получаем новую симплекс таблицу. Теперь базисной переменной будет 092913 0133 4670 Математика 46. Ведущая строка 092913 0133 4671 Математика 46

Б.п. 

092913 0133 4672 Математика 46

092913 0133 4673 Математика 46

092913 0133 4674 Математика 46

092913 0133 4675 Математика 46

092913 0133 4676 Математика 46

092913 0133 4677 Математика 46

092913 0133 4678 Математика 46

092913 0133 4679 Математика 46

0

1

5

2

0

1

20

092913 0133 4680 Математика 46

0

092913 0133 4681 Математика 46

3

092913 0133 4682 Математика 46

1

0

092913 0133 4683 Математика 46

092913 0133 4684 Математика 46

1

092913 0133 4685 Математика 46

2

2

0

0

092913 0133 4686 Математика 46

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

0

5

10

4

0

0

60

 

Базисное решение 092913 0133 4687 Математика 46
092913 0133 4688 Математика 46 оптимально. Отбрасывая временные переменные, получаем решение исходной задачи 092913 0133 4689 Математика 46
092913 0133 4690 Математика 46

Ответ: 092913 0133 4691 Математика 46
092913 0133 4692 Математика 46.

 

 

 

 

 

 

 

 

Задача 3.

Вариант 9.

 

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

 

7

3

8

4

545

6

1

2 

9

413

4

7

5

6

242

427

293

148

332

 

 

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

 

092913 0133 4693 Математика 46

092913 0133 4694 Математика 46

092913 0133 4695 Математика 46

092913 0133 4696 Математика 46

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

092913 0133 4697 Математика 46

7 

3 

8 

4 

545 

092913 0133 4698 Математика 46

6 

1 

2 

9 

413 

092913 0133 4699 Математика 46

4 

7 

5 

6 

242 

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

427 

293 

148 

332 

 

 

092913 0133 46100 Математика 46, 092913 0133 46101 Математика 46.

Так как 092913 0133 46102 Математика 46 то такая задача является закрытого типа.

Составляем начальный план. Для этого выбираем из таблицы тарифов минимальный элемент, им является элемент 1 в ячейке (2;2), впишем в нее значение 092913 0133 46103 Математика 46. Видим, что первом столбце все потребители выбраны. Вычеркиваем все ячейки первого столбца. Количество поставщиков в 2 строке стало 413-293=120. Далее продолжаем процесс, выбираем минимальный элемент из оставшихся элементов таблицы тарифов. Это элемент 2 в ячейке (2;3), впишем в нее значение 092913 0133 46104 Математика 46. Вычеркиваем все ячейки строки 2, так как все поставщики выбраны. Количество потребителей в 3 столбце стало 148-120=28. Из оставшихся ячеек таблицы тарифов выбираем минимальный элемент. Это элемент 4 в ячейке (1;4), впишем в нее значение 092913 0133 46105 Математика 46. Вычеркиваем все ячейки 4 столбца. Количество поставщиков в 1 строке стало 545-332=213. Минимальным из оставшихся ячеек будет 4 в ячейке (3;1) пишем в нее 092913 0133 46106 Математика 46. Вычеркиваем оставшиеся ячейки в 3 строке. Количество потребителей в 1 столбце стало 427-242=185. Минимальным из оставшихся ячеек будет 7 в ячейке (1;1) пишем в нее 092913 0133 46107 Математика 46. Вычеркиваем оставшиеся ячейки в 1 строке. Количество поставщиков в 1 строке 213-185=28. В оставшейся ячейке пишем 092913 0133 46108 Математика 46

 

092913 0133 46109 Математика 46092913 0133 46110 Математика 46

092913 0133 46111 Математика 46

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

<

092913 0133 46113 Математика 46


092913 0133 46114 Математика 46

092913 0133 46115 Математика 46

7

7

8

4

0 

7

7

8

4

-6

1

1

2 

-2

-3

4

4

5

1

092913 0133 46116 Математика 46 Полагая 092913 0133 46117 Математика 46. Получим 092913 0133 46118 Математика 46.

Так как в клетке (1;2) число больше чем в исходной таблице 092913 0133 46119 Математика 46, то полученный опорный план не оптимальный.

Составим новый опорный план. Для этого в предыдущий опорный план в ячейку (1;2) впишем новый груз +092913 0133 46120 Математика 46, а в остальных вершинах многоугольника чередующиеся знаки —092913 0133 46121 Математика 46, +092913 0133 46122 Математика 46, —092913 0133 46123 Математика 46.

092913 0133 46124 Математика 46 Новый 092913 0133 46125 Математика 46 определяем из системы неравенств 092913 0133 46126 Математика 46, 092913 0133 46127 Математика 46должен быть максимальным удовлетворяющий системе. Получим 092913 0133 46128 Математика 46, тогда новый опорный план будет

092913 0133 46129 Математика 46

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

092913 0133 46130 Математика 46


092913 0133 46131 Математика 46

092913 0133 46132 Математика 46

7

3

4

4

0 

7 

3 

4 

4 

-2

5

1

2 

2

-3

4

0

1

1

 

092913 0133 46133 Математика 46 Полагая 092913 0133 46134 Математика 46. Получим 092913 0133 46135 Математика 46.

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

092913 0133 46136 Математика 46

Стоимость перевозок 092913 0133 46137 Математика 46.

 

Ответ:

092913 0133 46138 Математика 46

092913 0133 46139 Математика 46

 

 

 

 

 

 

 

 

 

 

Задача 4.

Вариант 9.

 

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

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

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

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

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

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

 

092913 0133 46143 Математика 46

092913 0133 46144 Математика 46

092913 0133 46145 Математика 46

092913 0133 46146 Математика 46

092913 0133 46147 Математика 46

-2

1 

2 

0 

092913 0133 46148 Математика 46

4 

3

4 

4 

092913 0133 46149 Математика 46

2 

2 

3 

3 

092913 0133 46150 Математика 46

5 

4 

0 

-1 

092913 0133 46151 Математика 46

6 

5 

2 

1 

Показатель пессимизма 092913 0133 46152 Математика 46

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

1)

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

Выбирается 092913 0133 46153 Математика 46

092913 0133 46154 Математика 46

 

-2

1 

2 

0 

4 

3

4 

4 

2 

2 

3 

3 

5 

4 

0 

-1 

6 

5 

2 

1 

 

092913 0133 46155 Математика 46, 092913 0133 46156 Математика 46.

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

Критерий Гурвица с показателем пессимизма 092913 0133 46158 Математика 46

092913 0133 46159 Математика 46

 

 

092913 0133 46160 Математика 46

092913 0133 46161 Математика 46

092913 0133 46162 Математика 46

092913 0133 46163 Математика 46

2

-2

092913 0133 46164 Математика 46

092913 0133 46165 Математика 46

4

3

092913 0133 46166 Математика 46

092913 0133 46167 Математика 46

3

2

092913 0133 46168 Математика 46

092913 0133 46169 Математика 46

5

-1

092913 0133 46170 Математика 46

092913 0133 46171 Математика 46

6 

1 

092913 0133 46172 Математика 46

 

092913 0133 46173 Математика 46

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

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

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

092913 0133 46177 Математика 46

 

092913 0133 46178 Математика 46

092913 0133 46179 Математика 46 , 092913 0133 46180 Математика 46

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

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

 

092913 0133 46182 Математика 46

092913 0133 46183 Математика 46, 092913 0133 46184 Математика 46

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

2)

092913 0133 46186 Математика 46-нижняя цена игры. 092913 0133 46187 Математика 46.

092913 0133 46188 Математика 46-верхняя цена игры 092913 0133 46189 Математика 46

092913 0133 46190 Математика 46, 092913 0133 46191 Математика 46

 

092913 0133 46192 Математика 46, 092913 0133 46193 Математика 46

Ответ: 092913 0133 46194 Математика 46, 092913 0133 46195 Математика 46 следовательно гарантирующих стратегий для игроков A и B нет.

3)

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

 

092913 0133 46196 Математика 46

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

092913 0133 46197 Математика 46

Ответ: 092913 0133 46198 Математика 46.

4)

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

092913 0133 46199 Математика 46,

092913 0133 46200 Математика 46

 

092913 0133 46201 Математика 46

Найдем т. M решим уравнение 092913 0133 46202 Математика 46

092913 0133 46203 Математика 46. 092913 0133 46204 Математика 46

Тогда 092913 0133 46205 Математика 46

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

092913 0133 46207 Математика 46.

5)

092913 0133 46208 Математика 46

092913 0133 46209 Математика 46

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

092913 0133 46210 Математика 46

092913 0133 46211 Математика 46

Б.п.

092913 0133 46212 Математика 46

092913 0133 46213 Математика 46

092913 0133 46214 Математика 46

092913 0133 46215 Математика 46

С.ч.

092913 0133 46216 Математика 46

3

4

1

0

1

092913 0133 46217 Математика 46

5

1

0

1

1

индексная

строка 

-1

-1

0

0

0

 

 

 

 

 

 

092913 0133 46218 Математика 46

Б.п. 

092913 0133 46219 Математика 46

092913 0133 46220 Математика 46

092913 0133 46221 Математика 46

092913 0133 46222 Математика 46

С.ч. 

092913 0133 46223 Математика 46

0

092913 0133 46224 Математика 46

1

092913 0133 46225 Математика 46

092913 0133 46226 Математика 46

092913 0133 46227 Математика 46

1

092913 0133 46228 Математика 46

0

092913 0133 46229 Математика 46

092913 0133 46230 Математика 46

индексная

строка 

0

092913 0133 46231 Математика 46

0

092913 0133 46232 Математика 46

092913 0133 46233 Математика 46

 

 

 

 

 

092913 0133 46234 Математика 46

Б.п. 

092913 0133 46235 Математика 46

092913 0133 46236 Математика 46

092913 0133 46237 Математика 46

092913 0133 46238 Математика 46

С.ч. 

092913 0133 46239 Математика 46

0

1

092913 0133 46240 Математика 46

092913 0133 46241 Математика 46

092913 0133 46242 Математика 46

092913 0133 46243 Математика 46

1

0

092913 0133 46244 Математика 46

092913 0133 46245 Математика 46

092913 0133 46246 Математика 46

индексная

строка 

0 

0 

092913 0133 46247 Математика 46

092913 0133 46248 Математика 46

092913 0133 46249 Математика 46

 

 

 

 

 

092913 0133 46250 Математика 46

092913 0133 46251 Математика 46

092913 0133 46252 Математика 46

Ответ: оптимальная смешанная стратегия игрока A равна 092913 0133 46253 Математика 46, цена игры 092913 0133 46254 Математика 46.

 

Задача 5.

Вариант 2.

 

Задан взвешенный граф. Требуется найти кратчайший путь из вершины 092913 0133 46255 Математика 46в вершину 092913 0133 46256 Математика 46методом динамического программирования на графе.

092913 0133 46257 Математика 46

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

 

092913 0133 46258 Математика 46092913 0133 46259 Математика 46

092913 0133 46260 Математика 46

092913 0133 46261 Математика 46

092913 0133 46262 Математика 46

092913 0133 46263 Математика 46

092913 0133 46264 Математика 46

092913 0133 46265 Математика 46

092913 0133 46266 Математика 46Следовательно, кратчайший путь 092913 0133 46267 Математика 46 и он равен 9.

 

Ответ: путь 092913 0133 46268 Математика 46 длиной 9.

<

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

MAXCACHE: 1.06MB/0.00140 sec

WordPress: 22.73MB | MySQL:118 | 2,612sec