Математическое моделирование

Гл.2 Линейное программирование. 

§1.Оптимизационные  модели. Общая задача оптимизации.

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

       Для составления математической  модели такой задачи необходимо:

1. Ввести  и обозначить переменные и  параметры задачи:

 а) экзогенные – переменные,  которые  задаются вне модели, т.е.                          известны заранее;

     б) параметры –  это коэффициенты уравнений модели;

          в) эндогенные – те, которые  определяются в ходе расчётов  по модели и не задаются  извне, их обычно записывают  в виде вектора Х=(х₁, х₂, …, х_n).

2. Составить  систему ограничений:

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

В общем случае ограничения имеют вид:

   j₁(x₁, x₂, …, x_n) {£, =, ³} 0

   j₂ (x₁, x₂, …, x_n) {≤, =, ≥} 0

                  ………………………………….

                  j _m (x₁, x₂, …, x_n) {£, =, ³} 0. 

3. Задать целевую  функцию.

      Целевой функцией называется функция вида f(X) = f(x₁, x₂, …, x_n), которая характеризует качество выполнения задачи и экстремум которой нужно найти.

      В самом общем виде задача оптимизации математически записывается так:

     Найти X = (x₁, x₂, …, x_n) такое, что целевая функция f(Х) = f(x₁, x₂, …, x_n) принимает максимальное или минимальное значения при выполнении условиq (1).

      Множество всех значений X = (x₁, x₂, …, x_n), удовлетворяющих условиям (1) называется множеством допустимых (возможных) решений D. 

      Таким образом, задачу оптимизации можно  сформулировать так: из всех допустимых решений X Î D найти оптимальное решение, т.е. такое, при котором целевая функция f(Х) достигала бы своего наибольшего (наименьшего) значения:

Х₀ – оптимальное решение  Û Х₀ Î D: f(X₀) ³ f(X) " Х Î D.

     Методы  решения оптимизационных задач  зависят как от вида целевой функции  f(X), так и строения допустимого множества решений D, заданного ограничениями (1). Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

      В математическом программировании принято  выделять следующие основные задачи в зависимости от вида целевой  функции и вида ограничений (1):

       - задачи линейного программирования (ЗЛП): если целевая функция f(X) и ограничения (1) линейны;

       - задачи целочисленного программирования (ЗЦЛП): если ставится условие целочисленности переменных х₁, х₂, …, х_n.

       - задачи нелинейного программирования (ЗНП): если хотя бы одно из выражений -  целевая f(X) или хотя бы одна из функций ограничения j_i(X), i= (1,m)  - нелинейны.

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

      Рассмотрим  несколько примеров задач и их математические модели, реализуемые  методами математического (линейного) программирования. 

§2. Примеры задач  линейного программирования (ЗЛП).

2.1.  Задача об использовании ресурсов (задача планирования производства)

      Пусть предприятие имеет m видов ресурсов R₁, R₂, …, R_m в количествах соответственно b₁, b₂, …, b_m условных единиц. Предприятие выпускает n видов продукции Т₁, Т₂, …, Т_n. Обозначим a_ij – число единиц ресурса R_i (i=1,m) необходимое для изготовления единицы продукции T_j (j=1,n). Доход, получаемый предприятием от реализации единицы каждого вида продукции соответственно равен с₁, с₂, …, с_n (с_j, j=1,n).

     Требуется составить такой план производства (т.е. при данных ресурсах выпустить такую комбинацию продукции), при котором доход предприятия оказался бы максимальным.

      Решение.

      Обозначим через х₁, х₂, …, х_n – количество продукции соответственно Т₁, Т₂, …, Т_n. Очевидно, доход предприятия от реализации продукции имеет вид f = с₁x₁ + с₂x₂ + … + с_nx_n. (Это целевая функция).

      Общее количество i – го ресурса R_i (i=1,m), используемого при выпуске всех видов продукции Т₁, Т₂, …, Т_n равно a_i1x₁ + a_i2x₂ + … + a_inx_n. Эта сумма не должна превышать запасов этого вида ресурса b_i, т.е. a_i1x₁ + a_i2x₂ + … + a_inx_n. £  b_i (i=1, m). Таким образом, получим систему ограничений в виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n £ b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n £ b₂

_{…………………………………………..}

a_m1x₁ + a_m2x₂ + … + a_mnx_n £ b_m 

(2)      x₁ ³ 0, x₂ ³ 0,…, x_n ³ 0. 

      Требуется найти значение переменных х₁, х₂, …, х_n удовлетворяющих условиям (1) и (2) и максимизирующих целевую функцию:           

     f =S с_jх_j ® max

   

 2 .2.  Задача составления рациона (задача о диете или о смесях). 

      Имеется n видов кормов К₁, К₂, …, К_n, содержащие питательные вещества S₁, S₂, …, S_m. Известен необходимый минимум содержания в рационе питательного вещества S_i - b_i (i=1, m).  Известно a_ij – число единиц питательного вещества S_i, содержащееся в единице корма K_j - ого вида. Стоимость единицы корма K_j – ого вида  - с_j (j = 1, n). Требуется составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

      Решение:

      Обозначим х₁, х₂, …, х_n – количество кормов К₁, К₂, …, К_n,входящих в дневной рацион. Тогда этот рацион будет включать a_i1x₁ + a_i2x₂ + … + a_inx_n единиц питательного вещества S_i (i=1, m).Так как содержание веществ S_i (i=1, m) в рационе должно быть не менее b_i единиц, то получим следующую систему ограничений:

     a₁₁x₁ + a₁₂x₂ + … + a_1nx_n ³ b₁

     a₂₁x₁ + a₂₂x₂ + … + a_2nx_n ³  b₂   (4)      x₁³ 0, x₂ ³ 0,…, x_n³ 0.

          _{…………………………………………..}

     a_m1x₁ + a_m2x₂ + … + a_mnx_n ³  b_m

Общая стоимость рациона имеет вид:    (5) f = с₁x₁ + с₂x₂ + … +с_nx_n® min.

Найти такое решение Х = (х₁, х₂, …, х_n), удовлетворяющее условиям (3) и (4), при котором функция (5) принимает минимальное значение. 

2.3.  Задача об использовании  мощностей (о загрузке  оборудования). 

      Предприятию задан план производства продукции  по времени и номенклатуре: требуется  за время Т выпустить b₁, b₂, …, b_n единиц продукции соответственно P₁, P₂, …, P_n видов. Продукция производится на станках S₁, S₂, …, S_m – станки. Для каждого станка известны производительность a_ij (т.е. число единиц продукции Р_j (j=1,n), которое можно произвести на станке S_i (i=1, m)) и затраты c_ij на изготовление продукции Р_j –ого вида на станке S_i (i=1, m) в единицу времени.

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

     Решение:

     Обозначим x_ij – время, в течение которого станок S_i (i=1, m) будет занят изготовлением продукции Р_j (j=1,n). Так как время работы каждого станка ограничено и не превышает времени Т, то для каждого станка справедливо:

     x₁₁ + x₁₂ + … + x_1n £ Т