• 2014 год
  • Инфляция: 11.4% √ Безработица: 5.1% √ Рост ВВП: 0.6%
  • МРОТ: 5554 рублей
    Ключевая ставка: 17%
    • Россия в цифрах

      Россия в цифрах

      Статистические данные
    • Мировая экономика в цифрах

      Мировая экономика в цифрах

      Показатели и индикаторы развития мировой экономики.
    • Новости образования

      Новости образования

      Федеральная служба по надзору в сфере образования и науки (Рособрнадзор): список закрытых вузов, новости ЕГЭ

Пример решения модифицированным симплекс-методом


Решим прямую задачу линейного программирования модифицированным симплексным методом.
Определим минимальное значение целевой функции F(X) = 9x1+5x2-4x3 при следующих условиях-ограничений.
2x1+2x2-2x3≥2
4x1+7x2-9x3=6
2x2+5x3≤5

Автоматизировать процесс решения можно с помощью сервиса Симплекс-метод решения задач линейного программирования online

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к каноническойформе).
2x1 + 2x2-2x3-1x4 + 0x5 = 2
4x1 + 7x2-9x3 + 0x4 + 0x5 = 6
0x1 + 2x2 + 5x3 + 0x4 + 1x5 = 5

Введем искусственные переменные x.
2x1 + 2x2-2x3-1x4 + 0x5 + 1x6 + 0x7 = 2
4x1 + 7x2-9x3 + 0x4 + 0x5 + 0x6+ 1x7 = 6
0x1 + 2x2 + 5x3 + 0x4 + 1x5 + 0x6+ 0x7 = 5

Решение состоит из двух этапов. Первый этап - введение искусственного базиса (единичной матрицы) и поиск первого опорного плана (без учета целевой функции). Второйэтап - поиск оптимального решения на основе целевой функции.

Первый этап. Для нахождения начальной допустимой базы воспользуемся методом искусственного базиса.

Для постановки задачи на минимум целевую функцию запишем так:
F(X) = Mx6+Mx7 => min

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

Имеем:
Матрица коэффициентов A = aij

2 2 -2 -1 0 1 0
4 7 -9 0 0 0 1
0 2 5 0 1 0 0
Матрица b.

Итерация №1.
<X> = (6, 7, 5)

Матрица c.
c = (0, 0, 0, 0, 0, -1, -1)
cB = (-1, -1, 0)
cN = (0, 0, 0, 0)

Вычисляем:
Матрицу B-1 вычисляем через алгебраические дополнения.

u = cBB-1 = (-1, -1, 0)

c* = cN - uN = (6, 9, -11, -1)
Откуда s = 2


Откуда r = 2

Итерация №2.
<X> = (6, 2, 5)

Матрица c.
c = (6, 9, -11, -1, 0, 0, 0)
cB = (0, 9, 0)
cN = (6, -11, -1, 0)

Вычисляем:

u = cBB-1 = (0, 1.2857, 0)

c* = cN - uN = (0.8571, 0.5714, -1, -1.29)
Откуда s = 1


Откуда r = 1

Итерация №3.
<X> = (1, 2, 5)

Матрица c.
c = (0.8571, 0, 0.5714, -1, 0, 0, -1.29)
cB = (0.8571, 0, 0)
cN = (0.5714, -1, 0, -1.29)

Вычисляем:

u = cBB-1 = (1, -0.2857, 0)

c* = cN - uN = (-0, 0, -1, -1)
Откуда s = 2


Откуда r = 2

Итерация №4.
<X> = (1, 4, 5)

Матрица c.
c = (0, 0, -0, 0, 0, -1, -1)
cB = (0, 0, 0)
cN = (0, -0, -1, -1)

Вычисляем:

u = cBB-1 = (0, 0, 0)

c* = cN - uN = (0, -0, -1, -1)

Нулевая строка симплексной таблицы неотрицательна. Найдено оптимальное решение X.

Второй этап. Удаляем столбцы с искусственными переменными. Заменим вектор оценок С на целевую функцию.
Выразим базисные переменные:
x1 = 1.5+1.75x2-2.25x3
которые подставим в целевую функцию:
F(X) = 9(1.5+1.75x2-2.25x3) + 5x2-4x3
или
F(X) = 13.5-10.75x2+16.25x3

Имеем:
Матрица коэффициентов A = aij

Матрица b.

Итерация №1.
<X> = (1, 4, 5)

Матрица c.
c = (0, 10.75, -16.25, 0, 0)
cB = (0, 0, 0)
cN = (10.75, -16.25, 0, 0)

Вычисляем:
Матрицу B-1 вычисляем через алгебраические дополнения.

u = cBB-1 = (0, 0, 0)

c* = cN - uN = (10.75, -16.25, 0, 0)
Откуда s = 1


Откуда r = 2

Итерация №2.
<X> = (1, 2, 5)

Матрица c.
c = (0, 10.75, -16.25, 0, 0)
cB = (0, 10.75, 0)
cN = (-16.25, 0, 0, 0)

Вычисляем:

u = cBB-1 = (-7.1667, 3.5833, 0)

c* = cN - uN = (1.6667, -7.1667, 0, 0)
Откуда s = 1


Откуда r = 3

Итерация №3.
<X> = (1, 2, 3)

Матрица c.
c = (0, 0, 1.6667, -7.1667, 0)
cB = (0, 0, 1.67)
cN = (-7.1667, 0, 0, 0)

Вычисляем:

u = cBB-1 = (0.2667, -0.1333, 0.2)

c* = cN - uN = (-6.9, -0.2, 0, 0)
Нулевая строка симплексной таблицы неотрицательна. Найдено оптимальное решение X.

Вектор результатов X = (0.04, 1.4, 0.44)T
Значение целевой функции F(X) = bc = 5.6

Замечания по модифицированному симплексному методу.
1. Данный метод используется при m намного меньше n (например, количество строк m = 2, а количество переменных n= 8).
2. При расчетах метод затрачивает намного меньше времени и памяти ЭВМ.
3. Для вычислений всех оценок достаточно знать начальный вектор b и вектор цен u.
4. Для предотвращения зацикливания в модифицированном методе удобно применять правило Бленда.
5. Недостаток модифицированного симплекс-метода: накопление ошибок в связи с вычислением обратной матрицы B-1.
6. Существуют методы, позволяющие избежать вычисления обратной матрицы B-1.

К содержанию
τ twitter ВКонтакте Ψ facebook
+7 912 459 33 67 594-797-934