Симплексный метод

  • Просмотров 498
  • Скачиваний 12
  • Размер файла 109
    Кб

Задача 1. Решить задачу линейного программирования симплексным методом. Вариант 3. Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях 2x1 + x2 + x3  2 x1 - x2 + x3  1, xj  0, j = 1, 2, 3. Решение. Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5  0. f(X) = - x1 - x2 + 2x3  max 2x1 + x2 + x3 + x4 = 2 x1 - x2 + x3 + x5 = 1, xj  0, j = 1, 2, 3, 4, 5. Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает

очевидным начальным опорным решением. Очевидное начальное опорное решение (0; 0; 0; 2; 1). Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах Номер симплекс-таблицы Базис Cj Ci B -1 -1 2 0 0 Q A1 A2 A3 A4 A5 0 A4 0 2 2 1 1 1 0 2:1 = 1 A5 0 1 1 -1 1 0 1 1:1 = 1 j - 0 1 1 -2 0 0   1 A4 0 1 1 2 0 1 -1 1:2 = 1/2 A3 2 1 1 -1 1 0 1   j - 2 3 -1 0 0 2   2 A2 -1 1/2 1/2 1 0 1/2 -1/2   A3 2 3/2 3/2 0 1 1/2 1/2   j - 5/2 7/2 0 0 1/2 3/2   Начальное опорное решение (0; 0; 0; 1; 1),

соответствующее симплекс-таблице 0, неоптимальное, так как в  - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А5, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А5 выводим из базиса, а А3 - вводим в базис. После пересчета получаем симплекс-таблицу 1. Соответствующее опорное

решение (0; 0; 1; 1; 0) не оптимально, так как в  - строке есть отрицательные значения, в столбце А2.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А2 - вводим в базис. Опорное решение, соответствующее симплекс-таблице 2 (0; 1/2; 3/2; 0; 0) - оптимально, так как

в  - строке нет отрицательных значений. Отбрасывая значения дополнительных переменных х4 и х5, получаем оптимальное решение исходной задачи: х1 = 0, х2 = 1/2 = 0,5; х3 = 3/2 = 1,5; fmax = -10 - 10,5 + 21,5 = 2,5. Задача 2. Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи. Задание 2. Решить полученную задачу линейного программирования графическим методом. Задание 3. Сформулировать двойственную задачу и найти ее