Решение задач

Федеральное агентство по образованию

Государственное образовательное учреждение

Высшего профессионального образования 

«ГОСУДАРСТВЕННЫЙ   УНИВЕРСИТЕТ   УПРАВЛЕНИЯ» 
 
 

Институт  Национальной и Мировой  Экономики

Кафедра прикладной математики 
 
 
 
 
 
 
 

КУРСОВАЯ  РАБОТА

по учебной  дисциплине «Прикладная математика» 
 
 
 
 
 
 

Вариант №    9 

Выполнила:   Гаркуша П.А.

Студент ИФМ МО  

Курс  2  

Группа 2    
 
 

Руководитель  курсовой работы: 

         _____________ 
 
 

Москва, 2007

 

Содержание 

 

1. Линейная  производственная  задача

  Предприятие выпускает 4 вида продукции, используя 3 вида ресурсов.

  Технологическая матрица производства (A), запас ресурсов (B), удельная прибыль предприятия от производства и реализации каждого вида продукции (C) известны. 

       

  Требуется составить такой план производства продукции X=(x₁,x₂,x₃,x₄), реализация которого обеспечивает предприятие наибольшей прибылью.

  При производстве x₁ – единиц продукции Первого вида, x₂ – единиц продукции Второго вида, x₃ – единиц продукции Третьего вида, x₄ – единиц продукции Четвёртого вида предприятие затрачивает 3x₁+2x₂+6x₃+0x₄ единиц ресурсов Первого вида.

  Очевидно, что оно не должно превышать имеющийся  запас ресурса Первого вида, а именно 150.

  Составив  аналогичные ограничения для  ресурсов Второго и Третьего видов, получаем систему неравенств: 

            (1) 

  Z=60x₁+12x₂+44x₃+17x₄

  В качестве критерия эффективности правомерно принять принцип максимального  результата, поэтому математическая постановка задачи выглядит следующим образом: найти вектор X, обеспечивающий максимум линейной форме Z=60x₁+12x₂+44x₃+17x₄ при ограничивающих неравенствах (1) на его компоненты.

  Данная  задача является задачей линейного  программирования. Для её решения  симплексным методом проведём систему ограничений к предпочтительному виду за счёт введения в левую часть каждого ограничения по одной дополнительной неотрицательной неизвестной x₅, x₆, x₇.

  Переменные  x₅, x₆, x₇ по экономическому смыслу будут представлять собой остаток ресурсов Первого, Второго и Третьего видов соответственно.

  

  Выразим функцию Z таким образом для подстановки в таблицу:

  0-Z=-60x₁-12x₂-44x₃-17x₄ 
 
 
 
 
 
 
 
 
 
 
 

Решим систему симплексным методом: 

  

Ć Б Н X1 X2 X3 X4 X5 X6 X7 α Пояснения 0 х5 180 4 2 4 1 1 0 0 45 min(Dj<0)= -60 min(α)=40, x1 в базис, x6 из базиса 0 х6 160 4 0 2 2 0 1 0 40 0 х7 109 2 4 3 0 0 0 1 109/2   Z 0 – Z -60 -12 -44 -17 0 0 0   0 х5 20 0 2 2 -1 1 -1 0 10 min(Dj<0)= -14 min(α)=10, x3 в базис, x5 из базиса 60 х1 40 1 0 1/2 1/2 0 1/4 0 80 0 х7 29 0 4 2 -1 0 -1/2 1 29/2   Z 2400 – Z 0 -12 -14 13 0 15 0   44 х3 10 0 1 1 -1/2 1/2 -1/2 0   решения оптимальны 60 х1 35 1 -1/2 0 3/4 -1/4 1/2 0   0 х7 9 0 2 0 0 -1 1/2 1     Z 2540 – Z 0 2 0 6 7 8 0

 
 
 

  Оптимальная производственная программа: x₁=35, x₂=0, x₃=10, x₄=0.

  Остатки ресурсов: первого вида –x₅=0, второго вида –x₆=0, третьего вида – x₇=9.

  Узкими  местами производства, т.е. ресурсами, использующимися полностью, являются 1-й и 2-й ресурсы, x₅=0 и x₆=0 соответственно. 

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

  z = 2540 - 2х₂ - 6х₄ - 7х₅ - 8х₆                (2)

  то  становится совершенно очевидным (в силу того, что все x_j³0), что прибыль будет наибольшей тогда, когда x₂=0, x₄=0, x₅=0, x₆=0

  Это означает, что производственная программа (2) является наилучшей и обеспечивает предприятию наибольшую прибыль z_max = 2540 

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

  

  Для того, чтобы убедиться в правильности полученного решения, следует проверить  отношение Н = Q^-1 * В:

    
 

  Воспользуемся тем, что в оптимальной производственной программе х₂=0, х₄=0. Предположим, что продукции Второго и Четвёртого видов мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

  F(x₁,x₃)=60x₁+44x₃→max

    

   - направления наибольшего роста  целевой функции F. 
 

  

  В точке А достигается максимальное значение функции F. Найдём её координаты:

  

  F(22;14)=F_max=60*35+44*10=2540 

 

  2. Двойственная задача

  Некое предприятие, использующее те же ресурсы  что и предприятие из предыдущей задачи, желает приобрести все эти  ресурсы. Оно желает приобрести их по ценам y₁, y₂ и y₃ соответственно за единицу каждого из трёх ресурсов. Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции (A), количество ресурсов на производстве (B) и прибыль от единицы каждой продукции (C):

       

  Для производства единицы продукции  первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы третьего. В ценах у₁, у₂, у₃ наши затраты составят 4у₁ + 4у₂ + 2у₃, т.е. столько заплатит предприятие за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 60. Следовательно, мы можем согласиться с предложением предприятия «КПО» только в том случае, если он заплатит не меньше 60 :

  4у₁ + 4у₂ + 2у₃ ³ 60.

  Соответственные условия должны выполняться и для продукции других видов, т.е.

  2у₁ + 0у₂ + 4у₃ ³ 12,

  4у₁ + 2у₂ + 3у₃ ³ 44,

  1у₁ + 2у₂ + 0у₃ ³ 17.

  Но  при продаже требуется учитывать  и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие  желает закупить весь объём имеющихся ресурсов, то его затраты при ценах y₁, y₂ и y₃ составят , где коэффициенты при y₁, y₂ и y₃ - количество имеющихся ресурсов. Таким образом:

   → min

  Кроме того, так как цены не могут быть отрицательными, то .

  Решение полученной задачи легко найти с  помощью второй основной теоремы  двойственности, согласно которой для  оптимальных решений х(х₁,х₂,х₃,x₄) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий: 

   x ₁ (4y₁ + 4y₂ + 2y₃ - 60) = 0  y₁ (4x₁ + 2x₂ + 4x₃ + 1x₄ - 180) = 0

  x ₂ (2y₁ +       + 4y₃ - 12) = 0  y₂ (4x₁ +      + 2x₃ + 2x₄ - 160) = 0

  x ₃ (4y₁ + 2y₂  + 3y₃  - 44) = 0  y₃ (2x₁ + 4x₂ + 3x₃         - 109) = 0         .

  x ₄ (1y₁ + 2y₂            - 17) = 0

   Ранее (см. Задачу 1) было найдено, что  в решении исходной  задачи х₁>0 и х₃>0. Поэтому

  4y₁ + 4y₂ + 2y₃ - 60 = 0

  4y₁ + 2y₂  +3y₃  - 44 = 0

   Учитывая, что 3-ой ресурс был избыточным, то, согласно теореме двойственности, его двойственная оценка , получим систему:

  4y₁ + 4y₂ - 60 = 0

  4y₁ + 2y₂ - 44 = 0          откуда следует у₁ = 7, у₂ = 8. 

  Таким образом, получили двойственные оценки ресурсов: у₁ = 7, у₂ = 8, у₃ = 0

  причем  общая оценка всех ресурсов равна  180*7+160*8+109*0=2540

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

3. Задача о «расшивке узких мест производства»

  При выполнении оптимальной производственной программ Первый и Второй  ресурсы используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. Пусть T = (t₁, t₂, t₃) – вектор дополнительных объёмов ресурсов.

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

  Так как мы используем найденные оценки ресурсов, то должно выполняться условие:

  H + Q^-1T ³ 0

  Задача  состоит в том, чтобы найти вектор Т(t₁; t_2; 0), максимизирующий суммарный прирост прибыли W = 6t₁ + 3t₂ при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

  Обращённый  базис Q, соответствующий оптимальной производственной программе, содержатся в последней симплексной таблице в первой, второй, третьей строках восьмого, девятого и десятого столбцов:

  

Подставив соответствующие значения, получим  требуемую математическую модель:

  

предполагая, что дополнительно  можно надеяться получить не более 1/3 первоначального объёма ресурса каждого вида, то есть:

    
 
 
 
 

Перепишем неравенства в другом виде и получим: