Общая постановка задачи оптимизации металлургических процессов, страница 6

2)  Исходное ограничение, записанное в виде неравенства типа £ или ³, можно представить в виде равенства, прибавляя или вычитая дополнительную неотрицательную переменную к левой части ограничения. Число таких переменных равно числу неравенств в системе ограничений. (Чтобы дополнительные переменные не оказывали влияние на значение целевой функции, они должны входить в целевую функцию с нулевыми коэффициентами.)

3)  Если переменная xi не имеет ограничений в знаке, то она заменяется разностью двух неотрицательных переменных:

xi = xi¢ – xi¢¢, xi¢ ³ 0, xi¢¢ ³ 0.

8x1 + 7x2 + 6x3 ® max

2x1 + 3x2 + 4x3 £ 150

x1 + 4x2 + 5x3 £ 180

3x1 + 4x2 + 2x3 ³ 100

x1 ³ 0, x2 ³ 0.

– 8x1 – 7x2 – 6x3 ® min

x3 = x4x5, x4, x5 ³ 0.

2x1 + 3x2 + 4(x4x5) + x6 = 150

x1 + 4x2 + 5(x4x5) + x7 = 180

3x1 + 4x2 + 2(x4x5) – x8 = 100

Таким образом, преобразование задачи в каноническую форму приводит к увеличению размерности задачи (количества переменных).

Графический способ решения задач линейного программирования

Постановка задачи: минимизировать G = 40x1 + 36x2 при ограничениях

x1 < 8, x2 < 10, 5x1 + 3x2 > 45, x1 > 0, x2 > 0.

x1 > 9 – 0,6 x2

G = 40x1 + 36x2 = 400

x1 = 10 – 0,9 x2

G(A) = 40×8 + 36×5/3 = 320 + 60 = 380

G(B) = 40×8 + 36×10 = 320 + 360 = 680

G(C) = 40×3 + 36×10 = 120 + 360 = 480

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

Из линейности целевой функции следует, что ее градиент – вектор, указывающий направление возрастания функции и перпендикулярный ей,  постоянен в любой точке, а линии уровня функции G параллельны друг другу.

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

Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. Симплекс-метод является общим методом решения задач ЛП, с помощью которого можно получить экономическую интерпретацию полученного решения и провести анализ модели на чувствительность. Решение находится с помощью итеративной процедуры.

Классическим методом решения систем линейных уравнений является метод Гаусса-Жордана. Он заключается в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над

строками:

xi ³ 0, i = 1, 2, …, n.

Переменные х1, х2, …, хm, входящие с единичными коэффициентами, называются базисными или зависимыми. Остальные переменные – небазисные.

Базисным решением системы в каноническом виде называется решение, полученное при нулевых значениях небазисных переменных (х1 = b1,…, хm = bm, хm+1 = … = хn =0).

Если b1 ³ 0, …, bm ³ 0, то полученное решение называется допустимым базисным решением.

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

Алгоритм симплекс-метода включает следующие основные шаги:

-  сведение задачи ЛП к каноническому виду;

-  выбор допустимого базисного решения;

-  выражение ограничений и целевой функции через небазисные переменные (переменные, равные нулю в точке решения);

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