Теоретические основы решения задач

Математическая постановка оптимизационной задачи.

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

– технологическая матрица коэффициентов.

- вектор удельной прибыли от реализации продукции.

- вектор запасов ресурсов.

- вектор переменных.

Используя данные обозначения, получим искомый план производства продукции:

Где c_i, a_ij, b_i – заданные постоянные величины.

Каноническая форма записи задачи линейной оптимизации (ЗЛО) имеет особенность, принципиально отличающую ее от других форм записи. А именно, если в стандартной форме соотношении между количеством переменных n и не прямых ограничений m произвольное, то в канонической ЗЛО всегда число уравнений строго меньше числа переменных, т.е. m<n.

Сведение стандартной формы записи ЗЛО к канонической производится путем введение дополнительных переменных :

Таким образом, ограничения – неравенства преобразуются в ограничения равенства. Матрица коэффициентов новой системы ограничений имеет вид:

Итак, введение дополнительных переменных в стандартную форму ЗЛО (1) преобразовывает ее в ЗЛО (2):

(1)

(2)

Где – вектор переменных ЗЛО (2)

- вектор коэффициентов целевой функции (2).

Основные определения линейной оптимизации (ЛО).

Определение 1. Множество векторов называется множеством допустимых решений задачи или допустимым множеством.

Определение 2. Вектор (из множества допустимых планов) называется оптимальном планом задачи, или задачи, если для любого вектора х из допустимого множества выполняется неравенство С(х) ≤ С(х^*).

Определение 3. Пусть – допустимый план ЗЛО. Носителем плана х называется множеством индексов .

Определение 4. Пусть – допустимый план ЗЛО и σ – его носитель. Если векторы А_i, линейно независимые, то план Х называется базисным допустимым планом (БДП) или базисным допустимым решением (БДР).

Симплекс – метод.

Основные этапы симплекс – метода, при этом ЗЛО должна быть в приведенной форме:

1. Построение начального БДП х⁰.

2. Проверка плана х⁰ на оптимальность. Вычисление двойственных оценок.

3. Если все Δ_j ≥ 0, , тогда БДП х⁰ – оптимальный.

4. Если условие оптимальности не выполнено, т.е. существует Δ_s<0, то реализуется процедура поиска нового БДП х¹, которая заключается в определении вектора A_k, вводимого в базис, и вектора A_r, выводимого из базиса. При этом значение целевой функции на новом плане будет не меньше, чем на плане х⁰, т.е. С (х⁰) ≤ С (х¹). В процессе поиска нового БДП может быть сделан вывод, что в ЗЛО существует оптимальный план.

5. Если БДП х¹ существует, то происходит возврат к п. 2, а именно вычислению двойственных оценок, но уже для плана х¹ и т.д., пока не будет найден оптимальный план, или не будет установлено, что такого плана нет.

Методы решения задач параметрической оптимизации.

Параметрическая оптимизация – это метод определения того, как меняется решение задачи с изменением или вектора коэффициентов целевой функции, или вектора ограничений, или того и другого вместе.

Ниже излагаются основные факты теории параметрического программирования применительно к следующим однопараметрическим ЭММ:

Здесь

Параметры μ и λ могут изменяться в интервале (-∞, ∞), однако из содержательной постановки задачи обычно следует их принадлежность более узкому интервалу.

Методы решения многокритериальных задач (МКЗ).

Многокритериальная задача линейной оптимизации (МКЗ ЛО) записывается в следующем виде:

Здесь - вектор переменных.

– матрица системы ограничений.

- вектор правых частей ограничений

- k-й критерий (целевая функция).

План называется эффективным (или Парето – оптимальным, или оптимальным по Парето) если не существует другого плана , который не хуже, чем х^*, по всем критерием и лучше, чем х^* по некоторому критерию f_k, другими словами, не существует , такого что , и хотя бы для одного k

Метод сверстки критериев. Суть метода - сведение имеющего множества критериев к одному скалярному критерию, отражающую комбинированную (общую) цель системы критериев.

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

Сверстка критериев представляет собой функцию следующего вида:

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

,

Где

В результате таких действий решении задачи выглядит так:

Замечание 1. Если все критерии однородны, т.е. выражены в одинаковых единицах измерения, то можно не нормировать целевые функции, а в задачи применять свертку.

Замечание 2. Решение задачи, получаемое с помощью любого свертывания критериев (при любых , удовлетворяющих условию), является эффективным планом.

Замечание 3. Весовые коэффициенты , лицо принимающее решение (ЛРП) может изменять по своему усмотрению с целью получения наиболее приемлемого плана.

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

Предположим, что - главный (наиболее важный для ЛРП) критерий. Пусть - нижняя граница j-го критерия, устанавливаемая ЛРП. При этом .

Тогда решение будет:

Модифицированный метод идеальной точки. Суть метода – найти допустимое решение такое, что точка достижимого множества оказывается ближайшей к идеальной точке .

Чтобы нелинейный критерий привести к линейному виду, введем новую переменную . Таким образом, в данном методе решение МКЗ ЛО определяется в результате нахождения оптимального плана следующей задачи ЛО:

Идеальная точка – это некоторая точка, которая существует, и мы не можем улучшить одно значение, не ухудшая при этом другое.

Метод последовательных уступок (или пороговых значений). Суть метода – все критерии ранжируются по степени важности для ЛРП. Далее последовательно решаются однокритериальные задачи в установленном порядке с добавлением в каждую последующую задачу дополнительного ограничения на предыдущий критерий.

Пусть . Сначала решает задача ЛО:

В результате решения задачи определяется финальный план и вычисляется значения целевой функции на этом плане . Затем вычисляются и анализируются значения остальных критериев на этом плане . ЛРП анализирует значение первого критерия и назначают максимальную уступку такую, что . Далее решается следующая задача:

Для оптимального плана задачи анализируется значение критериев . Если значение устраивает ЛРП, то план принимается за лучшее решение. В противном случае вводится следующая уступка , по второму критерию и решается задача, и так далее пока решение не будет удовлетворять ЛРП.