В начало

Литература

Тема 2. Методы получения оптимальных решений

2.1. Основы линейного программирования. Математический аппарат линейного программирования. Различные формы записи задачи линейного программирования (ЗЛП). Графическое решение задачи линейного программирования, исследование случаев неразрешимости задачи. Основы симплекс-метода, процедуры решения с естественным и искусственным базисом. Особые случаи решения ЗЛП. Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана.

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

2.3. Основные понятия и общие сведения о методах реализации моделей нелинейного и динамического программирования.

Для изучения оптимизационных моделей необходимо повторение ряда разделов курса высшей математики:

— матрицы, действия над матрицами;

— обратная матрица, ее вычисление;

— ранг матрицы и его вычисление;

— определители, их свойства, вычисление определителей;

— миноры и алгебраические дополнения, их вычисление;

— системы линейных уравнений, решение методом обратной матрицы;

— исследование систем линейных уравнений методом Жордана-Гаусса;

— векторы и простейшие действия над ними;

— линейная зависимость и независимость системы векторов, базис системы векторов;

— линейные векторные пространства, базис пространства, естественный базис, переход от одного базиса к другому;

— выпуклые множества, выпуклые и вогнутые функции.

Необходимый минимум материала по указанным вопросам содержится в учебном пособии [1, с. 30-49]. Эти сведения являются частью базовых математических знаний, составляющих необходимую математическую культуру современного экономиста.

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

Рассмотрим последовательно основные вопросы по приведенным выше разделам темы 2.

2.1. Основы линейного программирования

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

f(x₁, x₂,…, x_n) = c₁x₁ + c₂x₂ + … +c_nx_n (2.1)

при ограничениях

(2.2)

x_j ≥ 0, j = 1, 2, …, n, (2.3)

где — a_ij, b_i, c_j (i = 1, 2, ... m, j = 1, 2,..., n) — заданные постоянные величины.

Это развернутая форма записи общей задачи линейного программирования (ЗЛП); знак {≤, =, ≥} означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (со знаком в ту или иную сторону).

Систему ограничений (2.2) называют функциональными ограничениями ЗЛП, а ограничения (2.3) - прямыми.

Вектор Х = (x₁, x₂, …, x_n), удовлетворяющий системе ограничений (2.2) и (2.3), называется допустимым решением или планом ЗЛП, т. е. ограничения (2.2), (2.3) определяют область допустимых решений или планов ЗЛП (область определения ЗЛП).

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

Канонической формой записи ЗЛП (КЗЛП) называют задачу вида (запись с использованием знаков суммирования)

max (min) f(x₁, x₂, …, x_n) = ∑c_jx_j

найти при ограничениях

∑a_ijx_j = b_i, i = 1, 2, …, m,

x_j ≥ 0, j = 1, 2, …, n; b_i ≥ 0, i = 1, 2, …, m.

Векторная форма записи КЗЛП имеет вид:

max (min) f(x₁, x₂, …, x_n) = f(X) = CX

A₁x₁ + A₂x₂ + … + A_nx_n = B,

X ≥ 0

где: C = (c₁, c₂, …, c_n), X = (x₁, x₂, …, x_n);

СХ - скалярное произведение векторов С и X;

A₁, A₂, …, A_n - вектор-столбцы.

Запись X ≥ 0 означает, что все компоненты вектора X неотрицательны.

Матричная форма записи КЗЛП имеет вид:

max (min) f(X) = CX,

АХ = В,

Х ≥ 0.

где C = (c₁, c₂, …, c_n) - матрица-строка;

Х - матрица-столбец;

B - матрица-столбец;

A = (a_ij) — матрица размерности m × n, столбцами которой являются вектор-столбцы A₁, A₂, …, A_n.

Иногда используется стандартная форма записи ЗЛП:

max (min) f(X)= CX,

АХ ≤ (≥) В,

Х ≥ 0.

При этом запись вектор АХ меньше или равен (больше или равен) вектору В понимается так, что все компоненты вектора слева меньше или равны (больше или равны) соответствующим компонентам вектора справа.

Имеет место утверждение, что любую ЗЛП можно привести к каноническому виду.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2.2) k-й дополнительной (вспомогательной) переменной x_n+k ≥ 0 со знаком «—» в случае ограничения типа «≥» и знаком «+» в случае ограничения типа «≤».

Если на некоторую переменную x_p не накладывается условие неотрицательности, то делают замену переменных В преобразованной задаче все переменные неотрицательные.

Пример 1. Привести к каноническому виду следующую ЗЛП:

max f(x₁, x₂) = (x₁ + 2x₂)

2x₁ + 3x₂ ≤ 10

2x₁ + x₂ = 6

x₁ + x₂ ≥ 2

x_1,2 ≥ 0.

Сделаем замену переменных ; введем в левую часть первого ограничения дополнительную переменную х₃ ≥ 0 (со знаком «+») и в левую часть третьего ограничения дополнительную переменную х₄ ≥ 0 (со знаком «-»). Будем иметь КЗЛП:

Любая ЗЛП может быть приведена к стандартной форме (как добиться неотрицательности всех переменных показано выше), а ограничение типа равенства следует заменить на два ограничения типа неравенств со «встречными» знаками неравенств (одно неравенство типа «≤», другое - типа «≥»). Рассмотрим ЗЛП в стандартной форме записи:

max f(x₁, x₂, …, x_n) = ∑c_jx_j, (2.4)

∑a_ijx_j ≤ b_j, i = 1, 2, …, m, (2.5)

x_j ≥ 0, j = 1, 2, …, n. (2.6)

Положим n = 2, т.е. рассмотрим эту задачу на плоскости. Пусть система неравенств (2.5), (2.6) совместна (имеет хотя бы одно решение):

a₁₁x₁ + a₁₂x₂ ≤ b₁

a₂₁x₁ + a₂₂x₂ ≤ b₂

a_m1x₁ + a_m2x₂ ≤ b_m

x_1,2 ≥ 0.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_i1x₁ + a_i2x₂ = b_i, i = 1, 2, …, m. Условия неотрицательности определяют полуплоскости с граничными прямыми х₁ = 0, х₂ = 0 соответственно. Система совместна, поэтому полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы [1]. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Если в системе ограничений (2.5), (2.6) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i, i = 1, 2, ..., m, а условия неотрицательности -полупространства с граничными плоскостями х_j = 0, j = 1, 2, 3, соответственно. Если система ограничений совместна, то эти полупространства как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе ограничений (2.5), (2.6) n > 3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью ∑a_ij, x_j = b_i, i = 1, 2, …, m, а условия неотрицательности - полупространства с граничными гиперплоскостями х_j = 0, j = 1, 2, ..., n. Если система ограничений совместна, то по аналогии с трехмерным пространством она образует общую часть n-мерного пространства, называемую многогранником решений, т.к. координаты каждой его точки являются решением.

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

Если целевая функция (ЦФ) ЗЛП ограничена на многограннике решений (на плоскости — многоугольнике решений), то:

- существует такая угловая (крайняя) точка многогранника решений, в которой ЦФ достигает своего оптимума;

- каждый опорный план ЗЛП соответствует угловой точке многогранника решений.

Для решения ЗЛП необходимо исследовать только вершины (угловые точки) многогранника решений - области допустимых решений (ОДР), т.е. только опорные планы.

ЗЛП не имеет решения в случаях, когда:

- ОДР — пустое множество, т.е. при несовместности системы ограничений,

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

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

1. Строится многоугольная область допустимых решений ЗЛП - ОДР.

2. Строится вектор-градиент ЦФ в какой-нибудь точке X₀ принадлежащей ОДР - ∇ = (С₁, С₂).

3. Линия уровня С₁x₁ + С₂x₂ = а (а — постоянная величина) - прямая, перпендикулярная вектору-градиенту ∇ - передвигается в направлении этого вектора в случае максимизации f(x₁, x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x₁, х₂).

4. Для нахождения ее координат достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x₁, x₂), найденное в получаемой точке, является максимальным.

