62. Задача линейного программирования: общая формулировка. Основные идеи и алгоритм симплекс-метода

Линейное программирование (ЛП) объединяет методы решения задач, которые описываются линейными уравнениями или неравенствами, причем целевая функция также линейна; оно широко используется при составлении оптимального по прибыли плана, выборе наилучшей схемы перевозок, наименьшего уровня потребления ресурсов при заданном нормативном расходе их на единицу продукции.

Задача:

1. Целевая функция представляет собой линейную сумму от неизвестных переменных x_j вида

где c_j – известные коэффициенты. Такую целевую функцию часто называют линейной формой и обозначают L.

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

где a_ij, b_i – известные величины, причем b_i положительные.

СИМЛЕКС-метод

Он состоит в направленном переборе допустимых базисных решений (ДБР) вплоть до нахождения оптимума, когда все «оценки» становятся неотрицательными. «Оценки» вычисляются как компоненты вектора, соответствующего решению двойственной задачи ЛП.

Этапы решения задачи симплекс-методом:

1) формирование начального ДБР;

2) проверка его на оптимальность с помощью признака оптимальности;

3) поиск вектора, вводимого в базис, и вектора, выводимого из базиса (в случае неоптимальности);

4) изменение базиса и пересчет симплекс-таблицы (получение нового ДБР);

5) возвращение к п. 2.

Пример решения задачи лп на максимум с ограничениями-равенствами симплекс-методом

Дано: С = (3, 2, 1, –1, 0),

b = A =

Требуется найти max (3x₁ + 2x₂ + x₃ – x₄ + 0x₅ )

при ограничениях: 3x₁ + x₂ + 3x₃ – x₄ + 2x₅ = 5,

3x₁ + 2x₂ + x₃ + x₅ = 5,

7x₁ + 2x₂ + 2x₃ – x₅ = 5,

x_1÷5 0.

ВАЖНО Если ограничения – неравенства, то нужно привести к стандартному виду:

- путем ввода ДОПОЛНИТЕЛЬНЫХ переменных (если <= то + хn’, если >= то –хn’)

- справа всегда неотрицательное число;

- в случае, если нет ограничения на знак (например, х1 – любое, то заменяется разностью двух положительных переменных)

ВАЖНО Если функция на min(a+b), то меняется на –(max(-a-b)).

Вводим искусственные переменные в каждое из ограничений и с большим по абсолютной величине отрицательным числом в целевой функции:

max (3x₁ + 2x₂ + x₃ – x₄ + 0x₅ – 100x₆ – 100x₇ – 100x₈).

3x₁ + x₂ + 3x₃ + x₄ + 2x₅ + x₆ = 5,

3x₁ + 2x₂ + x₃ + x₅ + x₇ = 5,

7x₁ – 2x₂ + 2x₃ – x₅ + x₈ = 5,

x_1÷8 0.

Построим начальную симплекс-таблицу 7.1:

L = –1500		x1	x2	x3	x4	x5	x6	x7	x8	Θ
cbase	xbase	3	2	1	–1	0	–100	–100	–100
100	x6=5	3	1	3	1	2	1	0	0	5/3
100	x7=5	3	2	1	0	1	0	1	0	5/3
100	x8=5	7	–2	2	0	–1	0	0	1	5/7
j		–1303	–102	–601	–99	–200	0	0	0

Получено НДБР. Проверим его на оптимальность, т.е. посчитаем _j и добавим результаты в таблицу:

₁ = 3 (–100) + 3 (–100) + 7 (–100) – 3 = 1303,

₂ = 1 (–100) + 2 (–100) – 2 (–100) – 2 = 102,

₃ = 3 (–100) + 1 (–100) + 2 (–100) – 1 = 601,

₄ = 1 (–100) – (–1) = 99,

₅ = 2 (–100) + 1 (–100) – 1 (–100) – 0 = 200.

И т.д. пока не будет отрицательных . Потом не забыть преобразовать max в min, доп. переменные в начальные и т.д., посчитать значение целевой функции.