Линейное программирование. Задача линейного программирования (ЗЛП), страница 7

Видим, что значение целевой функции не изменится:

Но, как было показано в разделе 5.6, если целевая функция достигает экстремума более чем в одной крайней точке, то она достигает того же экстремума в любой точке, являющейся их выпуклой линейной комбинацией.

Следовательно, если экстремум достигается в точках x₁* и x₂*, то есть  z(x₁*) = z(x₂*), то тот же экстремум достигается также и в любой точке

x = l₁x₁* + l₂x₂*, где  l₁ + l₂ = 1.

Отсутствие решения.

Если при поиске максимума в индексной строке симплексной таблицы имеется отрицательное число ∆_j<0, но в этом столбце нет ни одного положительного элемента а_ij, то целевая функция не ограничена сверху и задача не имеет решения.

Для доказательства этого утверждения перепишем уравнения (6.7) и (6.8) и рассмотрим их.

,                                                  

Можно сколько угодно увеличивать х_j, отчего будет неограниченно расти значение z. При этом нет опасности, что х_i станет отрицательной, так как коэффициент а_ij при х_j не положительный. Все это верно для других х.

Аналогичное утверждение справедливо и для случая поиска минимума.

Если при поиске минимума в индексной строке симплексной таблицы имеется положительное ∆_j>0, но в этом столбце нет ни одного положительного элемента а_ij, то целевая функция не ограничена снизу и задача не имеет решения.

Доказательство его аналогично предыдущему.

Контрольные вопросы

10.  Как привести ЗЛП к канонической форме.

11.  Как привести ЗЛП к предпочтительному виду.

12.  Определение выпуклого множества и его свойства.

13.  Какое место в многограннике планов занимает план вида (х₁; х₂;…; х_m; 0;…; 0) и почему?

14.  Для чего систему ограничений приводят к каноническому предпочтительному виду?

15.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j £  b_i в задаче на поиск максимума?

16.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j £  b_i в задаче на поиск минимума?

17.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j ³ b_i в задаче на поиск максимума?

18.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j ³ b_i в задаче на поиск минимума?

19.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j = b_i в задаче на поиск максимума?

20.  Как привести к предпочтительному виду систему ограничений Sa_ij x_j = b_i в задаче на поиск минимума?

21.  Требования к системе ограничений, чтобы можно было составить начальный опорный план.

22.  Что такое начальный опорный план, как он выглядит?

23.  Как составляется начальный опорный план?

24.  При поиске максимума что в симплексной таблице является признаком оптимальности плана?

25.  При поиске минимума что в симплексной таблице является признаком оптимальности плана?

26.  Как найти ключевое число в симплекс-таблице?

27.  Что такое ключевой столбец?

28.  Что такое ключевая строка?

29.  Как выглядит правило преобразования чисел симплексной таблицы?

30.  О чем говорит число нулей (> m) в индексной строке?

31.  О чем говорит число нулей (< m) в индексной строке?

7. Примеры решения задач линейного программирования.

7.1. Пример решения ЗЛП с дополнительными переменными

Имеется три вида сырья в следующих количествах: b₁ = 54; b₂ = 63; b₃ = 5 единиц.

Можно изготовить 3 вида продукта: П₁, П₂, П₃. Прибыль с единицы продукта: с₁ = 9; с₂ = 14;  с₃ = 5. Количество сырья а_ij, необходимое для изготовления единицы продукта, показано в таблице.

Виды продукта	П1	П2	П3	Виды и имеющиеся количества сырья
Количества продукта	х1	х2	х3
Прибыль с единицы продукта	с1 = 9	с2 = 14	с3 = 5
Количество аij сырья для изготовления единицы продукта	9	4	4	b1 = 54
	9	5	5	b2 = 63
	0	1	0	b3 = 5

Полная прибыль равна z = 9x₁ + 14x₂ + 5x₃, где x₁, x₂, x₃ -количества выпускаемого продукта П₁, П₂, П₃. Необходимо составить такой план выпуска продукции, который дает максимальную прибыль.