Применение экономико-математического моделирования для обоснования

        В сельскохозяйственных предприятиях на стойловый период ежегодно составляется план использования заготовленных и закупаемых кормов по видам, половозрастным группам животных, а также по фермам или отделениям.

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

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

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

  Для построения экономико-математической модели оптимизации плана иснользования имеющихся кормов в хозяйстве необходима следующая информация:

1. виды  кормов   и   кормовых  добавок,   которыми   располагает 
   хозяйство на планируемый период;
2. виды  минеральных, витаминных добавок и возможность  их 
   приобретения;
3. виды скота и птицы, разводимых в хозяйстве, и деление их 
   на основные половозрастные и хозяйственные группы;
4. продуктивность  и  нормы  кормления  в расчете  на  одну  го 
   лову по различным половозрастным группам, по видам животных 
   и птицы;
5. предельно допустимые границы содержания отдельный кормов или  групп  кормов  в  рационе кормления  различных  половозрастных групп по видам животных и птицы;
6. количество кормо – дней пребывания различных половозрастных групп в хозяйстве на планируемый период;
7. предельно  допустимые  нормы   ввода   кормов,   минеральных 
   и   витаминных     добавок   в   рацион     различных     половозрастных 
   групп но видам животных и птицы;
8. себестоимость   кормов  и   цены   на   животноводческую   продукцию;
9. затраты   на   доставку   кормов  от   места  хранения  до   места 
   скармливания.

 
 

2 Раздел.

Методы решения  задач линейного программирования.

2.1 Графический  метод 

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

где (2.1) – целевая функция задачи, (2.2) – основные ограничения, (2.3) – условия  не отрицательности переменных.

      Неравенствам (2.2) на плоскости соответствуют полуплоскости. Чтобы их построить, необходимо сначала построить прямые, отделяющие эти полуплоскости. Уравнения отделяющих прямых получаем их  соответствующих неравенств путём замены знака неравенств на " = ". Отделяющие прямые лучше строить по двум точкам, которые являются точками пересечения с осями координат (у этих точек одна из координат равна нулю).

     Чтобы выбрать полуплоскость, соответствующую  заданному неравенству, достаточно проверить, принадлежит ли точка  начала координат (0,0) полуплоскости, подставив координаты (0,0) в неравенство. Если неравенство окажется справедливым, то принадлежит, в противном случае – нет.

     Неравенства (2.2) должны выполняться одновременно. Это означает, что решение задачи будет лежать сразу на всех построенных  полуплоскостях. С математической точки зрения это равносильно тому, что решение принадлежит пересечению построенных полуплоскостей.

     Условие не отрицательности переменных (2.3) требует, чтобы из пересечения полуплоскостей выбрали ту часть, которая лежит в 1 – ой четверти.

     Целевая функция (2.1), как функция от двух переменных имеет пространственное представление. Для изображения её на плоскости используют линии уровня, уравнения которых получаем из целевой функции, приравнивая её к различным числовым значениям:

     с₁х₁ + с₂х₂ = с, где с Î (– ∞, + ∞ ).                 (2.4)

     Достаточно  построить две линии уровня (выбрав произвольные значения С), чтобы, сравнив  на них значения целевой функции, определить направление max или min.

     Возможные варианты решения задачи линейного  программирования графическим методом представлены на рис 2.1.

 
 
 

Решим задачу линейного  программирования 

            2.2.     f(x) = – x₁→ max (min)

                      

Строим  отделяющие прямые.

1-я отд.  прямая

2х₁+х₂=4

х₁=0; х₂=4    (0;4)

х₂=0; х₁=2    (2;0) 

2-я отд.  прямая

2х₁+х₂=8

х₁=0; х₂=8    (0;8)

х₂=0; х₁=4    (4;0) 

3-я отд.  прямая

х₁-2х₂=3

х₁=0; х₂=-1,5  (0;-1,5)

х₂=0; х₂=3       (3;0) 

4-я отд.  прямая

-х₁+2х₂=6

х₁=0;х₂=3      (0;3)

х₂=0; х₁=-6    (-6;0) 

Линии уровня

1-я линия

-х₁=5

х₁=-5 

2-я линия

-х₁=-5

Х₁=5 

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

А=(1-я  отд. прямая)   (4 отд. прямая)

2х₁+х₂=4          х₂=4-2х₁                                    -5х₁= -2      х₂= 4-0,8   