При минимизации f(x₁, x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум f(x₁, x₂) не существует.

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

Пример 2. Решить графическим методом следующую ЗЛП:

f(x₁, x₂) = (5x₁ + 4x₂) → max, min

2x₁ + 5x₂ ≤ 20

8x₁ + 5x₂ ≤ 20

5x₁ + 6x₂ ≤ 30

x_1,2 ≥ 0

1. Построим ОДР задачи (рис. 2.1).

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

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

2x₁ + 5х₂ = 20

8x₁ + 5x₂ = 40

5х₁ + 6х₂ = 30.

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

2. Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину ∇(5, 4) с началом координат О (0, 0).

3. Построим некоторую линию уровня 5x₁ + 4x₂ = а.

Пусть, например, а = 0. На рис. 2.1 такой линии уровня отвечает прямая ОХ, перпендикулярная вектор-градиенту.

4. При максимизации ЦФ необходимо перемещать линию уровня ОХ в направлении вектор-градиента, а при минимизации — в противоположном направлении. Предельными точками при таком движении линии уровня ОХ являются соответственно точка С и точка О. Далее она выходит из ОДР.

Рис. 2.1

Определим координаты точки С, являющейся точкой пересечения второй и третьей прямых:

8x₁ + 5x₂ = 40,

5x₁ + 6x₂ = 30,

x₁ ≈ 3,9; x₂ ≈ 1,7.

Таким образом, ЦФ в ЗЛП принимает при х₁ ≈ 3,9; x₂ ≈ 1,7 максимальное значение, равное

f(x₁, х₂) = 5 × 3,9 + 4 × 1,7 ≈ 26,3.

Поскольку координаты точки О равны х₁ = 0; x₂ = 0, то минимум ЦФ равен 0.

Указанные выше два случая отсутствия решений в ЗЛП иллюстрируются рисунками 2.2 и 2.3, на которых графически представлены задачи:

Как видно из рисунков, первая из приведенных ЗЛП не имеет решения, поскольку ее множество допустимых решений - пустое множество, вторая — поскольку не существует конечного максимума на неограниченном множестве допустимых решений.

Рис. 2.2

Рис. 2.3

Случай неединственности решения иллюстрируется следующей задачей:

max f(х₁, х₂) = (8х₁ + 10x₂)

5х₁ + х₂ ≤ 15

4х₁ + 5х₂ ≤ 40

x₂ ≥ 3

х₁ ≥ 0.

Графическое решение этой задачи показано на рис. 2.4.

Рис. 2.4

Линия уровня 8х₁ + 10х₂ = а параллельна одной из линий по границе области допустимых решений (4х₁ + 5х₂ = 40).

Это означает, что задача имеет бесконечное множество оптимальных решений (его задают координаты точек отрезка ВС), среди которых опорных оптимальных решений два соответственно в угловых точках В (0, 8) и С (5/3, 20/3).

Точки отрезка ВС задаются уравнением х₂ = 8 - 0,8х₁, где 0 ≤ х₁ ≤ 5/3. При этом максимальное значение целевой функции равно 80.

В общем случае, если оптимальными решениями являются опорные решения Х₁ и Х₂, то все множество оптимальных решений (отрезок, соединяющий две соответствующие соседние угловые точки) определяется выражением Х = αХ₁ + (1 - α)Х₂, где 0 ≤ α ≤ 1.

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

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

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):

max f(x₁, x₂, …, x_n) = ∑c_jx_j,

Sa_ij = b_i, i = 1, 2, …, m,

x_j ≥ 0, j = 1, 2, …, n; b_i ≥ 0, i = 1, 2, …, m.

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

Пример 3. Решить ЗЛП по модели задачи об оптимальном использовании ограниченных ресурсов:

max f(x₁, x₂) = (2x₁ + 3x₂)

х₁ + 3х₂ ≤ 300

x₁ + х₂ ≤ 150

х_1,2 ≥ 0.

Приведем задачу к каноническому виду путем введения дополнительных переменных х₃ и х₄:

max (2х₁ + 3х₂ + 0х₃ + 0х₄)

x₁ + 3x₂ + x₃ = 300

x₁ + x₂ + x₄ = 150

x_1,2,3,4 ≥ 0.

Найдем все опорные планы КЗЛП. Используя метод Жордана-Гаусса [1] выписываем все базисные решения системы уравнений:

х₁ + 3x₂ + x₃ = 300

x₁ + x₂ + x₄ = 150.

