23. М-симплекс-метод (вычислительная схема, основанная на преобразовании обратных матриц).

М-метод применяется, когда система ограничений не содержит единичную матрицу.

Пусть имеется задача ЛП, требуется найти минимум линейной функции μ(Х)=СХ, при ограничениях АХ=В, Х>0.

Чтобы получить единичную матрицу в каждом уравнении к левой его части прибавим по одной переменной: Хn+i, i=1…m, причем Хn+i≥0, тогда система ограничений примет вид:

a11X1+a12X2+…+a1nXn+Xn+1=b1

a21X1+a22X2+…+a2nXn+Xn+2=b2

….. (1)

am1X1+am2X2+…+amnXn+Xn+m=bm

при этом:

Xj≥0 j=1…m (2)

и будем отыскивать минимум функции.

η(X)=C1X1+C2X2+…+CnXn+MXn+1+…+MXn+m→min (3)

будем считать величину М достаточно большим положительным числом. Если в исходной задаче ищем max целевой функции, то в целевую функцию η(X) новые переменные входят с коэффициентом –М.

Опр: Задача (1) – (3) называется расширенной для исходной задачи ЛП, векторы An+1 An+2 … An+m образует базис, который будем называть искусственным, а переменные им соответствующие Xn+1 Xn+2 … Xn+m называются искусственными переменными.

Th: Если в оптимальном плане расширенной задачи ХР*=(х1, х2, х3, …, хn,0,0) искусственные переменные равны нулю, тогда план ХР*=(х1, х2, х3, …, хn,) является оптимальным для исходной задачи.

Док-во: Пусть ХР* - оптимальный план расширенной задачи, а Х* - план исходной задачи. Заметим, что μ(Х*) = η(ХР*), очевидно, что надо доказать, что Х* - оптимальный план исходной задачи. Допустим противное: это означает, что существует такой план Х(0)=(х1(0), х2(0), …, хn(0)), что μ(Х(0))< μ(Х*), тогда для плана ХР(0)=(х1(0), х2(0), …, хn(0),0,0, …,0) получим η(Х(0))= μ(Х(0)), а μ(Х(0))< μ(Х*) и μ(Х*)= η(Х(0)), следовательно получили противоречие, что найден план ХР(0), в котором значение целевой функции μ(Х*) < η(ХР*), а это невозможно, следовательно наше предположение неверно и Х* - оптимальный план исходной задачи ЛП.

<< | >>
Источник: Шпаргалка - Математические методы и модели исследования операций. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 23. М-симплекс-метод (вычислительная схема, основанная на преобразовании обратных матриц).:

  1. 69. Теорема: Обратное преобразование совершается с обратной матрицей.
  2. 26. Вычисление обратной матрицы с помощью элементарных преобразований.
  3. Квадратная матрица и ее определитель. Особенная и неособенная матрица. Присоединенная матрица. Матрица, обратной данной, и алгоритм ее вычисления.
  4. 20. Описание алгоритма симплекс-метода и табличная реализация вычислительного процесса.
  5. 30.Метод обратной матрицы
  6. 4.Обратная матрица.Теорема о существовании обратной матрицы.
  7. Метод обратной матрицы, метод Крамера, метод Гаусса.
  8. Система n линейных уравнений с n переменными. Метод обратной матрицы и формулы Крамера.
  9. 26. Левая обратная и правая обратная матрицы. Определение.
  10. 27. Теорема: Вырожденная квадратная матрица не имеет ни левой обратной, ни правой обратной.
  11. 30. Теорема: Если квадратная матрица А невырожденная, то д/неё матрица служит и левой, и правой обратной.
  12. Методы вычисления обратной матрицы
  13. 19.Правила преобразования текущего базисного плана и перехода к следующему плану в симплекс-методе.
  14. 6. Использование методов ортогональных преобразований для нахождения собственных чисел матрицы.
  15. 31. Обратная матрица для квадратной невырожденной матрицы.
  16. 13. Вычисление ранга матрицы с помощью элементарных преобразований. Ранг ступенчатой матрицы
  17. В. 7 Обратная матрица. Ранг матрицы
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -