Вопросы и задания для самоконтроля
1.Какая задача оптимизации называется задачей линейного программирования?
2.Дать определение общей задачи линейного программирования.
3.Дать определение канонической задачи линейного программирования.
4.Описать алгоритм сведения общей задачи к задаче в канонической форме линейного программирования. Привести пример.
5.Какие задачи линейного программирования можно решить графически?
6.Описать алгоритм графического решения задачи линейного программирования.
7.Дать определение плана и оптимального плана задачи линейного программирования.
8.Какую задачу линейного программирования можно решить с помощью симплекс-метода?
9.Дать определение опорного плана задачи линейного программирования.
10.Сформулировать признак оптимальности опорного плана для задачи линейного программирования симплексным методом.
11. Показать, что если для некоторого k < 0 среди чисел aik (i =1, ..., m) нет положительных, то целевая функция задачи линейного программирования в канонической форме (8.15) − (8.17) не ограничена на множестве ее планов.
12.Сформулировать правила пересчета ограничений задачи линейного программирования при переходе к новому базису. Привести пример.
13.Всегда ли решение задачи линейного программирования, записанной в канонической форме (8.15) − (8.17), может быть найдено за конечное число шагов?
14.Каким образом можно улучшить приведенный алгоритм решения задачи линейного программирования симплексным методом?
15.В каких случаях для решения задачи линейного программирования необходимо добавлять искусственные переменные? Привести пример.
16. |
Показать, что для метода искусственного базиса величины F k |
и |
j |
зависят |
|
0 |
|
|
|
от параметра M . |
|
|
|
|
17. |
В каких случаях метод искусственного базиса не даст решения задачи |
|||
линейного программирования? |
|
|
|
|
186
18.Описать алгоритм расчета задачи линейного программирования для метода искусственного базиса.
19.Решить задачи линейного программирования графическим методом
Задача 1.
f (x1 , x2 ) = −x1 − 4x2 |
→ min, |
||
x1 ≤ 2, x1 + 2x2 ≥ 2, |
|||
x2 ≤ 2, x1 + x2 ≤ 3, |
|
||
x1 , x2 ≥ 0. |
|
||
Ответ: x = (1, 2)T ; f = −9. |
|
|
|
Задача 2. |
|
|
|
f (x1 , x2 ) = −x1 − x2 |
→ min, |
||
x1 |
≤ 3, |
x2 ≤ 2, |
|
x1 |
+ x2 |
≤1, |
|
x1 , x2 ≥ 0.
Ответ: Бесконечное множество решений: x = (α, 1 −α)T , α [0, 1]; f =1. Задача 3.
|
f (x1 , x2 ) = −2x1 − x2 |
→ min, |
|
2x1 + x2 ≥1, 3x1 − x2 ≥ −1, |
|
|
x1 − 4x2 ≤ 2, |
|
|
x1 , x2 ≥ 0. |
|
Ответ: Нет решений. |
|
|
Задача 4. |
|
|
|
f (x1 , x2 ) = −x1 −3x2 |
→ min, |
|
2x1 + x2 ≤ 2, x1 − x2 ≥ 0, |
|
|
x1 − x2 ≤1, |
|
|
x1 , x2 ≥ 0. |
|
Ответ: |
x = (2 3, 2 3)T ; f = −8 3. |
|
Задача 5. |
|
|
|
f (x1 , x2 ) = x1 − 2x2 |
→ min, |
|
− x1 + x2 ≤ 0, 2x1 + x2 ≤ 3, |
|
|
x1 − x2 ≤1, |
|
|
x1 , x2 ≥ 0. |
|
Ответ: |
x = (1, 1)T ; f = −1. |
|
187