Последовательно будем иметь:

X₁ = (0, 0, 300, 150); Х₂ = (150, 0, -150, 0); Х₃ = (0, 150, -150, 0); X₄ = (75, 75, 0, 0); X₅ = (300, 0, 0, -150); Х₆ = (0, 100, 0, 50).

Среди этих базисных решений четыре опорных:

X₁ = (0, 0, 300, 150); Х₂ = (150, 0, 150, 0); Х₄ = (75, 75, 0, 0); Х₆ = (0, 100, 0, 50).

Указанным опорным планам на рис. 2.5 отвечают соответственно следующие угловые точки и значения ЦФ в них:

А (0, 0) и f (0, 0) = 0;D (150, 0) и f (150, 0) = 300; С (75, 75) и f (75, 75) = 375; В (0, 100) и f (0, 100) = 300.

Согласно теории ЛП оптимальное решение содержится среди опорных планов.

Таким образом, максимальное значение, равное 375, целевая функция f(x₁, х₂) достигает на опорном плане Х₄ = (75, 75, 0, 0), т.е. оптимальное решение рассматриваемой ЗЛП: х₁ = 75, x₂ = 75.

Рис. 2.5

Понятно, что при больших m и n найти оптимальный план, перебирая указанным выше способом (прямым перебором) все опорные ЗЛП весьма трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод, идея которого изложена в [1].

Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером m × m: в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).

Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден — (b₁, b₂, …, b_m, 0, …, 0).

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

Математический признак оптимальности состоит из следующих двух теорем.

1. Если для всех векторов А₁, А₂, ..., А_n выполняется условие Δ_j = Z_j – c_j ≥ 0, где Z_j = ∑c_j × a_ij, то полученный опорный план является оптимальным.

2. Если для некоторого вектора, не входящего в базис, выполняется условие Δ_j = Z_j - c_j < 0, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:

- если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

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

На основании признака оптимальности в базис вводится вектор А_k, давший минимальную отрицательную величину симплекс-разности:

Δ_k = min (Z_j- с_j), j = 1, 2, ..., n.

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

Q = min (b_i/a_ik) = b_r/a_rk, a_ik > 0, i = 1, 2, ..., m.

Строка А_r называется направляющей, столбец А_k и элемент a_rk - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы i-и строки - по формулам:

Значения нового опорного плана рассчитываются по формулам:

для i = r; i = 1, 2, …, m; i ≠ r.

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

Примечание. Для использования приведенной процедуры к минимизации линейной функции f(x₁, x₂, …, x_n) следует искать максимум — f(x₁, x₂, …, x_n), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

Пример. Решить ЗЛП по модели:

max (2х₁ + 3x₂)

х₁ + 3х₂ ≤ 300

х₁ + x₂ ≤ 150

x_1,2 ≥ 0.

Эту ЗЛП приведем к каноническому виду путем введения дополнительных переменных х₃ и x₄:

max (2х₁ + 3x₂+ 0x₃ + 0x₄)

x₁ + 3x₂ + х₃ = 300

х₁ +x₂ + х₄= 150

x_1,2,3,4 ≥ 0.

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0, 0, 300, 150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

В симплекс-таблице II получен оптимальный опорный план, поскольку все симплекс-разности (оценки) ∆_j ≥ 0, j = 1, 2, 3, 4. Оптимальные значения переменных равны: (основные переменные), (дополнительные переменные). Максимальное значение целевой функции равно 375.

Таким образом, в рассмотренной выше задаче об оптимальном использовании ограниченных ресурсов оптимальная производственная программа состоит в выпуске 75 ед. изделий первого вида и 75 ед. изделий второго вида. С этой программой связана максимальная выручка от реализации готовой продукции — 375 у.е.

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

Пример 4. Решить ЗЛП по модели:

max (-3x₁ - 2x₂ + 2x₃)

-x₁ - x₂ - x₃ + x₄ = 1

-2x₁ - x₂ + x₃ + x₅ = 1

x_1,2,3,4,5 ≥ 0

Решение этой КЗЛП осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

В симплекс-таблице I все компоненты вектора А₁, подлежащего вводу в базис, отрицательны. Задача не имеет решения вследствие неограниченности сверху целевой функции.

