18

Задача 1.3

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Решение

Составим экономико-математическую модель. Для этого обозначим число наборов удобрений: через x₁ – обычный, через x₂ – улучшенный наборы. Тогда, целевая функция будет иметь вид:

f (x) =3 x₁ +4 x₂→ min

Ограничения:

3х₁ +2х₂ ≥ 10 – по количеству азота,

4х₁ + 6х₂ ≥ 20 – по количеству фосфора,

х₁ + 3х₂ ≥ 7 – по количеству калия,

х₁≥0

х₂ ≥0

Строим область допустимых решений:

1. 3х₁ +2х₂ = 10

x₁ = 0, x₂ = 5

x₁ = 2, x₂ = 2

3*0+2*0<10 – следовательно, решением неравенства является полуплоскость выше прямой.

2. 4х₁ + 6х₂ = 20

x₁ = 2, x₂ = 2 ;

x₁ = 5, x₂ = 0 .

4*0+6*0<20 – следовательно, решением неравенства является полуплоскость выше прямой.

3. х₁ + 3х₂ = 7

x₁ = 1, x₂ = 2

x₁ = 7, x₂ = 0

1*0+3*0<7 – следовательно, решением неравенства является полуплоскость выше прямой.

Пересечением всех плоскостей является неограниченная область (заштрихованная область на графике).

Для определения направления движения к оптимуму построим вектор-градиент, соединив начало координат с точкой с координатами (3;4). Построим линию уровня. Она перпендикулярна вектору- градиенту.

Перемещаем линию уровня в направлении, противоположенном вектору-градиенту до тех пор, пока она не покинет пределов области допустимых решений. Крайняя точка области допустимых решений при этом движении является точка с координатами (2;2) – она и есть точка минимума.

Найдем ее координаты путем решения системы уравнений:

х₁= 2; х₂=2.

Значение целевой функции в точке с координатами (2;2) равно:

min f (x) = 3*2+4*2 = 14

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

Задача 2.3

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

Тип сырья	Нормы расхода сырья на одно изделие				Запасы сырья
	А	Б	В	Г
I II III	2 1 2	1 2 4	3 4 1	2 8 1	200 160 170
Цена изделия	5	7	3	6

Требуется:

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

2.Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.

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

4.На основе свойств двойственных оценок и теорем двойственности:

• проанализировать использование ресурсов в оптимальном плане исходной задачи;

• определить, как изменятся выручка от реализации продукции и план ее выпуска при увеличении запасов сырья I и II видов на 8 и 10 единиц соответственно и уменьшении на 5 единиц запасов сырья III вида;

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

Решение.

1.Сформулируем экономико-математическую модель задачи. Обозначим через x₁, x₂, x₃, x₄ количество продукции каждого типа. Тогда, целевая функция будет иметь вид: f (x) = 5 x₁ + 7 x₂ + 3 x₃ + 6 x₄ → max.

Ограничения:

2 x₁ + x₂ + 3 x₃ + 2 x₄ ≤ 200

x₁ + 2x₂ + 4 x₃ + 8x₄ ≤160

2 x₁ + 4 x₂ + x₃ + x₄ ≤170

x₁, x₂, x₃ , x₄ ≥0

Найдем оптимальное решение с помощью EXCEL. Введем исходные данные и ограничения:

Воспользуемся командой Поиск решения. Заполним окно Поиск решения:

В окне Поиск решения нажать на кнопку Выполнить. В диалоговом окне Результаты поиска решения нажать ОК. В результате:

Полученное решение означает, что максимальный доход 460 единиц можно получить при выпуске 80 изделий А и 10 изделий Г. При этом сырье II и III типа будет использовано полностью, а из 200 единиц сырья I типа будет использовано 180 единиц. Изделия Б и В убыточны, затраты на ресурсы превышают цену изготовления из них изделий.

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

Число неизвестных в двойственной задаче равно числу ограничений в исходной задаче. Следовательно, в двойственной задаче 3 неизвестных: y₁, y₂, y₃.

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

g (y) = 200 y₁ +160 y₂ +170 y₃→ min

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

Число ограничений в двойственной задаче равно числу переменных в исходной задаче. В исходной задаче 4 переменных, значит, в двойственной задаче 4 ограничения. В правых частях ограничений двойственной задачи стоят коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничений определяет стоимость ресурсов, затраченных на производство единицы изделия:

2 y₁ + y₂ +2 y₃ ≥ 5

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

3 y₁ +4 y₂ + y₃ ≥ 3

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

y₁, y₂, y₃ ≥0

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

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

2 y₁ + y₂ +2 y₃ = 5 0 + y₂ + 2 y₃ = 5

2 y₁ +8 y₂ + y₃ = 6 0 + 8 y₂ + y₃ = 6

y 3 = 34/15

y2 = 7/15

Подставим в систему, получим y₁ =0. Подставим значения y в целевую функцию.

200 * 0 + 160 * 7/15 + 170 * 34/15 = 460.

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

3. Сырье типа I используется не полностью, поэтому имеет нулевую двойственную оценку (y₁ = 0).Нулевая оценка ресурса свидетельствует о его недефицитности, которая возникла из-за невозможности его полного использования в оптимальном плане. Этот ресурс не влияет на план выпуска продукции. Данный ресурс не препятствует и дальше максимизировать целевую функцию.

4.На основе свойств двойственных оценок и теорем двойственности:

• если изделие вошло в оптимальный план, то в двойственных оценках оно не убыточно, т.е. стоимость сырья, затраченного на производство изделия, равна его цене. Такие изделия выгодны с точки зрения принятого критерия оптимальности. В задаче — это изделия A и Г. Если стоимость ресурсов, затраченных на производство одного изделия, больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В задаче в план выпуска не вошли изделия Б и В, потому что затраты по ним превышают цену. Сырье II и III имеют отличные от нуля оценки и - эти ресурсы полностью используются в оптимальном плане и являются дефицитными, т.е. сдерживающими рост целевой функции. Правые части этих ограничений равны левым частям.

• определим, как изменятся общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II видов на 8 и 10 ед. соответственно и уменьшении на 5 ед. запасов сырья III вида:

x1 + 2x2 + 4x3 + 8x4 = 160+10, x1 +8x₄ =170 , х4 = 35/3,

2х1 +4x2 ++ x3 + х₄ = 170 – 5. 2x1 + x4 = 165. x1 = 230/3

Значение целевой функции: 453,3.

460-453,3=6,7

Следовательно, выручка уменьшилась на 6,7 ден.ед.

• определим целесообразность включения в план изделия «Д» ценой 10 ден. ед., на изготовление которого расходуется по две единицы каждого вида сырья. Вычислим ∆ = 2*0 + 2* +2* -10 = - 3 < 0, т.е. затраты на производство данного изделия не превышают его цену, следовательно, включать такое изделие в план выгодно.