Построение математической модели

Задача 1

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

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

Требуется:

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

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

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

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

Построение математической модели

Необходимо найти объемы выпуска каждого изделия. Поэтому модель должна содержать две переменные: х ₁ — количество выпускаемых изделий 1 и х ₂ — количество выпускаемых изделий 2. Производственная программа (план) выпуска изделий задается вектором х = (х ₁, х ₂). Ее можно выполнить лишь тогда, когда он будет обеспечен необходимым количеством ресурсов. Поэтому модель должна включать для каждого ресурса, используемого в производстве, ресурсное ограничение вида

расход ресурса для выпуска изделий ≤ наличный объем ресурса (*)

Подсчитаем, сколько сырья понадобится для выпуска плана х. Чтобы выпустить х ₁ единиц изделия 1, нужно затратить х ₁ кг сырья; а выпуск х ₂ единиц изделия 2 потребует 4 х ₂ кг сырья. Значит, всего для выполнения плана х требуется х ₁ + 4 х ₂ кг сырья. Его наличный запас равен 90 кг. Поэтому ресурсное ограничение (*) для сырья имеет вид:

х ₁ + 4 х ₂ ≤ 90.

Ограничения по остальным ресурсам выглядят так:

4 х ₁ + 2 х ₂ ≤ 80 (оборудование),

2 х ₁ + 4 х ₂ ≤ 140 (труд).

Так как по своему экономическому смыслу х ₁ и х ₂ не могут быть отрицательными величинами, то кроме ресурсных ограничений должны также выполняться неравенства

х ₁ ≥ 0 и х ₂ ≥ 0.

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

Пусть х = (х ₁, х ₂) — некоторый план выпуска. Выручка Z от продажи х ₁ единиц изделия 1 и х ₂ единиц изделия 2 вычисляется по формуле

Z (х ₁, х ₂) = 9 х ₁ + 8 х ₂.

Основная цель производственной деятельности фирмы состоит в получении максимальной выручки от продажи произведенной продукции. Следовательно, Z является целевой функцией.

Таким образом, на множестве всех допустимых планов х = (х ₁, х ₂), ищется план, на котором достигает максимума целевая функция Z, т.е. математическая модель задачи имеет вид:

Z = 9 х ₁ + 8 х ₂ ® max, (1)

х ₁ + 4 х ₂ ≤ 90, (2)

4 х ₁ + 2 х ₂ ≤ 80, (3)

2 х ₁ + 4 х ₂ ≤ 140, (4)

х ₁ ≥ 0, х ₂ ≥ 0. (5)

Так как Z — линейная функция, а все ограничения — линейные неравенства, то эта модель является задачей линейного программирования.

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).

Перемещение линии уровня в направлении, задаваемом вектором градиента, показывает, что оптимальным планом является точка В. Она находится на пересечении граничных прямых 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.

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

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

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

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

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

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

,

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

,

,

.

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

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

.

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

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

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

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

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

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

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

Поиск по сайту: