2. Нахождение оптимального плана производства

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

1. строится область допустимых решений (ОДР) задачи;

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

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

х₁+ 4х₂= 90 (6)

Чтобы построить эту прямую, нужно определить координаты двух лежащих на ней точек. Для этого следует приравнять к нулю одну из координат и найти из уравнения прямой (6) значение второй координаты. Если х₁= 0, тох₂= 22.5, а еслих₂= 0, тох₁=90. Значит, граничная прямая, задаваемая уравнением (6), проходит через точких¹ = (0, 22,5) их² = (90, 0).

Эта прямая делит плоскость на две полуплоскости. Чтобы определить, какая из них искомая, возьмем в качестве "пробной" точки начало координат О = (0, 0). Так как 0 + 4·0 < 90, то координаты этой точки удовлетворяют неравенству (2). Значит, полуплоскость, которой принадлежит начало координат, является искомой. Это показано с помощью стрелок на рис. 1.

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

4х₁+ 2х₂= 80.

Эта прямая проходит через точки х¹ = (0, 40) их² = (20, 0).

Соответственно, уравнение граничной прямой полуплоскости, задаваемой неравенством (4), имеет вид:

2х₁+ 4х₂= 140.

Эта прямая проходит через точки х¹ = (0, 35) их² = (70, 0).

Подстановка в неравенства (3) и (4) координат точки О = (0, 0) показывает, что она удовлетворяет обоим неравенствам. Поэтому искомыми в обоих случаях являются нижние полуплоскости, содержащие эту точку. Условия неотрицательности (5) показывают, что ОДР лежит в первом квадранте системы координат.

ОДР состоит из точек, которые удовлетворяют всем ограничениям задачи. Следовательно, это множество является пересечением построенных полуплоскостей и представляет собой многоугольник ОАВD(см. рис. 1).

Д

Рис. 1. Графическое решение задачи фирмы

ля нахождения оптимального плана построим вектор градиентаОС = (9, 8), задающий направление возрастания целевой функции. Затем проведем перпендикулярно этому вектору прямую, проходящую через начало координат. Эта прямая является линией нулевого уровня целевой функции и задается уравнением 9+ 8= 0.

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

Ее решение: . Таким образом, оптимальным планом в задаче фирмы будет выпуск 10 единиц изделия 1 и 20 единиц изделия 2. Выручка фирмы составиттыс. руб.

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

Построим двойственную задачу к задаче фирмы.

Z= 9х₁+ 8х₂max,

u₁↔1х₁+ 4х₂≤ 90,

u₂↔ 4х₁+ 2х₂≤ 80,

u₃↔ 2х₁+ 4х₂≤ 140,

х₁ ≥ 0,х₂ ≥ 0.

Для этого используются следующие правила:

1) каждому общему ограничению прямой задачи соответствует переменная двойственной задачи. В нашей задаче три общих ограничения. Следовательно, двойственная задача имеет три переменных, которые мы обозначим через u₁,u₂,u₃.

2) каждой переменной x_jпрямой задачи соответствует ограничениеjдвойственной задачи. Следовательно, двойственная задача имеет два ограничения.

3) коэффициентами при переменных в целевой функции двойственной задачи становятся элементы вектора ограничений прямой задачи, причем тип экстремума меняется на противоположный;

4) элементами вектора правой части двойственной задачи становятся коэффициенты при переменных в целевой функции прямой задачи;

5) каждый столбец в матрице ограничений прямой задачи формирует ограничение двойственной задачи;

6) тип неравенства в ограничениях меняется на противоположный;

7) переменные двойственной задачи удовлетворяют стандартным условиям неотрицательности u_i ≥ 0.

Таким образом, двойственная задача имеет следующий вид:

90u₁ + 80u₂ + 140u₃ min,

х₁ ↔ u₁ + 4u₂ + 2u₃ ≥ 9,

х₂↔ 4u₁+ 2u₂+ 4u₃≥ 8,

u₁ ≥ 0,u₂ ≥ 0,u₃≥ 0.

Так как прямая задача имеет оптимальное решение, то по первой теореме двойственности двойственная задача также имеет оптимальное решение u^*. Для его нахождения используем соотношения дополняющей нежесткости:

,

Подставим оптимальные значения переменных прямой задачи в левые части ее ограничений:

,

,

.

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

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

.

Так как , то для нахождения оптимальных значений оставшихся переменных двойственной задачи достаточно решить систему уравнений:

Ее решение таково: = 1 и=2. Следовательно, оптимальным решением двойственной задачи будет векторu^*= (1, 2, 0).

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

1. Z^* = — значение целевой функции в прямой задаче;

2. W^* = — значение целевой функции в двойственной задаче.

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

Анализ полученного решения показывает, что дефицитными ресурсами являются сырье и оборудование, так как оба эти ресурса имеют положительную оценку. Так как оценка оборудования выше, чем оценка сырья, то оборудование — наиболее дефицитный ресурс. Труд является недефицитным ресурсом, поскольку не полностью используется в производстве. Он имеет нулевую оценку. В оптимальный план выпуска вошли оба вида продукции. Их выпуск имеет нулевую рентабельность, если затраты ресурсов оценивать в найденных оптимальных оценках.