Лекции по "Экономике организации"

 

 

 Задачи линейного  программирования. Постановка и  геометрическая интерпретация задач  линейного программирования. Методы  линейного программирования. Прямые  и двойственные задачи математического  программирования. Симплекс-метод.  Многокритериальные задачи линейного  программирования.

Линейное программирование (ЛП) –  один из первых и наиболее подробно изученных разделов математического  программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

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

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

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

(8)

при условиях

(9)

(10)

(11)

где - заданные постоянные величины и .

Определение 2.

Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

Определение 3.

Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

Определение 4.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

Определение 5.

Совокупность чисел  , удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

Определение 6.

План  , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (8) при  плане Х будем обозначать через . Следовательно, X^* – оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

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

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

В том случае, когда требуется  найти минимум функции  , можно перейти к нахождению максимума функции , поскольку .

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

 

 

Определение 1. Задача, состоящая в нахождении минимального значения функции называется двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

 

1. Целевая функция исходной задачи  задается на максимум, а целевая  функция двойственной на минимум. 

2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной  задаче (35) – (37) равно числу ограничений  в системе (33) исходной задачи (32) – (34), а число ограничений  в системе (36) двойственной задачи  – числу переменных в исходной  задаче.

4. Коэффициентами при неизвестных  в целевой функции (35) двойственной  задачи (35) – (37) являются свободные  члены в системе (33) исходной  задачи (32) – (34), а правыми частями  в соотношениях системы (36) двойственной  задачи – коэффициенты при  неизвестных в целевой функции  (32) исходной задачи.

5. Если переменная xj исходной задачи (32) – (34) может принимать только лишь положительные значения, то j–е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “>”. Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i–я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

 

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

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

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

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

Пример 26.1

Решить симплексным методом  задачу:

Решение:

Приводим задачу к каноническому  виду.

Для этого в левую часть первого  ограничения-неравенства вводим дополнительную переменную x₆ с коэффициентом +1. В целевую функцию переменная x₆ входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

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

Δ_k = C_бX_k — c_k

Где:

• C_б = (с₁, с₂, ... , с_m ) — вектор коэффициентов целевой функции при базисных переменных
• X_k = (x_1k, x_2k, ... , x_mk ) — вектор разложения соответствующего вектора А_к по базису опорного решения
• С_к — коэффициент целевой функции при переменной х_к.

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

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

В последней строке таблицы с  оценками Δ_k в столбце "А₀" записываются значения целевой функции на опорном решении Z(X₁).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ₁ = -2, Δ₃= -9 для векторов А₁ и А₃ отрицательные.

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

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

Приращение целевой функции  находится по формуле: .

Вычисляем значения параметра θ₀₁ для первого и третьего столбцов по формуле:

Получаем θ₀₁ = 6 при l = 1, θ₀₃ = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции  при введении в базис первого  вектора ΔZ₁ = — 6*(- 2) = 12, и третьего вектора ΔZ₃ = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению  необходимо ввести в базис опорного решения вектор А3 вместо первого  вектора базиса А6, так как минимум параметра θ₀₃ достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем  параметр θ₀₂ для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х₂₂ = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ₁ = 7/2, Δ₄ = 2, Δ₆ = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

 

 Модели и численные  методы безусловной оптимизации.  Классификация методов безусловной  оптимизации. Скорости сходимости. Методы первого порядка. Градиентные  методы. Метод Ньютона и его  модификации. Квазиньютоновские методы. Конечно-разностные методы. Методы нулевого порядка: методы покоординатного спуска, Хука—Дживса, сопряженных направлений, методы деформируемых конфигураций, симплексные методы.

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

Классификация методов.

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