Симплексный метод линейного программирования.

При поиске оптимального режима симплексным методом целевая функция должна быть представлена в виде:

, (4.7)

а уравнение ограничений – в виде:

(4.8)

Принято отображать сомножители произведений, входящих в состав F_ц, в виде векторов-строк:

,

а коэффициенты и свободные члены в системе уравнений (4.8) – в виде векторов-столбцов:

.

Векторы a_j называют векторами условий задачи, а вектор b называют вектором ограничений задачи. Компоненты векторов a_j в своей совокупности образуют матрицу:

,

которую называют матрицей условий задачи.

В векторной форме выражение (4.7) записывается в виде скалярного произведения векторов c и x, а левая часть системы уравнений (4.8) записывается в виде произведения матрицы А на вектор х. Теперь в очень краткой форме можно записать основную задачу линейного программирования:

(4.10)

или

.

Чтобы перейти к стандартной процедуре решения основной задачи линейного программирования симплексным методом необходимо, чтобы среди векторов a_j было m единичных. Так, в системе уравнений (4.8) векторы a₁, …, a_m – единичные, т.е. у каждого из этих векторов имеется только одна компонента a_ij (i = 1, 2, …, m), не равная нулю, и она равна единице. Если число единичных векторов a_j меньше m, то в соответствующие уравнения ограничений необходимо ввести дополнительные переменные x_j, с помощью которых уравнения ограничений (4.10) будут записаны в канонической форме (4.8).

В общем виде это производится методом искусственного базиса. Однако в большинстве случаев недостающие переменные x_j можно просто прибавить в соответствующие уравнения ограничений, где их до того не хватало (см. пример 4.1). Это возможно, если ограничения в условиях задачи представлены в виде неравенств.

Процедура симплексного метода основана на следующих положениях:

1. Совокупность точек х в n -мерном евклидовом пространстве E_n, ограниченная условиями (4.10), образует область допустимых решений рассматриваемой задачи. Каждую точку x = (x₁, x₂, …, x_n) из указанной области в экономических расчётах принято называть планом (допустимым). Точка, в которой достигается либо максимум, либо минимум заданной целевой функции, называется оптимальной точкой, или оптимальным планом.

2. В пространстве E_n область допустимых решений образуется в результате пересечения полупространств x ≥ 0 (при n = 2 – полуплоскостей) и Ax ≤ b или –Ax ≤ -b, заданных условиями (4.10), и существует в виде многогранника решений. Оптимальная точка (оптимальный план) является одной из вершин многогранника решений.

3. Любые m линейно независимых векторов a_j (j = 1, 2, …, n, m ≤ n), удовлетворяющих системе уравнений (4.8), порождают точку x = (b₁, b₂, …, b_m, 0, …, 0), являющуюся вершиной многогранника решений. Такую точку принято называть угловой точкой, или опорным планом. Оптимальная точка является одной из угловых точек. В этом нетрудно убедиться на примере нахождения максимального значения функции двух переменных (n = 2):

(4.11)

при условии:

λ – коэффициент пропорциональности, значение которого определяется в зависимости от того, какой вектор выводится из базиса.

Параметр ∆ _j определяет величину и знак приращения, которое получает целевая функция после ввода в базис нового вектора a_j. Если ∆ _j > 0, то целевая функция убывает (F_цj < F_ц0), а если ∆ _j < 0, то целевая функция возрастает. Знак ∆ _j является критерием полезности ввода нового вектора в базис. При поиске максимума имеет смысл вводить в базис только такой вектор, которому соответствует ∆ _j < 0, а при поиске минимума поиск оптимального режима (оптимального плана) продолжают лишь тогда, когда находится вектор, ввод которого в базис приводит к ∆ _j > 0 и, соответственно, к уменьшению F_ц.

Значение ∆ _j определяют по формуле:

, (4.14)

где c_i – первые m коэффициентов целевой функции (4.7);

a_ij – коэффициенты при x_j (j = 1, 2, …, n) системы уравнений (4.8).

При j ≤ m, т.е. для m единичных векторов, входивших перед этим расчётом в состав базиса, согласно (4.14) получим ∆ _j = 0.

Рассмотрим более подробно поиск оптимального режима, когда он соответствует максимуму целевой функции. Сначала перечислим признаки оптимальности режима (опорного плана):

1) опорный план решения задачи (4.7) … (4.9) является оптимальным, если ∆ _j ≥ 0 для любого j (j = 1, 2, …, n);

2) если ∆ _k < 0 для некоторого j = k и среди чисел a_ik нет положительных, то целевая функция (4.7) не ограничена;

3) если ∆ _k < 0, но среди чисел a_ik есть положительные (не все (a_ik ≤ 0), то существует опорный план x' такой, что F_ц(x') > F_ц(x).

Затем составим табл.4.1, в которой первые m строк определяются исходными данными задачи, а показатели (m + 1) -й строки вычисляют.

Исходные данные табл.4.1 соответствуют опорному плану .

Таблица 4.1

Исходные данные для разработки опорного плана

Таблица 4.2

Параметры оптимизационного процесса (опорного плана)

В (m + 1) -й строке табл.4.1 в столбце b записывают значение F_ц0, рассчитанное по формуле (4.7), а в каждом столбце a_j (j = 1, 2, …, n) записывают значение ∆ _j, рассчитанное по формуле (4.14). Если ∆ _j < 0 для некоторых индексов j и для каждого такого j, по крайней мере, одно из чисел a_ij положительно, то можно составить новый опорный план, при котором значение целевой функции увеличится.

Чтобы перейти к улучшенному опорному плану, нужно ввести в базис вектор a_k, у которого ∆ _k > 0 и это ∆ _k является наибольшим (по абсолютной величине) отрицательным числом среди всех ∆ _j. Взамен из базиса исключается вектор a_r. Номер r соответствует элементу a_rk вектора a_rk находят по минимуму выражения b_i / a_ik для всех a_ik > 0. Если же все a_ik ≤ 0 (i = 1, 2, …, m), то целевая функция не ограничена сверху. Число a_rk называется разрешающим элементом. Столбец a_k и строка r, на пересечении которых находится разрешающий элемент, называются направляющими, или разрешающими.

Улучшенный опорный план находят методом Жордана-Гаусса. При этом положительные компоненты нового опорного плана находят по формулам:

, (4.15)

а коэффициенты разложения векторов a_j через векторы нового базиса, соответствующего новому опорному плану, находят по формулам:

Дано:

затраты времени электроэнергии по каждому сортаменту в расчёте на тонну продукции: t₁ = 0, 04 ч/т; t₂ = 0, 08 ч/т; w₁ = 8 кВт*ч/т; w₂ = 3 кВт*ч/т;

месячный фонд технологического времени t_м ≤ 600 ч;

месячный лимит электроэнергии на текущий месяц W_м ≤ 100 000 кВт*ч.

Найти такой вариант месячной программы прокатки x₁(m) первого сортамента стали и x_m второго сортамента стали, который обеспечит в текущем месяце, когда имеются ограничения по электроэнергии, максимум прибыли при условии, что прибыльность второго сортамента стали в 1.2 раза выше прибыльности первого сортамента стали:

.

В уравнении целевой функции F_ц прибыльность выражена в относительных единицах (отн.ед.). За единицу прибыли принята прибыль от 1 т проката первого сортамента.

Выпуск проката ограничивается неравенствами:

.

Вводим: x₃ – неиспользование технологическое время;

x₄ – неиспользованная в пределах лимита электроэнергия.

Получаем систему уравнений ограничений задачи, выраженную в канонической форме: