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

   х₁    х₂     х₃    х₄     х₅     х₆

   у₅    у₆     у₁    у₂    у₃     у₄

Если знаем решение  двойственной задача, то решение исходной задачи получаем автоматически.

Переменные двойственной задачи у₁, у₂, у₃, у₄  равны оценкам соответствующих переменных исходной задачи в оптимальном плане.

 

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

     2 × х₁ + 3 × х₂ + х₃ = 19,    

     2 × х₁ +   х₂ + х₄ = 13,    

     3 × x₂ + х₅ = 15,    

     3 × x₁ + х₆ = 18.    

x₃ = 19,  x₄ = 13,  х₅ = 15,  х₆ = 18.

БП		План	7	5	0	0	0	0
			х1	х2	х3	х4	х5	х6
х3 х4 х5 х6	0 0 0 0	19 13 15 18	2 2 0 3	3 1 3 0	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1
∆j			-7	-5	0	0	0	0

   …                                       …                                                                  

х6 х2 х5 х1	0 5 0 7	3 3 6 5	0 0 0 1	0 1 0 0	9/4 2/4 -3/2 -1/4	-9/4 -2/4 3/2 3/4	0 0 1 0	1 0 0 0
∆j		50	0	0	3/4	11/4	0	0

                                     y₅           y₆          y₁          y₂           y₃         y₄

х₁ = 5,  х₂ = 3,  х₃ = 0,  х₄ = 0,  х₅ = 0,  х₆ = 3 – выпускаем продукции А – 5 штук, В – 3 штуки, сырье s₁  и s₂  используется полностью,  s₃ – недоиспользовано 6 единиц,  s₄ – 3 единицы.

у₁ = 3/4,  у₂ = 11/4,  у₃ = 0,  у₄ = 0,  у₅ = 0,  у₆ = 0,  F = 50 – в первую очередь необходимо закупать ресурс s₂.  Чем выше оценка, тем эффективнее ресурс.

Прямая задача:  max

,   i = ;   х_j ³ 0,   j = .

Двойственная  задача:   min 

,    .

              y_i ³ 0,      .

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

,  - оптимальные решения

   f ( ) =  g ( )

Теорема 2:  пусть = (х₁*,  х₂*,  … х_n*) - допустимое решение прямой задачи, а   = (y₁*, y₂*, … y_m*) - допустимое решение двойственной задачи. Для того чтобы и были оптимальными решениями необходимо и достаточно, чтобы выполнялись следующие соотношения:

            (1)

           (2)

Из теоремы 2 вытекает четыре условия дополняющей нежесткости:

1. Если переменная исходной задачи равна нулю  x_j* =0, то  S a_ij × y_i* >  c_j  отлично от нуля, т.е. если изделие невыгодно и оно не вошло в оптимальный план, то оценка затрат больше ре-зультата (дополнительная переменная соответствующего неравенства двойственной задачи > 0).

2. Если в оптимальном плане переменная исходной задачи больше нуля  x_j* > 0,  то из  (1)     S a_ij × y_i* = c_j соответствующее ограничение двойственной задачи выполняется как строгое равенство. Изделие, которое выгодно производить и оно вошло в оптимальный план, для него оценка затрат на одну единицу продукции равно результату от единицы продукции. Дополнительная переменная двойственной задачи равна нулю (если ограничения в виде равенства, соответствующая переменная больше нуля). Можно судить о выгодности производства по дополнительным переменным соответствующих ограничений двойственной задачи. Чем меньше дополнительные переменные, тем выгоднее производить эту продукцию. Самая выгодная продукция, у которой дополнительная переменная равна нулю.

3. Если сумма S a_ij × x_j* - b_i = 0, то из   (2)    y_i* > 0, если какое-либо ограничение прямой задачи выполняется как строгое равенство, то соответствующие переменные двойственной задачи больше нуля, т.е. если какой-либо вид ресурса полностью тратится на оптимальный план, то его оценка больше нуля.

4. Если S a_ij × x_j* - b_i < 0,  то из   (2)   y_i* = 0, если какое-то ограничение прямой задачи выполняется как неравенство, то соответствующая переменная двойственной задачи равна нулю, т.е.  если какой-либо ресурс потрачен не полностью на оптимальный план, то его оценка равна нулю.

Из пунктов 3 и 4 следует, что можно использовать переменные двойственной задачи для оценки дефицитности какого-либо: чем выше оценка переменной двойственной задачи, тем эффективнее ресурс.

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

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

Свойства двойственных оценок:

1. Оценки, как мера дефицитности ресурсов. Дефицитный  ресурс - полностью используемый в оптимальном плане, он имеет положительную оценку  S а_ij × x_j = b_i,   y_i > 0.

Избыточный (недефицитный) ресурс – не полностью используемый в оптимальном  плане, имеет нулевую оценку. S а_ij × x_j < b_i, × y_i = 0    чем больше оценка, тем дефицитнее (эффективнее) ресурс.  

2. Оценки, как мера влияния ограничения на целевую функцию.  Df ( ) = y_i^* × Db_i (из 1-ой теоремы) – величина двойственной оценки характеризует прирост / снижение значения целевой функции при увеличении / уменьшении ресурса  b_i на одну единицу.

3. Оценки, как инструмент для определения эффективности отдельных вариантов плана. Это свойство вытекает из 1 и 2 условия дополняющей не жесткости, по величине S a_ij × y_i^* - c_j можно судить об эффективности того или иного варианта плана. Если D = êS a_ij × y_i^* - c_j ê= 0, то этот вариант плана оптимальный. Если D = êS a_ij × y_i^* - c_j ê® 0, то этот вариант плана рациональный (не плохой). Дополнительная переменная двойственной задачи характеризует соответствующий вариант плана.

4. Оценки, как инструмент балансирования суммарных затрат и результата  z  (x^*)= F(y^*) 

5. Двойственная оценка относительно устойчива, т.е. при небольших изменениях свободных членов прямой задачи двойственная оценка не меняется ® 1, 2, 3 действительны для небольших изменений.

 

 

 

 

НАХОЖДЕНИЕ  ИСХОДНОГО  ОПОРНОГО  ПЛАНА

 

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

если задача составлена на минимум, то  ´ (-1)  для того, чтобы она была на максимум; 

если ограничения £, то в левую часть добавляем дополнительные переменные;

если ограничения ³, то из левой части вычитаем дополнительные переменные;

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

Исходное опорное решение  задано, если среди коэффициентов  системы ограничений можно выделить единичный минор порядка  m,  где m – число уравнений. Если все ограничения £, то коэффициенты дополнительных переменных и будут образовывать единичный минор. Если все ограничения   =,   то единичного минора нет:

z = c₁ × x₁ + c₂ × x₂ + … + c_n × x_n

    a₁₁ × x₁ + a₁₂ × x₂ + … + a_1n × x_n  =  b₁,

    a₂₁ × x₁ + a₂₂ × x₂ + … + a_2n × x_n  =  b₂,

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

    a_m1 × x₁ + a_m2 × x₂ + …+ a_mn × x_n =  b_m.

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

Формируют дополнительную задачу (М-задача). В ней среди  коэффициентов будет единичный  минор. В любом уравнении искусственно добавлена неотрицательная переменная:

    a₁₁ × x₁ + a₁₂ × x₂ + … + a_1n × x_n + w₁ = b₁,

    a₂₁ × x₁ + a₂₂ × x₂ + … + a_2n × x_n + w₂ = b₂,

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

    a_m1 × x₁ + a_m2 × x₂ + …+ a_mn × x_n + w_m = b_m.

        где   х₁, …,  х_n  ³  0,      w₁, …, w_m  ³  0.

В целевую функцию  добавляем эти же переменные с большим отрицательным коэффициентом:

F = c₁ × x₁ + c₂ × x₂ + … + c_n × x_n – M × w₁ - … - M × w_m ® max

Исходное решение: w₁ = b₁,…, w_m = b_m,    х₁, …,  х_n = 0,     z  ®  - бесконечности.

Эта М-задача и исходная задача связаны между собой:

- если М-задача имеет  оптимальное решение в котором  все исходные переменные w_i = 0, то оно является решением и для исходной задачи;

- если М-задача имеет  оптимальное решение в котором  не все w_i = 0, то исходная задача не имеет решения;

- если М-задача  не имеет оптимального решения, то и исходная задача не имеет решения.

 

 

 

 

 

РАСЧЕТ  ОПТИМАЛЬНОЙ 

ПРОИЗВОДСТВЕННОЙ  МОЩНОСТИ

 

1. Понятие производственной  мощности.

2. Модели расчета оптимальной  производственной мощности.

 

1.  Понятие производственной мощности ПМ.

Производственная  мощность - способность закрепленных за предприятием средств труда (машины, оборудование, площади) к максимальному выпуску продукции за год в соответствии с установленной специализацией производства и режимом работы.

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

Производственная мощность (ПМ) зависит от:  

изменения технологии; 

изменения имеющегося оборудования; 

изменения структуры оборудования; изменения производительности;

изменения специализации.

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

1. В каких единицах будем считать (важно для текущего планирования динамики ПМ; выпуск продукции в натуральных единицах).

2. Как учитывать средства труда (учитывается все закрепленное за предприятием оборудование, даже не установленное. Оборудование группируется по цехам, участкам, группам. В группу могут входить станки, которые считаются взаимозаменяемыми).

3. Как рассчитать фонд времени работы оборудования. Действительный фонд времени – это все время, которое может работать данное оборудование, исключая праздники, выходные, время на капитальный ремонт:

(F_ном. – F_{план. рем.} = F_{действ.} ) × количество станков в группе = F _{действ. по группе}.

4. Какую номенклатуру учитывать при расчете, в каком состоянии учитывать виды продукции.

ПРИМЕР: 

В соответствии со специализацией предприятие выпускает 3 вида продукции: А, В, С. Для расчета ПМ все оборудование поделено на группы: 1, 2, 3. Плановое задание: 100, 200, 300 - его берут в расчете за основу.

Пусть F_i – действительный фонд времени i-той группы, Т_i - трудоемкость i-той группы в плановом задании, N_i - пропускная способность (во сколько раз больше мы можем прогнать задание):   N_i  = F_{действ i}  /  T_i .

N₁ =1,3;  N₂ = 1,5;  N₃=1,7.

 Выбирают ведущую группу оборудования, на которую приходится наибольшая продолжительность операции и число операций максимально. Пропускная способность этой группы будет являться ПМ предприятия. Допустим, ведущая – 2 группа и пропускная способность  N₂  берем за основу для производственной мощности, получаем, что ПМ в полтора раза больше, чем предусмотрено планом:      А – 150;  В – 300;   С – 400.

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

 

2. Модели расчета оптимальной производственной мощности.