Приобретение навыков решения задач линейного программирования симплекс-методом и M-методом

– число переменных. Ранг матрицы системы r = 2, так как, например, определитель, составленный из коэффициентов системы при переменных x1 и x2, не равен нулю. Следовательно, общее решение этой системы содержит две базисных переменных и n–r=5–2=3 свободных переменных.
Общее решение системы можно получить методом Жордана-Гаусса. При этом в случае нашей системы достаточно будет из первого уравнения вычесть второе, а само второе уравнение оставить без изменений:
x1 x2 x3 x4 x5 x*
x1 x2 x3 x4 x5 x*
9 -3 -7 1 4 14 ⇒ 8 -4 -8 0 4 12
1 1 1 1 0 2
1 1 1 1 0 2
Получили две базисных переменных x4 и x5 и три свободных x1, x2 и x3:
x5=4–13x1+43x2+83x3
x4=2–x1–x2–x3
Наша целевая функция z(x)=1+x1+x2 выражена через свободные переменные.
Записываем наше начальное допустимое базисное решение в стандартной форме:
x5=3-2x1+2x2+2x3
x4=2-x1-x2-x3
xj ≥ 0; j = 1,…,5;
Z(x)=1– (–x1–2x2).
Отсюда имеем: X1=(0;0;0;2;3); Z(X1)=1.
5.3.3. Начальное допустимое базисное решение найти удалось. Находим оптимальное решение.
Так как в скобках у целевой функции нет положительных коэффициентов, то найденное решение улучшить нельзя. Следовательно, оно является оптимальным:
x5=3-2x1+2x2+2x3
x4=2-x1-x2-x3
xj ≥ 0; j = 1,…,5;
Z(x)=1– (–x1–2x2)
Xmi =(0;0;0;2;3); zmin=1 .  
5.3.4. Находим оптимальное решение задачи в Excel.
5.3.4.1. Создаем представление задачи в Excel.
Табличная модель задачи имеет следующий вид:
5.3.4.2. Проверка формул табличной модели:
5.3.4.3. Получение оптимального решения задачи с помощью надстройки “Поиск решения”.
Обращаемся к надстройке “Поиск решения” и устанавливаем необходимые параметры:
После нажатия кнопки “Найти решение” получаем сообщение об успешном решении задачи:
После нажатия кнопки Ok получаем окончательное решение нашей задачи:
5.3.5. Сравнение полученных результатов и выводы.
Результат, полученный с помощью надстройки MS Excel “Поиск решения”, совпал с тем, который был получен ранее в п.5.3.3.
5.3.6. Решение задачи M-методом.
5.3.6.1. Условие исходной задачи линейного программирования:
z(x)=1+x1+2x2→min
9x1-3x2-7x3+x4+4x5=14x1+x2+x3+x4=2x1,x2,x3,x4,x5≥0
5.3.6.2. Для данной канонической задачи линейного программирования составляем M-задачу.
Сначала записываем систему уравнений в следующем виде:
14–(9x1–3x2–7x3+x4+4x5)=0;
2–(x1+x2+x3+x4)=0
Рассматриваем вспомогательную каноническую задачу линейного программирования:
14–(9x1–3x2–7x3+x4+4x5)=ξ1;
2–(x1+x2+x3+x4)=ξ2;
xj ≥ 0; j=1,…,5; ξ1≥0; ξ2≥0;
G(X)=1+x1+2x2+M(ξ1+ξ2)  min.
Здесь М – некоторое достаточно большое положительное число