Симплекс-метод с искусственным базисом (М-метод) применяется в тех случаях, когда затруднительно найти первоначальный опорный план канонической формы задачи ЛП.

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки ∆_j теперь будет зависеть «от буквы М». Для сравнения оценок нужно помнить, что М — достаточно большое число.

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

Пример 5. Решить ЗЛП по модели:

min f(X) = 10x₁ – 5x₂

2x₁ – х₂ ≥ 3

х₁ + х₂ ≥ 2

х₁ + 2х₂ ≥ -1

х_1,2 ≥ 0.

Эту ЗЛП приведем к каноническому виду и одновременно перейдем к задаче «на максимум»:

max (-10х₁ + 5x₂)

2х₁ - х₂ – х₃ = 3

x₁ + x₂ - x₄ = 2

x₁ - 2x₂ + х₅ = 1

x_1,2,3,4,5 ≥ 0.

Для нахождения опорного плана переходим к М-задаче:

max (-10х₁ + 5х₂ – My₁ - My₂)

2x₁ - x₂ - x₃ + y₁ = 3

х₁ + x₂ – х₄ + у₂ = 2

-х₁ - 2х₂ + х₅ = 1

x_1,2,3,4,5 ≥ 0, y₁, y₂ ≥ 0.

Дальнейшее решение проводим в симплекс-таблицах:

В симплекс-таблице II получен опорный план исходной ЗЛП. Поскольку все симплекс-разности ∆_j ≥ 0, j = 1, 2, 3, 4, 5, то этот план является и оптимальным, т.е. (основные переменные), (дополнительные переменные), f(X^*) = 15 (исходная задача на минимум).

Особый случай симплексного метода - случай неединственности оптимального решения — иллюстрирует следующий пример.

Пример 6. Решить ЗЛП по модели:

max ( -15х₁)

3х₁ - 2х₂ ≤ 10

х₁ + 2х₂ ≤ 5

x_1,2 ≥ 0.

Приводим эту задачу к каноническому виду и решаем симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

В симплекс-таблице 0 все оценки ∆_j ≥ 0, j = 1, 2, 3, 4, т.е. план х¹ = (0; 0; 10; 5) является оптимальным. Кроме того, это решение не является единственным, поскольку для внебазисной переменной х₂ оценка ∆₂ = 0. Перейдем к следующему опорному плану: для этого введем в число базисных вектор А₂, а вектор A₄ исключим из базиса. Получим в симплекс-таблице I новый опорный план х² = (0; 2,5; 15; 0), который также является оптимальным (∆_j ≥ 0, j = 1, 2, 3, 4); т.е. целевая функция достигает максимума в двух угловых точках многогранника решений, а значит, и в любой точке, являющейся выпуклой линейной комбинацией этих угловых точек. Таким образом, в рассматриваемой задаче имеется бесконечное множество оптимальных решений, которое можно представить выражением: х = aх¹ + (1 - а)х², 0 ≤ а ≤ 1.

Примечание. Если опорный план вырожденный, т.е. среди его базисных компонент есть хотя бы одна нулевая, то минимальное оценочное отношение Q может оказаться равным нулю и значение ЦФ при переходе к новому опорному плану не изменится. В этом случае вычисления проводят аналогично рассмотренным. Теоретически возможно зацикливание (возврат к уже встречавшемуся базису), однако в практических задачах это встречается крайне редко.

Перейдем к рассмотрению специального инструментария для проведения экономико-математического анализа полученного оптимального плана - теории двойственности в линейном программировании.

При этом математические утверждения принимаются без доказательства - необходимо содержательно их понимать и уметь использовать в экономическом анализе.

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

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

Правило построения двойственной задачи определяется системой соотношений:

Исходная задача	Двойственная задача

Пример 7. Записать двойственную задачу к следующей исходной:

max f(X) = x₁ + х₂ + 2х₃

2х₁ + х₂ + х₃ ≤ 15

2х₂ + 3x₃ ≥ 10

x₁ + х₂ + 4х₃ = 8

x₁ ≥ 0, x₂ ≥ 0.

Для использования приведенного правила построения двойственной задачи умножим обе части второго неравенства на (-1). Будем иметь:

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

Пример 8. Записать двойственную задачу к исходной задаче

min f(X) = 2x₁ - 3x₂

2x₁ – x₂ ≤ -4

x₁ + х₂ ≥ 5

х₁ ≥ 0, х₂ ≥ 0.

Для использования приведенного выше правила умножим первое неравенство на -1.

Связь между оптимальными планами пары двойственных задач устанавливают теоремы двойственности.

Теорема 1 (основная теорема двойственности). Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны: max f(X) = f(X^*) = min φ(Y) = φ(Y^*). Если одна из двойственных задач неразрешима, то неразрешима и другая.

Теорема 2 (о дополняющей нежесткости). Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю. Если i-я компонента оптимального плана двойственной задачи положительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

То есть для оптимальных планов двойственных задач имеют место соотношения:

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

Пример 9. На станках трех видов С₁, С₂, С₃ последовательно обрабатываются детали четырех видов: D₁, D₂, D₃, D₄. Известно, сколько часов каждая деталь изготавливается на каждом станке, сколько времени может отработать каждый станок и какая прибыль может быть получена при продаже одной детали каждого вида. Данные для решения задачи содержатся в таблице:

Найден оптимальный по критерию «максимум прибыли» план, предусматривающий выпуск трех деталей второго вида и одной детали третьего вида. Дать экономико-математический анализ оптимального плана.

Решение.

Обозначим через х_j = 1,4 - объем выпуска деталей j-го вида и запишем математическую модель задачи критерию «максимум прибыли»:

max (3x₁ + 4x₂ + 3x₃ + x₄)

2x₁ + 4х₂ + 8х₄ ≤ 12

7x₁ + 2х₂ + 2х₃ + 6х₄ ≤ 8

5x₁ + 8х₂ + 4х₃ + 3х₄ ≤ 48

x_j ≥ 0, j = 1, 2, 3, 4.

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

Проверим, как удовлетворяется система функциональных ограничений оптимальным планом X^* = (x₁ = 0, x₂ = 3, х₃ = 1, х₄ = 0):

2*0 + 4*3 + 8*0 = 12

7*0 + 2*3 + 2*1 + 6*0 = 8

5*0 + 8*3 + 4*1 + 3*0 = 28 < 48.

Значение целевой функции на этом плане равно

f(X) = 3×0 + 4×3 + 3×1 + 1×0 = 15.

Двойственная задача имеет вид:

min (12y₁ + 8y₂ + 48у₃)

2у₁ + 7y₂ + 5y₃ ≥ 3

4y₁ + 2y₂ + 8y₃ ≥ 4

2y₂ + 4y₃ ≥ 3

8y₁ + 6y₂ + 3y₃ ≥ 1

y_1,2,3 ≥ 0.

Для нахождения оценок у₁, у₂, у₃ используем вторую теорему двойственности. Поскольку третье ограничение в (*) выполняется как строгое неравенство, то у₃ = 0. Так как х₂ > 0 и x₃ > 0, то:

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

т.е.

Вычислим значение целевой функции двойственной задачи:

φ(Y) = 12×1/4 + 8×3/2 + 48×0 = 15, т.е. f(X*) = φ(Y*) = 15.

По первой теореме двойственности мы можем утверждать, что действительно найдены оптимальные значения двойственных переменных.

Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок (для определения этих границ существуют математические соотношения [1], которые реализованы в «Отчете по устойчивости» Excel) имеют место следующие свойства.

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

В рассматриваемом примере увеличение фонда времени работы станка С₁ на 1 час привело бы к росту максимальной суммы прибыли на 0,25 у.е. (у₁ = 1/4), а увеличение фонда рабочего времени третьего станка не повлияет на оптимальный план выпуска продукции и сумму прибыли.

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

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

В примере 3 недефицитным ресурсом является фонд рабочего времени станка С₃ поскольку у₃ = 0.

Острее ощущается дефицитность ресурса С₂ (у₂ = 3/2) - он более дефицитен, чем ресурс С₂ (у₁= 1/4).

3. Двойственные оценки позволяют определять своеобразные «нормы заменяемости ресурсов»: имеется в виду не абсолютная заменяемость ресурсов, а относительная, т.е. заменяемость с точки зрения конечного эффекта и лишь в конкретных условиях данной задачи.

