Экономико - математические методы и модели

1) Оптимальным является план, обеспечивающий заданный результат при минимальных затратах ресурсов.

2) Оптимальный план – обеспечивает максимальный результат при заданном объеме ресурсов.

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

Разное: разные варианты учета продукции.

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

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

2) В любой оптимальной задаче всегда существует ограничение. Необходимо выбрать наиболее существенно ограничивающие условия.

3) Должен обязательно быть выбор.

4) Цель и ограничения должны быть записаны в линейной форме. Ограничение на ресурсы будут иметь линейную форму, если затраты прямо пропорциональны объему производства.

 

3. Постановка задачи оптимального планирования. Основные понятия.

Требуется найти набор n переменных

Набор, максимизирующий  линейную форму:  (х₁,  х₂,  х₃,…,  х_n)

z = с₁× х₁ + с₂ × х₂ + … + с_n × x_n ® max      (1)    и удовлетворяющий следующим уравнениям:

     b₁ = а₁₁ × х₁ + а₁₂ × х₂ + … + а_1n × х_n,

     b₂ = a₂₁ × х₁ + a₂₂ × х₂ + … + a_2n × х_n,         (2)          

     …………………………………

     b_n = a_m1 × х₁ + a_m2 × x₂ + … + a_mn × х_n,

            где х_j ³ 0,   j = ,  m < n  (3)  Подобная запись системы называется канонической формой; задача имеет смысл, если   m < n, если    m > n, то система имеет множество решений.

Условия:

1. Целевая функция на максимум.

2. Ограничения представлены в виде равенств.

3. b_i ³ 0, где b_i -  объем ресурсов.

4. Переменные неотрицательны

х_j – количество произведенной продукции разных видов;

с_i – коэффициенты эффективности (цены, прибыль);

а_ij – норма расхода  i-того ресурса на единицу продукции j-той отрасли.

Набор (х₁, х₂, х₃,…, х_n), удовлетворяющий условиям (2), (3) является планом. Таких планов множество, т.к. число уравнений меньше, чем число переменных. Множество всех планов составляют множество определения всех планов.

Область определения может быть: выпуклая, т.е. угол между гранями  > 90⁰ и невыпуклая.

 

         выпуклая

                                                          невыпуклая

Математически это выглядит:        ,    D – область,  – планы

a × + (1 - a) × ,  где    0 £ a £ 1.

Опорный план – это набор переменных, который соответствует границе области определения.

Р_j – коэффициенты, при   j – переменной.

          a_1j                    b₁

Р_j =    …   ;       b =    …   ;                                (4)

          a_mj                   b_m

Опорный план – это набор переменных, если в разложении  (4)  для х_j > 0 вектора P_j линейно независимы. Оптимальный план всегда опорный, достигается на границе области определения и содержит не больше m положительных переменных.

 

4. Графический метод решения задач линейного программирования. Геометрическая интерпретация:

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

z = c₁ × x₁ + c₂ × x₂  ® max             (1)

a_i1 × x₁ + a_i2 × x₂  £  b_i,   i =      (2)

x₁, x₂ ³  0                                       (3)

Если придать целевой  функции конкретное постоянное значение  a  на прямой   c₁ × x₁ + c₂ × x₂ = a      (4)    перпендикулярной  вектору n = (с₁, с₂). Для различных a будем иметь семейство параллельных прямых перпендикулярных вектору n, причем значение a увеличивается в направление вектора n.

    x₂

 

 

     c ₂

                 

      c₁       a                 x₁

Геометрическая  интерпретация целевой функции z  (1) – прямая, перпендикулярная нормальному вектору n, где она принимает постоянные значения.

Графическая интерпретация системы ограничений – это неравенства (2) и (3), решения которых – полуплоскости.

Область определения (D) – общая часть всех полуплоскостей, это выпуклый многоугольник, он не обязательно замкнут.

Графический метод решения:  строится область определения; определяется нормальный вектор, проводится прямая a перпендикулярная вектору и пересекающая область определения; двигаем прямую a параллельно себе по вектору n до крайней точки, пока она не примет оптимальное значение. 

         x₂

                               D                   A

          c₂

 

                             

                             c₁               x₁

Ситуации:

1) Единственное решение – предельное  значение совпадает с вершиной  D;  

2) Множество решений – предельное  решение совпадает со стороной многоугольника; 

3) Бесконечное множество решений; 

4) нет решения – область определения  пуста, нет ни одной общей  точки.

 

 

 

 

 

 

АЛГОРИТМ  СИМПЛЕКСНОГО  МЕТОДА

 

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

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

Симплекс - метод  позволяет перейти к соседней вершине области определения, в которой более оптимальное решение.

z = c₁ × x₁ + c₂ × x₂ +...+ c_n × x_n  → max

   x₁ + … a_{1, m+1} × x _m+1  +…+ a_1j × x_j +…+ a_1n × x_n  = b₁,

   x₂ + … a_{2, m+1} × x _m+1  +…+ a_2j × x_j +…+ a_2n × x_n = b₂,

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

   x_m + … a_{m, m+1} × x _m+1 +…+ a_mj × x_j +…+ a_mn × x_n = b_m.

         где    х₁,  х₂,… х_n ³ 0.

Исходное оптимальное  решение:  х₁ = b₁,  x₂ = b₂,  x_m = b_m,  x_m+1 = 0,  x_n = 0 – опорный план, т.е. вектор p – линейно не зависимый. 

№ строки	Базисные перемен-ные	С	План	c1 x1	…	cm xm	cm+1 xm+1	… …	cj xj	… …	cn xn
1 2 … m	x1 x2 … xm	c1 c2 … cm	b1 b2 … bm	1 0 … 0	… 1 … …	0 0 … 1	a1, m+1 a2, m+2 … am, m+1	… … … …	a1j a2j … amj	… … … …	a1n a2n … amn
m +1				∆1	…	∆m	∆m+1	…	∆j		∆n

 ∆_j =        (1)   - оценка  j-той   переменной

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

1) Анализ опорного плана на оптимальность. Если все оценки ∆_j ³ 0, то план  оптимален. Если хотя бы одна оценка < 0, то необходим переход к другому плану, т.е. пересчет всех коэффициентов.

2) Выбор разрешающего элемента. Решаем вопрос о том, какую переменную ввести, а какую вывести: вводим переменную, у которой ∆_j < 0. Если таких много, то наибольшую по модулю. Рассматриваем отношение элементов вектора плана к положительным коэффициентам вводимой переменной:  (b₁ / a_1j ;   b₂ / a_2j ; … b_m / a _mj),      a ³ 0

Минимальное отношение покажет  строку выводимой переменной, например, b₂ / a_2j – min, тогда выводим х₂,   x_j – вводим.

а_2j  – разрешающий элемент, находится на пересечении х_j и х₂.

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

Два способа пересчета  оценочной строки: по формуле   (1)  или по правилу треугольника, а затем переходим к пункту 1.

Возможны различные случаи:

1. Единственное решение: если в оптимальном плане для всех небазисных переменных оценки больше нуля.

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

3. Оптимальное значение достигается в ∞ (бесконечности): если только одна переменная имеет отрицательную оценку, но среди коэффициентов нет ни одного положительного, т.е. мы не можем делить.

 

 

 

ОПТИМАЛЬНОЕ  ПЛАНИРОВАНИЕ  И 

ОПТИМАЛЬНЫЕ  ОЦЕНКИ

 

1. Экономический смысл двойственной задачи линейного программирования.

2. Взаимосвязь прямой  и двойственной задач линейного  программирования.

3. Свойства двойственных  оценок. Их экономическое содержание.

 

1. Экономический смысл двойственной задачи линейного программирования:

Допустим мы имеем  прямую задачу об использовании сырья. Для изготовления двух видов продукции  А и В  используются  s₁, s₂, s₃, s₄ – виды сырья. Необходимо определить план выпуска продукции с целью получения максимального дохода.

Исходные данные о  наличии и использовании сырья:

Вид сырья	Нормы расхода сырья		Запас сырья
	А	В
s1 s2 s3 s4	2 2 0 3	3 1 3 0	19 13 15 18
Доход	7	5

Пусть х₁ – количество продукции А,  х₂ – продукции В.

Прямая задача:  z = 7 × x₁ + 5 × x₂  ®  max

    2 × х₁ + 3 × х₂ £ 19    |  у₁    х₃

    2 × х₁ + х₂ £ 13         |  у₂    х₄

    3 × x₂  £  15               |  у₃    х₅

    3 × x₁ + 0  £ 18         |  у₄     х₆

 x₁, x₂ ³ 0

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

Правила для  построения двойственной задачи:

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

2. Если прямая задача на max, то двойственная на min и наоборот.

3. Неравенства в системе ограничений направлены в противоположную сторону.

4. Коэффициенты целевой функции двойственной задачи есть свободные члены прямой и наоборот (коэффициенты целевой функции двойственной задачи есть свободные члены исходной).

5. Между переменными прямой и двойственной задач есть соответствие: дополнительные переменные прямой соответствуют основным двойственной и наоборот.

6. О чем речь идет в неравенстве, то и оцениваем.

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

Экономический смысл: Решение двойственной задачи дает оптимальную систему условных оценок применяемых ресурсов.

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

Новая задача:

   2 × у₁ + 2 × у₂ + 3 × у₄ ³ 7

   3 × у₁ +  у₂ + 3 × у₃ ³ 5,

         где   у₁,  у₂,  у₃,  у₄  ³ 0. 

Рассмотрим первое уравнение: 2 × у₁ + 2 × у₂ + 3 × у₄ – оценка всего сырья (затрат), идущего на единицу продукции, а   7 – результат от единицы продукции.

F = 19 × у₁ + 13 × у₂ + 15 × у₃ + 18 × у₄  ®  min

Переменные  у  показывают оценку единицы соответствующего ресурса, показывает как повлияет на конечный результат деятельности (суммарный доход) дополнительная единица соответствующего ресурса. Целевая функция F – оценивает все ресурсы, которыми располагает предприятие.

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