-х₁+2х₂=6       - х₁+2(4-2 х₁)=6            х₁= 0,4        х₂= 3,2 

А(0,4; 3,2) 

В(2-я  отд. прямая)   (3-я отд. прямая) 

2х₁+х₂=8       х₁= 3+2х₂                              х₁=3+0,8

х₁ - 2х₂=3      2(3+2х₂) + х₂=8         х₁= 3,8

                     5х₂= 2

                     х₂= 0,4         

В(3,8; 0,4)

F (max)  А            -0,4

F (min)   В            -3,8 
 
 

2.2 Симплекс  метод

     Учитывая  тот факт, что целевая функция  достигает своего оптимального значения в одной из вершин многогранника  допустимых решений задачи линейного программирования, то всякая процедура, предусматривающая направленный перебор угловых точек области определения задачи, должна привести к отысканию оптимального решения. Эта идея положена в основу классического метода решения задач линейного программирования – симплекс – метода, который разработан Дж. Данцигом в 1947 году.

     Симплекс  – метод применяют к задачам  линейного программирования, заданным в каноническом виде, где элементы вектора правых частей ограничений принимают неотрицательные значения:

        (3.1)

      Основные  положения, на которых  базируется симплекс – метод

1. Каждая  вершина многогранника допустимых  решений обладает следующими  свойствами:

- m  её координат имеют значения ≥0 (их называют базисными переменными);

- остальные  (n - m) координат равны нулю (их называют свободными переменными);

- вектор  – столбцы матрицы коэффициентов  А, соответствующие базисным переменным вершины являются линейно независимыми, т.е. с- помощью линейных преобразований их можно привести к единичной матрице.

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

3. Переход  из одной вершины в другую  осуществляется с помощью метода  последовательного исключения неизвестных, который называется методом Жордана-Гаусса. В результате чего из базисного решения выводим одну переменную, а вводим другую. Причём, из свободных переменных, не вошедших в базис, вводим ту, которая больше всех уменьшает значение целевой функции. А из базисных переменных выводим ту, которая не нарушает условия неотрицательности базисных переменных у новой вершины. При этом вектор – столбцы матрицы ограничений А, соответствующие новой вершине, так же будет линейно независимыми, т.е. образовывать единичную матрицу. 

Алгоритм  симплекс – метода

1. Находим  первое опорное решение (угловую  точку).

2. Составляем  симплексную таблицу (см. рис.3.1).

3. Выясняем, имеется ли хотя бы одно  отрицательное число ∆j. Если таких чисел нет, то найденное опорное решение является оптимальным. Если же среди чисел ∆_j  имеются отрицательные, то либо переходят к новому опорному решению, либо устанавливают неразрешимость задачи, когда все коэффициенты столбца матрицы ограничений А, соответствующего отрицательному ∆_j, тоже отрицательны.

4. Направляющий столбец (номер вводимой в базис переменной) определяем наибольшим по абсолютной величине отрицательным числом ∆_j. Пусть это будет к-ый столбец.

5. Направляющая  строка (номер выводимой из базиса  переменной) соответствует минимальному из всех соотношений для положительных значений а_ik. Пусть это l – ая строка.

6. По  методу Жордана – Гаусса исключаем переменную Хк из всех ограничений, кроме  l –ого, где эта переменная должна быть с коэффициентом 1. Строим, новею симплекс – таблицу.

7. Переходим  к этапу 3.

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

   - метод естественного базиса,

   - метод искусственного базиса.

      Метод естественного базиса применяется для задач линейного программирования, записанных в виде (3.2), где все ограничения неравенства имеют тип "≤" и элементы вектора правых частей ограничений неотрицательны.

            (3.2)

      В этом случае задачу (3.2) приводим к каноническому  виду (3.3), вводя в левую часть каждого ограничения неравенства самостоятельную переменную, которые и будут образовывать естественный базис.

          (3.3)

      Метод искусственного базиса применяется для задач, заданных в каноническом виде, или с ограничениями смешанного типа. Если в задаче ограничения смешанного типа, то её сначала преобразуем к каноническому виду (3.1), причем нужно отслеживать, чтобы элементы вектора правых частей были неотрицательными, а затем в каждое ограничение равенство водим по самостоятельной переменной y_j , которые и будут образовывать искусственный базис. При этом в целевой функции переменные искусственного базиса записываются с большими отрицательными коэффициентами. В результате преобразований получим задачу вида (3.4).