Формализация задачи

а) переменные задачи – объемы выпускаемой продукции x₁ и x₂;

б) – ограничения задачи:

6x₁ + 4x₂ ≤ 24 (по первому ресурсу b₁)

x₁ + 2x₂ ≤ 6 (по второму ресурсу b₂)

x₁, x₂ ≥ 0.

в) целевая функция – функция ежедневного дохода фирмы:

.

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

.

6x₁ + 4x₂ ≤ 24

x₁ + 2x₂ ≤ 6

x₁, x₂ ≥ 0

1.2. Графическое решение задачи

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

.

6x₁ + 4x₂ ≤ 24

x₁ + 2x₂ ≤ 6

x₁, x₂ ≥ 0

В этой задаче число переменных n = 2, а число ограничений m = 2.

Для графического решения задачи необходимо:

- построить область допустимых решений D;

- построить линии уровня целевой функции f(x) = c^Tx = f_0;, которые будут перпендикулярны вектору с;

- выбрать линию с максимальным уровнем: она пересекает множество D либо в одной вершине, либо в двух вершинах. В первом случае имеем одно оптимальное решение, а во втором случае – бесчисленное множество оптимальных решений.

На рис.1.1 изображены : а) выпуклое (ограниченное по расстоянию) множество допустимых решений D, б) линии уровня целевой функции f(x), перпендикулярные вектору с = (5, 4)^Т. Линия максимального уровня проходит через вершину х^* с координатами х₁^* = 3, х₂^* = 1.5, являющейся оптимальным решением задачи. Максимальное значение целевой функции в этой точке равно f^* = f(x^*) = 21000. Таким образом, искомое решение есть х^* = (x₁^*, x₂^*)^T = (3, 1.5)^T, f^* = f(x^*) = 21000.

Очевидно, что найденные оптимальные значения х^* и f^* зависят от параметров задачи с_j, j = 1, …, n, b_i, i = 1, …, m, a_ij, i = 1, …, m, j = 1, …, n, другими словами, х^* = х^*(с, b_, А), f^* = f^*(с, b_, А). Поэтому, перед тем, как рекомендовать найденное решение к внедрению, необходимо провести его анализ чувствительности, т. е. решить вопрос о том, как влияют параметры задачи на оптимальное решение.

Рис. 1.1. Графическая иллюстрация решения.

1.3. Каноническая форма задачи

Основной метод решения задачи ЛП - симплекс-метод обычно применяется к ограничениям в виде равенства, т. е. Ax = b, x ≥ 0. Такая форма задачи называется канонической. Для ее построения неравенства исходной задачи преобразовываются в равенства с помощью искусственных переменных, которые также являются неотрицательными. В результате этого действия происходит расширение области решений исходной задачи, другими словами, она становится подмножеством области решения новой – канонической задачи.

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

свойства области исходной задачи, т. е. содержит ее в виде своего подмножества.

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

Для того чтобы преобразовать ограничения – неравенства этой задачи, добавим в каждое из m неравенств системы Ax  b по одной искусственной переменной у_i, i = 1,…, m, превратив тем самым неравенства в равенства , i = 1,…, m. Тогда новая форма задачи (расширенная, каноническая) будет иметь вид

,

, i = 1,…, m,

х_j  0 j; y_i  0  i

или в матричной форме

,

Ax + Iy = b

х, y ≥ 0

где I – единичная матрица размерности (mхm). В принципе, в новой задаче можно выполнить обозначение переменных, например, х_{п+ i} = y_i, i = 1, …, m, и представить расширенную задачу в форме

,

Ax = b

х ≥ 0

где вектор х содержит как старые, так и новые переменные, т. е. имеет размерность (m+n)x1, в матрице А уже появились новые столбцы, соответствующие столбцам единичной матрицы I, а последние m координат вектора с равны нулю, так как искусственные переменные отсутствуют в целевой функции. Сохраняя для числа переменных прежнее обозначение п + m: = п, можно вновь считать, что расширенная задача (т.е. каноническая форма) имеет п переменных и m ограничений, другими словами, считать матрицу А размерности (mхп), причем, m  п.

Иллюстрирует построение канонической формы задачи на примере

f(x) = 2x₁ + 3x₂ + 5x₃ → max.

x₁ + x₂ - 5x₃ ≥ -5

-6x₁ + 7x₂ - 9x₃ ≤ 4

x₁ + x₂ + 4x₃ = 10

x₁ , x₂ , x₃ ≥ 0

Два из трех ограничений этой задачи являются неравенствами. Преобразуем их в равенства с помощью неотрицательных искусственных переменных х₄ ≥ 0 и х₅ ≥ 0. Первое ограничение примет вид x₁ + x₂ - 5x₃ - х₄ = -5, а второе – вид -6x₁ + 7x₂ - 9x₃ + х₅ = 4. В канонической форме новая задача есть

f(x) = 2x₁ + 3x₂ + 5x₃ → max.

x₁ + x₂ - 5x₃ - х₄ = -5

-6x₁ + 7x₂ - 9x₃ + х₅ = 4

x₁ + x₂ + 4x₃ = 10

x₁ , x₂ , x_3, х₄, х₅ ≥ 0

Теперь целевую функцию можно записать в виде , где с = (2, 3, 5, 0, 0)^Т, х = (х₁, …, х₅)^Т, а ограничения имеют вид Ах = b, где матрица А имеет размерность (3х5), последние два столбца которой соответствуют переменным х₄ и х₅.