В нашем примере относительная заменяемость ресурсов определяется соотношением (нормой) 1/4 : 3/2 = 1:6.

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

если - выгодно,

если Δ_j > 0 - невыгодно.

Предположим в рассматриваемом примере следует решить вопрос о целесообразности включения в программу производство деталей нового (пятого) вида при затратах ресурсов станков: 8, 2 и 3 соответственно и ожидаемой удельной прибыли в: а) 6 у.е.; б) 1 у.е.

С учетом сказанного будем иметь в двух рассматриваемых случаях:

в случае а) - 1/4×8 + 3/2×2 + 3×0 - 6 = - 1 < 0 — выгодно расширение ассортимента;

в случае б) - 1/4×8 + 3/2×2 + 3×0 - 1 = 4 > 0 — невыгодно.

Ответим на вопрос, как изменится объем выпуска продукции и прибыль от ее реализации, если фонд рабочего времени станка С₁ увеличится на 2 часа, а фонд рабочего времени станка С₂ уменьшится на 1 час?

Предполагая, что эти изменения проходят в пределах устойчивости двойственных оценок (уметь проверить!) имеем:

2*0 + 4x₂ +8*0₄ = 14

7*0 + 2x₂ + 2x₃ + 6*0 = 7.

Отсюда определяется план выпуска в новых производственных условиях -Х= (х₁ = 0; х₂ = 3,5; х₃ = 0; х₄ = 0) соответственно прибыль составит 14 у.е., т.е. уменьшится на 1 у.е.

В заключении рассмотрим наш сквозной пример задачи о выборе производственной программы.

Поскольку в оптимальном плане исходной задачи т.е. х₁, x₂ > 0, то по теореме о дополняющей нежесткости для двойственных оценок имеют место равенства:

Из этой системы получаем

Двойственные оценки найдены правильно, поскольку:

φ(Y*) = 300×0,5 + 150×1,5 = 375 = f(X*).

Таким образом, оба ресурса, участвующие в производстве, дефицитны. При этом с позиции максимизации выручки более дефицитен второй ресурс. Прирост объема первого ресурса на единицу дает приращение выручки на 0,5 у.е., второго ресурса — на 1,5 у.е., т.е. сравнительная норма взаимозаменяемости составляет 1:3 (в пределах устойчивости двойственных оценок).

2.2. Специальные задачи линейного программирования

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

Для успешного решения транспортной задачи (ТЗ) необходимо знать как [1]:

1) получить первоначальное распределение поставок;

2) оценить оптимальность полученного распределения поставок (например методом потенциалов [1]);

3) перейти к улучшенному распределению поставок с помощью перераспределения поставки по циклу;

4) оценить единственность полученного оптимального плана перевозок.

В [1] рассмотрен пример решения транспортной задачи, в [7] - задача о назначениях.

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

Для понимания теории и практики решения этих задач необходимо хорошо усвоить суть и алгоритм решения транспортной задачи [1], решение ТЗ средствами пакета Excel проводится аналогично решению обычной ЗЛП [5].

2.3. Общие сведения о методах реализации моделей нелинейного и динамического программирования

Задача (модель) нелинейного программирования (НЛП) формулируется так же, как и общая задача оптимального программирования со следующими требованиями к целевой функции (ЦФ) и допустимой области: целевая функция f(x₁, x₂, …, x_n) и (или) одна из функций g_i(x₁, x₂, …, x_n) являются нелинейными:

min (max)f(x₁, x₂, ..., х_n),

g_i(x₁, x₂, ..., x_n){≤, =, ≥}b_i, i = 1, 2, ..., m,

x_j ≥ 0, j = 1, 2, ..., n.

У произвольной задачи НЛП некоторые или все свойства, характерные для задач ЛП, отсутствуют [1]. Вследствие этого задачи НЛП несравнимо сложнее задач ЛП и для них не существует общего универсального метода их решения (аналогично симплексному методу).

