Оптимальные модели. Линейное програмирование в оптимальном планировании

1. Понятие оптимального плана.

2. Применение методов линейного программирования в оптимальном планировании.

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

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

1. Понятие оптимального плана:

Существует 2 рода оптимального плана:

- план, обеспечивающий максимальный результат при заданных объемах ресурсов;

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

2. Применение методов линейного программирования в оптимальном планировании.

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

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 – область, – планы

  + (1 - )  , где 0    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)

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

x₂

c₂

c₁  x₁

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

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

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

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

x₂

D A

c₂

c₁ x₁

Ситуации:

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

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

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

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