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

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

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

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

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

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

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

Метод обратной матрицы

Достоинства усовершенствованного симплексного метода:
  1. простота;
  2. эффективность вычислительной процедуры;
  3. меньшее количества вычислительных операций;
  4. меньший объем памяти ЭВМ;
Линейное программирование (ЛП) - это метод поиска неотрицательных значений переменных, минимизирующих или максимизирующих значение линейной целевой функции при наличии ограничений, заданных в виде линейных неравенств.
Инструкция. Выберите количество переменных и количество строк (количество ограничений).
Количество переменных
Количество строк (количество ограничений)
При этом ограничения типа xi ≥ 0 не учитывайте.

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

Дана математическая запись модели:
-x1 - 5x2 + 3х3 = 4;
2x1 + 5x2 - 3х3 ≥2;
1 + 4х2 ≤ -4;
F(x)= -5x1 + х2 - 2х3 → max.

Шаг №0. Сведем задачу ЛП к нахождению минимума.
-x1 - 5x2 + 3х3 = 4;
2x1 + 5x2 - 3х3 ≥2;
1 + 4х2 ≤ -4;
-F(x)= 5x1 - х2 + 2х3 → min.
Если сразу задана функция минимизации (min), то Шаг №0 пропускаем.

Приводим из системы неравенств в систему уравнений, вводя дополнительные переменные:
-x1 - 5x2 + 3х3 = 4;
2x1 + 5x2 - 3х3 - х4 = 2;
1 + 4х2 + х5= -4;
-F(x)= 5x1 - х2 + 2х3 → min.

В матричной форме:
Матрица А

-1 -5 3 0 0
2 5 -3 -1 0
2 4 0 0 1

Матрица В
4
2
-4
или BT = (4 ;2; -4);

Тогда задачу ЛП можно записать следующим образом:

A x X = B
X ≥ 0
F(x) = Z = C x X → min
Базисные переменные: x1, x2, x3
Небазисные переменные: x4, x5
Преобразуем матрицу А, выделяя единичную матрицу I
-1/3 -5/3 1 0 0
-1 0 0 1 0
2 4 0 0 1

Шаг №1.
В начале первого цикла нам известны обратная матрицаA-1 (единичная матрица), базисное решение xb = A-1 x b

1 0 0
0 1 0
0 0 1

xb = (4; 2; -4);

Шаг №2. Образуем для каждой небазисной переменной характеристическую разностьdj, используя уравнение:

dj = cj - sj x Pj,
где s - двойственные переменные, которые можно найти следующим образом:
sj = cx x A-1,
где cx - вектор коэффициентов целевой функции при базисных переменных.
cx = (-5; 1; -2);
sj = cx x A-1 = (-5; 1; -2);
dj = (-5; 1; -2) - (-5; 1; -2) = (0; 0; 0)

Шаг №3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим: s = min dj.
s = -5, индекс столбца p = 1

Шаг №4. Если s ≥ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

Шаг №5. Если s ≤ 0, вычисляем преобразованный столбец:

P-p = A-1 x Pp
P-1 = (-1/3; -1; 2)
P-p = (a1s,a2s,...,ams)
Если все ais ≤ 0 - процедура останавливается: оптимум неограничен.

Шаг №6. В противном случае находим выводимую из базиса переменную:

xbr / ars = min (ais ≥ 0) = θ

Шаг №7. Строим матрицу и трансформируем ее с ведущим элементом ars

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


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

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

Дана математическая запись модели:
-2x1 + 6x2 + 7х3 ≥ 3;
5x1 + 3x2 - 4х3 ≤ -3;
1 + 2х3 ≤ 2;
F(x)= -5x1 + 5х2 - 7х3 → min.
τ twitter ВКонтакте Ψ facebook
+7 912 459 33 67 594-797-934