Задачи по "Экономико-математическому моделированию"

    Задача 1.8

    Решить  задачу графическим  методом

    Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁, S₂, S₃. Содержащие числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведен в таблице.

      Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.

    Необходимо  составить дневной рацион, имеющий минимальную стоимость, в котором содержание питательных веществ каждого вида было не менее установленного предела.

    Решение

      Обозначим через Х₁ и Х₂ количество кг корма I и II вида.

      Тогда целевая функция будет иметь  вид:

      F(x) = 4Х₁ + 6Х₂ = ® min

      при следующих ограничениях:

     3Х₁ + 1Х₂  ≥9             (1)(ограничение по питательному веществу S₁)

     1Х₁ + 2Х₂ ≥ 8      (2)(ограничение по питательному веществу S₁)

     Х₁ + 6Х₂≥  12      (3)(ограничение по питательному веществу S₁)

      Х₁, Х₂ ³ 0.        (4)(условия неотрицательности переменных) 

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

     Ограничения (1)-(4) линейные, поэтому каждое из неравенств задает соответствующую полуплоскость, ограниченную прямой, уравнение которой получается, если знак неравенства заменить на знак равенства.  Последние два ограничения (4) задают первую четверть.  

     

 
 
 

  
 
 
 
 

     

       

     Получаем  ОДР – на графике многоугольник  АВCО.

     Целевая функция f(Х) = 4х₁ + 6х₂  является линейной функцией. Проводим линию уровня проходящую через ОДР (при с = 40).

     Строим  вектор градиент целевой функции Ñ(4, 6).

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

      3Х₁ + 1Х₂ ≥9

     Х₁ + 2Х₂ ≥8

     X₁ = 2 

      X₂ = 3  

     т.В(2; 3)

     Минимальное значение целевой функции:

     f_max(Х) = 4*2 + 6*3 = 26 (ден.ед)

     Если  решать задачу на максимум, то нельзя получить конкретное решение, т.к. ОДР сверху не ограничена, множество решений  бесконечно. Т.е. при увеличении числа  единиц бесконечно будет расти стоимость дневного рациона.

     Решение в Excel:

    Создаем форму для решения и вводим формулы. Задаем целевую ячейку и ограничения: 

    Получаем  решение:

 
 

     Ответ: Минимальная стоимость дневного рациона при соблюдении необходимого вида питательных веществ будет равна 26 ден. ед., если в него войдет 2 кг корма I и 3 кг корма II. 

    Задача 2.8

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

    Требуется:

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

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

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

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

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

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

    •    оценить целесообразность включения в план изделия четвертого вида ценой 7 у.е., если нормы затрат сырья 2, 4 и 3 единицы.

    Решение

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

      Обозначим:

      x₁ – количество сырья первого вида,

      x₂ – количество сырья второго вида,

      x₃ – количество сырья третьего вида,

      Целевая функция имеет вид:

      max F(Х) = 3х₁ + 2x₂  + 5x₃

      Получим систему ограничений:

     x₁ + 2x₂ + x₃  ≤ 430,

     3x₁ + 2x₃  ≤ 460,

     х₁ + 4x₂ ≤ 420,

     х_1,2,3 ≥ 0

    Получим оптимальный план выпуска продукции с помощью надстройки Поиск решения (Ехсеl).

    Создаем форму для решения и вводим формулы. Задаем целевую ячейку и ограничения: 

    Получаем  решение:

      

    Максимальное  значение целевой функции составляет F_max(Х) = 1350 ден. ед. Оптимальный план выпуска продукции: x₁ = 0, x₂ = 100, x₃ = 230. 

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

    Число неизвестных в двойственной задаче равно числу функциональных ограничений  в исходной задаче. Исходная задача содержит 3 ограничения: по типам сырья  I, II и III. Следовательно, в двойственной задаче 3 неизвестных:

    y₁ – двойственная оценка ресурса «сырье I типа», или «цена» сырья I типа;

    y₂ – двойственная оценка ресурса «сырье II типа», или «цена» сырья II типа;

    y₃ – двойственная оценка ресурса «сырье III типа», или «цена» сырья III типа.

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

    min G(y) = 430y₁ + 460y₂  + 420y₃

    При ограничениях:

    y₁ + 3y₂ + y₃ ≥ 3,

    2y₁ + 4y₃ ≥ 2,

    y₁ + 2y₂ ≥ 5,

    y_1,2,3 ≥ 0

    Найдем  ее оптимальный план с помощью теорем двойственности. Из соотношений второй теоремы двойственности вытекают следующие условия:

    Если  то y_i = 0;

      Если  y_i > 0, то  

      Подставим значения x₁ = 0, x₂ = 100, x₃ = 230 в ограничения прямой задачи:

     1*0 + 2*100 + 1*230 = 430,      Þ y₁>0

     3*0 + 2*230 = 460                    Þ y₂>0

     1*0 + 4*100 = 400  < 420   Þ y₃=0

     Получаем  систему уравнений:

     y₃ = 0

      y₁ + 3y₂ + y₃ = 3,

     2y₁ + 2y₂ = 5,

     y₃ = 0

      y₂ = 2

     y₁ = 1,

     Решаем:

     y₁=1; y₂=2; y₃=0 

     min G(y) = 430*1 + 460*2  + 420*0 = 1350

     Условие первой теоремы двойственности выполняется, следовательно, рассматриваемый план оптимальный.

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

    Нулевое значение x₁ = 0 говорит о том что изделия A выпускать нецелесообразно, при его выпуске выручка будет уменьшаться.

    Нулевой значение y₃ = 0 показывает, что ресурс «сырье III типа» используется не полностью и не влияет на план выпуска продукции.

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

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

    Ресурсы «сырье I типа» и «сырье II типа» имеют отличные от нуля оценки 1 и 2 – эти ресурсы полностью используются в оптимальном плане и являются дефицитными, т.е. сдерживающими рост целевой функции.

    Наиболее  дефицитным является ресурс «сырье II типа».

    Ресурс  «сырье III типа» используется не полностью и не влияет на план выпуска продукции.

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

    DF(X) = Db₁y₁ + Db₂y₂