Есть целый ряд методов решения задач НЛП, некоторые из них рассмотрены в [1]. В пакете Excel реализован [8] метод множителей Лагранжа, идея которого заключается в преобразовании задачи условной оптимизации в задачу безусловной оптимизации, решение которой производится методами поиска — градиентными методами (метода первого порядка) или методами Ньютона (методы второго порядка). Наиболее распространенными являются градиентные методы.

Следует, на наш взгляд, согласиться с Б. Курицким [8], что для практического решения задачи оптимизации суть этих методов знать не обязательно.

Однако необходимо помнить, что существующие методы дают возможность находить только локальные оптимумы (помимо случаев, когда задачи обладают соответствующими свойствами выпуклости и вогнутости [1]). Если же есть подозрение, что в допустимой области ЦФ может иметь несколько оптимумов, то эту область следует разбить на ряд областей и в каждой из них определить свои локальные оптимумы, а затем из всех локальных оптимумов выбрать глобальный. В таком практическом подходе задача поиска глобального оптимума сводится к решению ряда задач, в которых ищется свой (локальный) оптимум.

Следует отметить, что в подавляющем большинстве практических задач оптимизации существует только один оптимум [8].

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

назначаются начальные значения искомых переменных так, чтобы ЦФ в начальной точке не была равна нулю,

в диалоговом окне Поиска решения в режиме Параметры не надо вводить «Линейная модель».

В Excel признаком достижения оптимума является величина относительного приращения ЦФ на каждой итерации . Оптимум считается достигнутым, если выполняется условие Δf_k ≤ Δf_зад, где Δf_зад - точность, назначаемая при решении задачи (Параметры).

Примером задачи НЛП является модель оптимального формирования портфеля ценных бумаг (модель Марковица минимального риска).

В этой модели приняты следующие обозначения:

x_j, - доля капитала, потраченная на покупку ценных бумагу j-го вида (весь выделенный капитал принимается за 1);

m_j - средняя ожидаемая доходность j-й ценной бумаги, (m_j называют эффективностью j-и ценной бумаги);

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

В предположении о некоррелированности ценных бумаг (их независимости) модель Марковица имеет вид:

Найти x_j, , минимизирующие риск портфеля ценных бумаг

(1)

при условии, что обеспечивается заданное значение эффективности портфеля m_p, т.е.

(2)

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

(3)

x_j ≥ 0, . (4)

В модели (1)—(4) нелинейной является ЦФ.

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

min(max) f (x₁, x₂,...,x_n);

g_i (x₁, х₂,..., х_n){≤, =, ≥}b_i, ;

x_j - целые неотрицательные ∀j∈< n' >.

Если множество индексов <n'>=<n>= {1, 2, ..., n}, то задачу называют полностью целочисленной, если <n'>⊂<n> , то - частично целочисленной.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel.

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

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

Достаточно часто при моделировании экономических процессов используется особый случай дискретности задачи - булевость переменных, т.е. переменные могут принимать значения 0 или 1 . Характерным примером этого случая является задача о назначениях.

Постановка задачи. Имеется n видов работ и m исполнителей этих работ. Известны экономические оценки эффекта C_ij, i = 1, 2, …, n, j = 1, 2, …, m; от назначения i-го исполнителя j-й вид работ. Требуется так распределить исполнителей по видам работ, чтобы суммарный эффект от назначений был максимальным.

ЭММ. Введем необходимые обозначения, пусть

Тогда математически задачу о назначениях можно записать в виде:

(на каждую работу должен быть назначен исполнитель);

(все исполнители должны получить назначение).

(*)

Для реализации этой ЭММ средствами Excel ограничение (*) в рабочей таблице Excel следует записать в виде:

(Этот прием используется во всех дискретных задачах с булевыми переменными.)

Отметим некоторые особые случаи приведенной задачи.

1. Если по той или иной причине некоторое назначение является недопустимым, то соответствующий элемент матрицы (C_ij)_m×n принимается равным (-М), т.е. его значение заведомо меньше любого другого значения. После этого в ходе решения мы сможем избежать данного назначения автоматически.

2. Если матрица (C_ij)_m×n не является квадратной, то по аналогии с открытой транспортной задачей в модели задачи о назначениях следует записать либо ограничение (число исполнителей m больше числа работ n) или (число исполнителей m меньше числа работ n).