Теория и методы принятия решений

решение системы: x1 = 3, x2 = 4.

Вывод: максимальное значение целевой функции f равно 3 + 2*4 + 3 = 14 и достигается при x1 = 3, x2 =4.

Примечание.

Упражнения. Решить геометрически задачу линейного программирования, результат проверить в Microsoft Excel.

1. 2.

3. 4.

1.4. Симплекс-метод решения задач линейного программирования

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

1. Если требуется найти максимум целевой функции f,

то найти минимум целевой функции –f.

2. Найти любое опорное решение задачи линейного программирования.

3. Если опорное решение существует,

то

найти оптимальное (min) опорное решение;

4. Если требовалось найти максимум целевой функции,

то

умножить на -1 найденный минимум.

1.4.1. Поиск опорного решения задачи линейного программирования

1. Преобразовать систему ограничений к стандартному виду:

(1)

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

2. Если в системе (1) все ?i ? 0,

то

приравнять к нулю все свободные переменные и этим получить опорное решение.

3. Если в системе (1) найдётся ?i < 0,

то

найти и поменять местами свободную переменную xk и базисную переменную xn (то есть свободную переменную xk ввести в состав базисных, а базисную переменную xn – в состав свободных).

4. Если обмен произвести удалось,

то

продолжить с п. 2,

иначе

опорного решения не существует.

Пример. Найти опорное решение следующей задачи линейного программирования

(2)

Решение.

1. Приводим систему ограничений к стандартному виду:

а) получаем систему линейных уравнений по правилу:

если в системе ограничений есть неравенства, то в левые части неравенств со знаком "?" следует добавить новые переменные , а из левых части неравенств "?" – вычесть новые переменные:

в системе ограничений (2) есть неравенства и все со знаком "?", поэтому, добавляем к левым частям неравенств новые переменные:

(3)

б) Приводим систему линейных уравнений (3) к ступенчатому виду:

• записываем расширенную матрицу системы из коэффициентов при неизвестных и свободных членов:

;

• умножаем вторую строку на -1 и меняем местами первую и вторые строки:

;

• умножаем первую строку на 5 и складываем со второй, умножаем первую строку на 3 и складываем с третьей и получаем ступенчатый вид матрицы:

.

в) Приводим систему линейных уравнений к приведённому ступенчатому виду:

• первую строку умножаем на -1, третью строку делим на -3:

;