Решение задачи по линейному программированию симлекс методом на заказ.

Симплекс-метод

Определим минимальное значение целевой функции F(X) = - 2x2 при следующих условиях-ограничениях:
- x1 + 3x2 ≤ 9
x1 – x2 ≤ 4
x1 + x2 ≤ 5
2x1 + 3x2 ≥ 6
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
-1x1 + 3x2 + 1S1 + 0S2 + 0S3 + 0S4 = 9
1x1 – 1x2 + 0S1 + 1S2 + 0S3 + 0S4 = 4
1x1 + 1x2 + 0S1 + 0S2 + 1S3 + 0S4 = 5
2x1 + 3x2 + 0S1 + 0S2 + 0S3 – 1S4 = 6
Введем искусственные переменные x: в 4-м равенстве вводим переменную S5;
-1x1 + 3x2 + 1S1 + 0S2 + 0S3 + 0S4 + 0S5 = 9
1x1-1x2 + 0S1 + 1S2 + 0S3 + 0S4 + 0S5 = 4
1x1 + 1x2 + 0S1 + 0S2 + 1S3 + 0S4 + 0S5 = 5
2x1 + 3x2 + 0S1 + 0S2 + 0S3-1S4 + 1S5 = 6
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -2x2+M•S5 → min
Из уравнений выражаем искусственные переменные:
S5 = 6-2x1-3x2+S4
которые подставим в целевую функцию:
F(X) = -2Mx1+(-2-3M)x2+ M•S4+6M → min
Матрица коэффициентов A = aij этой системы уравнений имеет вид:
-1 3 1 0 0 0 0
1 -1 0 1 0 0 0
1 1 0 0 1 0 0
2 3 0 0 0 -1 1

Решим систему уравнений относительно базисных переменных:
S1, S2, S3, S5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0, 0 ,9, 4, 5, 0, 6)

Базис B x1 x2 S1 S2 S3 S4 S5
S1 9 -1 3 1 0 0 0 0
S2 4 1 -1 0 1 0 0 0
S3 5 1 1 0 0 1 0 0
S5 6 2 3 0 0 0 -1 1
F(X0) 6M 2M 2+3M 0 0 0 -1M 0

Переходим к основному алгоритму симплекс-метода.

Нулевая (начальная) "Итерация".
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 S1 S2 S3 S4 S5 min
S1 9 -1 3 1 0 0 0 0 3
S2 4 1 -1 0 1 0 0 0 -
S3 5 1 1 0 0 1 0 0 5
S5 6 2 3 0 0 0 -1 1 2
F(X1) 6M 2M 2+3M 0 0 0 -1M 0 0


Получаем новую симплекс-таблицу:
Базис B x1 x2 S1 S2 S3 S4 S5
S1 3 -3 0 1 0 0 1 -1
S2 6 12/3 0 0 1 0 -1/3 1/3
S3 3 1/3 0 0 0 1 1/3 -1/3
x2 2 2/3 1 0 0 0 -1/3 1/3
F(X1) -4 -11/3 0 0 0 0 2/3 -2/3-1M

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной S4, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai6
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 S1 S2 S3 S4 S5 min
S1 3 -3 0 1 0 0 1 -1 3
S2 6 12/3 0 0 1 0 -1/3 1/3 -
S3 3 1/3 0 0 0 1 1/3 -1/3 9
x2 2 2/3 1 0 0 0 -1/3 1/3 -
F(X2) -4 -11/3 0 0 0 0 2/3 -2/3-1M 0


Получаем новую симплекс-таблицу:
Базис B x1 x2 S1 S2 S3 S4 S5
S4 3 -3 0 1 0 0 1 -1
S2 7 2/3 0 1/3 1 0 0 0
S3 2 11/3 0 -1/3 0 1 0 0
x2 3 -1/3 1 1/3 0 0 0 0
F(X2) -6 2/3 0 -2/3 0 0 0 -1M

Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (11/3) и находится на пересечении ведущего столбца и ведущей строки.
Базис B x1 x2 S1 S2 S3 S4 S5 min
S4 3 -3 0 1 0 0 1 -1 -
S2 7 2/3 0 1/3 1 0 0 0 101/2
S3 2 11/3 0 -1/3 0 1 0 0 11/2
x2 3 -1/3 1 1/3 0 0 0 0 -
F(X3) -6 2/3 0 -2/3 0 0 0 -1M 0


Получаем новую симплекс-таблицу:
Базис B x1 x2 S1 S2 S3 S4 S5
S4 71/2 0 0 1/4 0 21/4 1 -1
S2 6 0 0 1/2 1 -1/2 0 0
x1 11/2 1 0 -1/4 0 3/4 0 0
x2 31/2 0 1 1/4 0 1/4 0 0
F(X3) -7 0 0 -1/2 0 -1/2 0 -1M

Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 S1 S2 S3 S4 S5
S4 71/2 0 0 1/4 0 21/4 1 -1
S2 6 0 0 1/2 1 -1/2 0 0
x1 11/2 1 0 -1/4 0 3/4 0 0
x2 31/2 0 1 1/4 0 1/4 0 0
F(X4) -7 0 0 -1/2 0 -1/2 0 -1M

Оптимальный план можно записать так:
S4 = 71/2
S2 = 6
x1 = 11/2
x2 = 31/2
F(X) = 0•11/2 - 2•31/2 = -7

3 комментария:

  1. Помощь студентам. Решение задач - математика, физика, химия, ТОЭ, механика.

    скайп-репетитор.рф

    Решение задач по физике, математике, математическому анализу, теории вероятности, программированию, химии, ТОЭ, электротехнике, сопромату, теоретической механике.


    MOCKBA3452061.narod.ru

    ОтветитьУдалить
  2. Симплекс метод легко решить только с репетитором Алексеем Учителем!


    репетитор-по-математике.рф

    ОтветитьУдалить
    Ответы
    1. Пусть ABCD-равнобокая трапеция, с основаниями AD и BC. Диагональ АС= основанию АD. Углы ВАС=АDC=ACD (так как треугольник АСD равнобедренный).
      Трапеция. Свойства трапеции, диагональ равнобедренной трапеции с основаниями 4 и 16 образует с основанием угол 45 градусов. найдите площадь трапеции. В равнобокий трапеции АВСD с основаниями ВС=9 и АD=15 диагональ АС перпендикулярна боковой стороне СD. Найти высоту трапеции, диагональ и косинус большего угла между диагоналями. Разбор III этапа всероссийской олимпиады школьников по физике. Теоретический тур.

      Удалить