Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
СОДЕРЖАНИЕ
Перечень типовых задач 3
Примерные тестовые задания 4
(для проведения контроля в форме бланкового тестирования в периоды рубежных срезов)
Указания к решению задач 6
ПЕРЕЧЕНЬ ТИПОВЫХ ЗАДАЧ
|
№ п/п |
Наименование раздела дисциплины |
Типовые задачи |
|
1 |
Линейное программирование |
1. Составить математическую модель задачи оптимизации. 2. Решить задачу линейного программирования графическим методом, симплекс-методом, М-методом. 3. Указать возможные методы решения задачи линейного программирования. 4. Решить прямую и двойственную задачи линейного программирования, установит из взаимосвязь. 5. Решить транспортную задачу закрытого типа, открытого типа, с ограничениями. |
|
2 |
Нелинейное программирование |
1. Решить задачу нелинейного программирования графическим методом, методом множителей Лагранжа. 2. Решить задачу выпуклого программирования методом штрафных функций. |
|
3 |
Динамическое программирование |
1. Составить оптимальный план ежегодного распределения средств между предприятиями на некоторый период времени при определенных условиях. |
|
4 |
Теория игр |
1. Упростить платежную матрицу посредством исключения доминируемых стратегий. 2. Установить наличие седловых элементов. 3. Решить графически игры с матрицами, предварительно упростив. 4. Решить матричные игры, заданные платежными матрицами, сведя их к парам двойственных задач линейного программирования. |
|
5 |
Теория массового обслуживания |
1. Экономическая эффективность n типов электростанций зависит от к состояний природы задана матрицей. Положить состояния природы равновероятными. 2. Предприятие может выпускать n видов продукции, получая при этом прибыль, зависящую от спроса. Спрос, в свою очередь, может принимать одно из к состояний. Элементы матрицы характеризуют прибыль, которую получит предприятие при выпуске i-ой продукции и j-состоянии спроса. Определить оптимальные пропорции выпускаемой продукции, считая состояние спроса полностью неопределенным, гарантирую при этом среднюю величину прибыли при любом состоянии спроса. |
ПРИМЕРНЫЕ ТЕСТОВЫЕ ЗАДАНИЯ
(для проведения контроля в форме бланкового тестирования в периоды рубежных срезов)
Задания закрытой формы (с одиночным вариантом выбора):
(разделы 1, 2, 4; знание)
1. Укажите, какой из следующих этапов (не) является обязательным в процессе исследования задачи (указан раздел) методом ________:
(разделы 1, 2; знание)
2. Укажите, какое из следующих действий (не) может быть использовано в процессе исследования задачи (не)линейного программирования графическим методом:
(разделы 1, 2, 3, 4, 5; знание)
3. Какое из следующих утверждений (не)верно:
(раздел 1; понимание)
4. Какая из следующих задач линейного программирования является двойственной к следующей задаче:
(раздел 1; понимание)
5. Установите, какой из планов (не) может быть получен ни одним из следующих методов: аппроксимации Фогеля, наименьшей стоимости, метод северо-западного угла в задаче:
(раздел 1; понимание)
6. Какая из следующих таблиц соответствует первому этапу решения следующей транспортной задачи: Имеются m пунктов поставки однородного груза и n пунктов потребления . В пунктах груз находится соответственно в количествах у. е. В пункты требуется доставить соответственно у. е. груза. Стоимость перевозки единицы груза (с учетом расстояний) из в определена матрицей. При этом запретить поставки из в , а также из в доставить не менее (не более) единиц груза.
(раздел 4; понимание)
7. Упростить посредством удаления доминируемых стратегий следующую платежную матрицу:
(раздел 4; понимание)
8. Какая из упорядоченных троек элементов является решением игры, заданной платежной матрицей:
(раздел 5; знание)
9. Какая из следующих матриц (не) является матрицей риска для платежной матрицы:
(разделы 3,4,5; знание)
10. Динамическое планирование (личный ход, стратегия, поток событий, … ) - это:
(раздел 5; знание)
11. Какое их следующих свойств не относится к известным свойствам потока событий:
Задания закрытой формы (на установление соответствия):
(раздел 1; понимание)
12. Установите соответствие между математическими моделями задач линейного программирования и их геометрическими интерпретациями:
(раздел 1; понимание)
13. Установите соответствие между опорными планами транспортной задачи и методами их получения:
(разделы 1, 2, 3, 5; понимание)
14. Установите соответствие между экономическими задачами и разделами, в которых описываются методы из решения:
(раздел 5; знание)
15. Установите соответствие между критериями оптимальности решения статистической игры и формулами:
Задания закрытой формы (с несколькими вариантами выбора):
(раздел 1; понимание)
16. Какую из следующих задач линейного программирования нельзя решить графическим способом:
(разделы 1, 2; понимание)
17. Какие из следующих наборов значений переменных лежат в области допустимых решений следующей задачи:
(раздел 1; понимание)
18. Известно, что в результате решения транспортной задачи получено следующее значение целевой функции. Какие из следующих планов (не) являются оптимальными. Стоимость перевозки единицы груза (с учетом расстояний) из в определена матрицей:
(раздел 2; знание)
19. К градиентным методам (не) относятся:
(разделы 1, 2, 3, 4, 5; знание)
20. Какие из следующих разделов исследования операций не существуют:
По результатам представленного текущего контроля студенты могут набрать до 60-и баллов. К промежуточной аттестации допускаются студенты, набравшие в течение семестра 30 баллов и выше.
УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ
Решить задачу ЛП, используя графический метод.
Найти максимальное (минимальное значение функции) при условиях .
Решение.
Приведем систему ограничений к виду, пригодному для использования графического метода. Для этого преобразуем задачу из канонической формы в стандартную.
Найдем многоугольник решений полученной задачи – область допустимых значений:
|
5 |
0 |
|
|
0 |
10 |
|
-3 |
0 |
|
|
0 |
2 |
|
4 |
0 |
|
|
0 |
2 |
ABCD – область допустимых решений новой задачи.
Построим вектор с координатами и будем двигать прямую в направлении этого вектора.
B является точкой выхода из области ABCD. Поскольку B – точка пересечения прямых (1) и (2), то для нахождения ее координат необходимо решит систему . Таким образом, решение является оптимальным .
. Следовательно, решение исходной задачи .
Найдем теперь , где с заданной системой ограничений (*). C (с координатами (5;0)) является точкой выхода из области ABCD. Таким образом, решение является оптимальным , а, значит, .
Решить задачу ЛП симплекс-методом.
Найти максимуму функции при ограничениях Решим задачу симплекс-методом.
Решение: Перепишем условие задачи в векторной форме: , где .
Среди векторов векторы единичные. Примем их за базисные.
Составим симплексную таблицу 1.
z= 3x1+ 0x2+ 0x3+ 0x4+ 2x5+ (-5)x6
|
i |
Базис |
3 |
0 |
0 |
0 |
2 |
-5 |
||
|
1 |
0 |
34 |
2 |
1 |
0 |
0 |
-3 |
5 |
|
|
2 |
0 |
28 |
4 |
0 |
1 |
0 |
2 |
-4 |
|
|
3 |
0 |
24 |
-3 |
0 |
0 |
1 |
-3 |
6 |
|
|
m+1 |
0 |
-3 |
0 |
0 |
0 |
-2 |
5 |
Найдем разрешающий элемент в таблице 1.
Поскольку , то найдем по следующим формулам:
.
. Таким образом, разрешающий будем выбирать из элементов . Для этого найдем минимум из произведений :
. Тогда разрешающим будет элемент . Следовательно, вместо базисного вектора в таблице 1 базисным становится вектор в таблице 2.
|
i |
Базис |
3 |
0 |
0 |
0 |
2 |
-5 |
||
|
1 |
0 |
34 |
2 |
1 |
0 |
0 |
-3 |
5 |
|
|
2 |
0 |
28 |
4 |
0 |
1 |
0 |
2=a25 |
-4 |
|
|
3 |
0 |
24 |
-3 |
0 |
0 |
1 |
-3 |
6 |
|
|
m+1 |
0 |
-3 |
0 |
0 |
0 |
-2 |
5 |
Построим симплексную таблицу 2, опираясь на разрешающий элемент и следующие правила:
Правило 1: Все элементы k-ой строки (строки в которой находится разрешающий элемент ), начиная со столбца , делятся на разрешающий элемент ;
Правило 2: Все элементы столбца заменяются нулями, кроме ;
Правило 3: Любой элемент таблицы 2 вычисляется по правилу прямоугольника:
;
Правило 4: (m+1)-строка вычисляется аналогично: .
В таблице 2 базисными будут векторы .
Таблицу 2.
|
i |
Базис |
3 |
0 |
0 |
0 |
2 |
-5 |
||
|
1 |
0 |
76 |
8 |
1 |
3/2 |
0 |
0 |
-1 |
|
|
2 |
2 |
14 |
2 |
0 |
1/2 |
0 |
1 |
-2 |
|
|
3 |
0 |
76 |
3 |
0 |
0 |
1 |
0 |
0 |
|
|
m+1 |
28 |
1 |
0 |
1 |
0 |
0 |
1 |
Вычислим элементы в столбце : Вычислим элементы в столбце :
Вычислим элементы в столбце : Вычислим элементы в столбце :
Опорный план найден, так как в (m+1)-строке среди нет отрицательных.
, .
Замечание 1. После конечного числа шагов получим оптимальный план или докажем отсутствие такового. Оптимальный план отсутствует, если некоторое , но среди чисел нет положительных (т.е. целевая функция не ограничена на множестве ее планов).
Замечание 2. Задача по нахождению сводится к нахождению . Для этого достаточно изменить коэффициенты целевой функции на противоположные () и решать задачу по нахождению максимума функции, при этом ограничения оставить прежними.
Решить задачу ЛП М-методом.
Найти максимуму функции при ограничениях Решим задачу методом искусственного базиса (М-методом).
Решение: Запишем систему ограничений в канонической форме. Получим
или . Поскольку в системе 3 уравнения, то и базисных векторов также должно быть 3. Один из них уже известен, это вектор . И других базисных векторов нет. Поэтому добавим их искусственно во второе и третье уравнения системы. Получим . Таким образом, мы перешли к расширенной задаче: при ограничениях (*). Рассмотрим векторы
.
Среди векторов векторы являются базисными.
Симплексная таблица при этом методе содержит еще и (m+2)-строку, куда записывают слагаемое из , содержащее M, а в (m+1)-строку – другое слагаемое из этой разности.
Составим симплексную таблицу 1.
Т = 5x1+ 2x2+ (-1)x3+ 0x4+ 0x5+ (-М)x6+ (-М)х7
|
i |
Базис |
5 |
2 |
-1 |
0 |
0 |
-М |
-М |
||
|
1 |
0 |
5 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
2 |
-М |
6 |
3 |
2 |
1 |
0 |
0 |
1 |
0 |
|
|
3 |
-М |
1 |
5 |
3 |
4 |
0 |
-1 |
0 |
1 |
|
|
m+1 |
0 |
-5 |
-2 |
1 |
0 |
0 |
0 |
0 |
||
|
m+2 |
-7 |
-8 |
-5 |
-5 |
0 |
1 |
0 |
0 |
Найдем разрешающий элемент в таблице 1 по (m+2)-строке.
Найдем по следующим формулам:
.
. Таким образом, разрешающий будем выбирать из элементов . . Тогда разрешающим будет элемент . Следовательно, вместо базисного вектора в таблице 1 базисным становится вектор в таблице 2, причем искусственный вектор, исключенный из базиса, из таблицы удаляется.
Построим симплексную таблицу 2, опираясь на разрешающий элемент и следующие правила:
Правила 1-3 такие же как в предыдущем примере.
Правило 4: (m+1) и (m+2)-строки вычисляется аналогично: .
Правило 5: Процесс продолжается до тех пор пока из базиса не будут исключены все искусственные векторы, после чего переходят к (m+1)-строке. Удаленные из базиса искусственные векторы также исключаются и из таблицы.
Правило 6: Если не все искусственные векторы исключены из базиса, а в (m+2)-строке нет отрицательных, то расширенная и исходная задачи решений не имеют.
В таблице 2 базисными будут векторы .
Таблица 2.
|
i |
Базис |
5 |
2 |
-1 |
0 |
0 |
-М |
||
|
1 |
0 |
14/3 |
1/3 |
0 |
-1/3 |
1 |
1/3 |
0 |
|
|
2 |
-М |
16/3 |
-1/3 |
0 |
-5/3 |
0 |
2/3 |
1 |
|
|
3 |
2 |
1/3 |
5/3 |
1 |
4/3 |
0 |
-1/3 |
0 |
|
|
m+1 |
2/3 |
-5/3 |
0 |
11/3 |
0 |
-2/3 |
0 |
||
|
m+2 |
-16/3 |
1/3 |
0 |
5/3 |
0 |
2/3 |
0 |
Вычислим элементы в столбце : Вычислим элементы в столбце :
Вычислим элементы в столбце : Вычислим элементы в столбце :
Поскольку в (m+2)-строке нет отрицательных (начиная со столбца ), то задача новая, а, значит и исходная, оптимального плана не имеет.
Замечание 1. После конечного числа шагов получим оптимальный план или докажем отсутствие такового. Оптимальный план отсутствует, если некоторое , но среди чисел нет положительных (т.е. целевая функция не ограничена на множестве ее планов).
Замечание 2. Задача по нахождению сводится к нахождению . Для этого достаточно изменить коэффициенты целевой функции на противоположные () и решать задачу по нахождению максимума функции, при этом ограничения оставить прежними.
Решить задачу транспортную задачу ЛП.
|
|
Мощность (т) |
||||
|
2 |
3 |
9 |
7 |
20 |
|
|
3 |
4 |
6 |
1 |
16 |
|
|
5 |
1 |
М |
2 |
14 |
|
|
4 |
5 |
8 |
1 |
22 |
|
|
потреб. (т) |
16 |
18 |
12 |
10 |
72 61 |
модель задачи открытая. Запасы превышают потребности, следовательно, необходимо ввести искусственного потребителя .
Поскольку из в перевозка груза запрещена, следует заблокировать клетку ,. Для этого будем считать , где - сколь угодно большое число.
Замечание. Если , то в любом опорном плане, в том числе и в оптимальном. В противном случае затраты на перевозку всех грузов не будут минимизированы, так как появится слагаемое и значение целевой функции будет сколь угодно большим, что не соответствует требованию минимизации её значения.
|
|
Мощность (т) |
||||||
|
2 |
3 |
9 |
7 |
20 |
0 |
7 |
|
|
3 |
4 |
6 |
1 |
16 |
0 |
М |
|
|
5 |
1 |
М |
2 |
14 |
0 |
2 |
|
|
4 |
5 |
8 |
1 |
22 |
0 |
1 |
|
|
потреб. (т) |
16 |
18 |
12 |
10 |
72 61 |
11 |
15-10=5 |
1. Заполним таблицу по методу наименьшей стоимости.
1 шаг
Первой заполняется клетка , так как наименьший из всех тарифов. В этой ячейке ставим число 28, так как . Тогда строка оказывается заполненной полностью.
2 шаг
Заполняем клетку , так как наименьший из всех тарифов в незаполненных клетках. Заметим, что также равно 2 и клетка выбрана произвольно. В этой ячейке ставим число 17, чтобы окончательно заполнить столбец .
3 шаг
Первой заполняется клетка , так как наименьший из всех тарифов в незаполненных клетках. В этой ячейке ставим число 27 так как . Тогда строка оказывается заполненной полностью.
4 шаг
Заполняем клетку , так как наименьший из всех тарифов в незаполненных клетках. В этой ячейке ставим число 15, чтобы окончательно заполнить строку .
5 шаг
В ячейке ставим число 22, чтобы окончательно заполнить столбец .
6 шаг
В ячейке ставим число 13, чтобы окончательно заполнить столбец .
Опорный план: , а значение функции равно
.
2. Заполним таблицу методом аппроксимации Фогеля.
|
|
Мощность (т) |
Потенциалы постав |
||||
|
2 17 (2 шаг) |
3 15 (6 шаг) |
4 X (4 шаг) |
32 |
1,1,1,1,В |
||
|
1 28 (1 шаг) |
5 X (1 шаг) |
3 X (1 шаг) |
28 |
2,В |
||
|
6 X (2 шаг) |
4 22 (5 шаг) |
2 5 (4 шаг) |
27 |
2,2,2,4,4,В |
||
|
7 X (2 шаг) |
8 X (3 шаг) |
5 35 (3 шаг) |
35 |
2,2,3,В |
||
|
потреб. (т) |
45 |
37 |
40 |
122 122 |
||
|
1,4,В |
1,1,1,1,1,3В |
1,2,2,2,В |
||||
|
Потенциалы потреб |
1 шаг
Найдем разности между минимальными тарифами в столбцах и строках и выберем максимум. . Заметим, что минимум из тарифов выбирается из столбцов и строк, которым соответствует . В этой ячейке ставим число 28, так как . Тогда строка оказывается заполненной полностью.
2 шаг
Найдем разности между минимальными тарифами в столбцах и строках, не учитывая заполненные клетки, и выберем максимум. (минимум из тарифов выбирается в столбце ). В этой ячейке ставим число 17, чтобы окончательно заполнить столбец .
3 шаг
Найдем разности между минимальными тарифами в столбцах и строках, не учитывая заполненные клетки, и выберем максимум. (минимум из тарифов выбирается в строке ). В этой ячейке ставим число 35, так как . Тогда строка оказывается заполненной полностью.
4 шаг
Найдем разности между минимальными тарифами в столбцах и строках и выберем максимум. . Заметим, что минимум из тарифов выбирается из столбцов и строк, которым соответствует . В этой ячейке ставим число 5, чтобы окончательно заполнить столбец .
5 шаг
Найдем разности между минимальными тарифами в столбцах и строках и выберем максимум. . В строке не заполнена только ячейка . В этой ячейке ставим число 22, чтобы окончательно заполнить строку .
6 шаг
В ячейке ставим число 15, чтобы окончательно заполнить таблицу.
Опорный план: , а значение функции равно
.
Составляя опорный план двумя методами, получили что стоимость перевозки при плане, полученном вторым методом, меньше, более того, этот план окажется минимальным. Но метод потенциалов будем применять к опорному плану, полученному первым методом.
Опорный план , .
Заполненных клеток в опорном плане должно быть 4+3-1=6. Заполнено тоже 6.
Замечание: должно быть равно числу заполненных клеток в таблице. Если число заполненных клеток окажется меньше, то в недостающее количество клеток необходимо вписать нули и рассматривать их в качестве заполненных.
Составим систему потенциалов по заполненным клеткам.
Определяем потенциалы. Пусть . Тогда Решение системы будет следующим:
Проверим условие оптимальности: в свободных клетках . Убеждаемся, что в клетке это условие не выполнено . Рассмотрим цикл, одна из вершин которого лежит в клетке .
|
|
Мощность (т) |
Потенциалы постав |
|||
|
2 17 |
3 15 |
4 X |
32 |
||
|
1 28 |
5 X |
3 X |
28 |
||
|
6 X |
4 X + |
2 27 - |
27 |
||
|
7 X |
8 22 - |
5 13 + |
35 |
||
|
потреб. (т) |
45 |
37 |
40 |
122 122 |
|
|
Потенциалы потреб |
Определение. Циклом называется замкнутая ломаная, все вершины которой лежат в заполненных клетках, кроме одной, расположенной в свободной клетке, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-ч вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.
Вычислим - минимум из чисел в отрицательных клетках цикла. . Таким образом делаем сдвиг по циклу на число 22.
Определение. Сдвигом по циклу называется процесс вычитания из отрицательных клеток числа и прибавления этого числа в положительных клетках.
Получим новый план, оптимальность которого вновь предстоит проверить методом потенциалов.
.
, где
.
Составим систему потенциалов по заполненным клеткам.
Определяем потенциалы. Пусть . Тогда Решение системы будет следующим:
Проверим условие оптимальности: в свободных клетках . Убеждаемся, что во всез незаполненных клетках это условие выполнено. Таким образом, найденный план является опорным, а (ден.ед).
Решить задачу транспортную задачу ЛП.
Задача 1. Найти решение игры:
1) 2)
Решение.
1) Найдем нижнюю цену игры (Назовем нижней ценой игры или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В):
Найдем верхнюю цену игры (назовем верхней ценой игры или минимаксом. Это минимальный гарантированный проигрыш игрока В):
Таким образом, . В случае совпадения нижней и верхней цены игры существует седловой элемент (в данной задаче это элемент ) и задача разрешима в чистых стратегиях. Придерживаясь чисто второй стратегии, первый игрок обеспечивает себе выигрыш, не меньший 5; второй игрок, применяя чистую третью стратегию, проигрывает не более 5. Обе стратегии и являются оптимальными для первого и второго игроков, при этом цена игры , т.е. тройка - оптимальное решение игры.
2) Найдем нижнюю цену игры (Назовем нижней ценой игры или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В):
Найдем верхнюю цену игры (назовем верхней ценой игры или минимаксом. Это минимальный гарантированный проигрыш игрока В):
Таким образом, . В случае несовпадения нижней и верхней цены игры седловой элемент отсутствует и задача разрешима только в смешанных стратегиях.
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В этом случае можно получить оптимальное решение, чередуя чистые стратегии.
Смешанной стратегией игрока А называется применение чистых стратегий А1, А2, …, Аm c вероятностями u1, u2, …, um.
Обычно смешанную стратегию первого игрока обозначают как вектор: U = (u1, u2, …, um), а стратегию второго игрока как вектор: Z = (z1, z2, …, zm).
Очевидно, что:
Чистые стратегии можно считать частным случаем смешанных и задавать вектором, в котором единица соответствует чистой стратегии.
Теорема Неймана. Каждая конечная игра с нулевой суммой имеет решение в смешанных стратегиях.
Пусть U* = (, , ..., ) и Z* = (, , ..., ) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с вероятностью, отличной от нуля, то она называется активной.
Теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.
ЗАМЕЧАНИЕ. Эта теорема имеет большое практическое значение - она дает конкретные модели для нахождения оптимальных стратегий при отсутствии седловой точки.
Упростим платежную матрицу:
Исключим 4 - ую строку матрицы, так как ее элементы не превосходят элементы 2-ой строки (4 – ая доминируемая 2- ой). Получим
Столбцы 1 и 3 дублируют друг друга, исключим 3. Получим
Элементы 3 – его столбца в новой матрице не меньше элементов 1 - ого и 2 – ого столбцов, следовательно, он доминируем и мы его исключаем. Получим
.
Найдем координаты точки М (точка пересечения прямых A1A'1 и A3A'3).
Пусть
Прямая A1A'1 (проходит через точки с координатами ((0,7) и (1,6)):
Прямая A3A'3 (проходит через точки с координатами ((0,5) и (1,6)):
Решим систему
.
.
Зная, что М - точка пересечения прямых A1A'1 и A3A'3, можем найти оптимальную стратегию при помощи матрицы (). Для нахождения составим систему:
Решение задачи: .
PAGE \* MERGEFORMAT 9
EMBED Equation.3
EMBED Equation.3
(1)
2)
(3)
A
B
C
D
x
A
B
C
D
A3
A4
B2
B1
y
A2
A1
A1’
A2’
A3’
A4’
M