Контрольная работа по "Экономике". 84

  Задача 1 

    Условие задачи

    Цех предприятия выпускает 2 вида изделий  А и В, для изготовление которых требуются ресурсы трёх видов: R1, R2, R3. Данные о наличии ресурсов, наличии ресурсов каждого вида, необходимое для изготовления тысячи изделий (нормы расходов), а также прибыль от реализации тысячи изделий каждого вида, приведенные в табл 1. 

                                               Таблица 1

    Определить  объем выпуска изделий А и В максимизирующие прибыль предприятия. 

    Построение  математической модели.

    Пусть за плановый период выпускаются Х1 (тыс.шт.) изделий А и Х2  (тыс.шт.) изделий В. По условию задачи прибыль, получаемая от реализации 1000 шт. изделия А, составляет 6 у.е., а 1000 шт. изделий В – 7 у.е.

    Тогда прибыль, получаемая от реализации Х1 изделий А и Х2 изделий В, выпущенных за плановый период, может быть записан в виде выражения             Z=6Х1+7Х2.

    Отрицательные значения Х1 и Х2 не имеют смысла, т.е.    Х1>=0, Х2 >=0.

    Величины  Х1  и Х2 нельзя выбирать произвольно, т.к. на них накладываются ограничения, определяемые наличием ресурсов R1, R2, R3. Как видно из табл. 1, Для изготовления 1000 шт. изделия А, требуется 4 (ед) ресурса R1, а для изготовления 1000 шт. изделия В требуется 10 (ед) ресурса R1. Следовательно, расход ресурса R1 для выпуска Х1 (тыс. шт.) изделий А составит 4Х1  (ед) , а для выпуска Х2 (тыс. шт.) изделий В - 10Х2 (ед). Таким образом, для планового выпуска изделий А и В потребуется 4Х1 + 10Х2 (ед) ресурса R1. В связи с тем, что запас ресурса R1 составляет 400 ед., ограничение по нему будет иметь вид:

    4Х₁ + 10Х₂ <=400.

    Аналогично  рассуждая, можно составить ограничения для ресурсов R2 и R3:

    R2:  6Х₁ +9Х₂ <=540

    R3: 8Х₁ +6Х₂ <=480 

    Получили  математическую модель задачи.

    Имеем целевую функцию линейной формы

     Z=6Х₁+7Х₂.              max,    (1)

    Систему линейных ограничений:

    4Х₁ + 10Х₂ <=400

             6Х₁ + 9Х₂ <=540   (2)

    8Х₁ + 6Х₂ <=480 

    и граничные условия: Х₁ >=0, X₂ >=0       (3) 

    Задача  формулируется следующим образом:

    Найти такие неотрицательные Х₁ и Х₂, которые будут удовлетворять системе ограничений (2) и обращать в максимум целевую функцию (1)

    Целевая функция и ограничения имеют линейную форму, поэтому данная задача относится к  классу ЗЛП и для решения можно использовать симплекс-метод. Т.к. задача имеет только две переменные, она может быть решена графическим методом.

    Графический метод решения  задачи

    Область допустимых решений определяется граничными условиями (3) и системой неравенств (2). Граничные условия Х₁>=0, X₂>=0 указывают на то, что область допустимых решений находится в I-ом квадранте.

    Построим  систему неравенств (2). Каждое неравенство  геометрически определяет полуплоскость с граничными прямыми

    4Х₁ + 10Х₂ =400

               6Х₁ + 9Х₂ =540       (4)

    8Х₁ + 6Х₂ =480

    Построим  эти прямые. Каждая из них делит  плоскость на две полуплоскости. Решение следует искать в той  полуплоскости, все точки которой  удовлетворяют неравенству. Чтобы определить эту полуплоскость, возьмем какую-нибудь точку на плоскости, например точку с координатами (0;0). Если приравнять к нулю значения Х₁ и Х₂ в левой части соответствующих неравенств, получим соотношение 0<= const,  значит точка с координатами (0;0) входит в полуплоскость, соответствующую рассматриваемому неравенству. Во все полуплоскости, соответствующие ограничениям (2) входит начало координат ( при Х₁=Х₂=0, 4Х₁ + 10Х₂ <400,  6Х₁ + 9Х₂ <540, 8Х₁ + 6Х₂ <480). Т.к. система (2) совместна, то полуплоскости, пересекаясь, образуют общую для всех полуплоскостей часть, которая представляет собой многогранник. Таким образом, определили область, удовлетворяющую всем ограничениям и граничным условиям, т.е.область допустимых решений (многогранник решений). Известно, что решение должно находиться на границе этой области, и, если решение единственное, в одной из его вершин. Точка с координатами (Х₁;Х₂), в которой значение целевой функции достигает максимума, должна находится в одной из вершин многоугольника. 

    Проведем   линию уровня ЦФ. Проходящую через  начало координат: Z=6Х₁+7Х₂=0 
 

    Значение  Z возрастает в направлении нормального вектора n= {6;7}. Будем передвигать прямую параллельно самой себе в направлении вектора n до тех пор,  пока многоугольник решений не будет находится с одной стороны от неё, и прямая не будет иметь с ним, по крайней мере, одну общую точку. Этой точкой будет точка С с координатами Х₁ =42,8  Х₂=22,88, в которых ЦФ Z принимает максимальное значение. Подставив значения Х₁ = 42,8  Х₂=22,88 в целевую функцию Z =6Х₁ +7Х₂, получим её максимальное значение Z= 6 * 42,8 + 7 * 22,88 = 417

    ИСПОЛЬЗОВАНИЕ СИМПЛЕКС-МЕТОДА ДЛЯ  РЕШЕНИЯ ЗАДАЧИ

Определение базисного (допустимого) решения

    Перейдем  от неравенств (2) к равенствам (5), введя дополнительные неотрицательные переменные Х₃, Х₄ , Х₅. Тогда система ограничений будет иметь вид:

    4Х₁ + 10Х₂  + Х ₃ =400

           6Х₁ + 9Х₂  + Х₄ =540    (5)

                       8Х₁ + 6Х₂ + Х₅ =480,

где    Х₁,Х₂, Х₃, Х₄,Х₅>=0.

 Дополнительные  переменные войдут в целевую функцию    Z    с нулевыми коэффициентами:

(6)

      Z =6Х₁ + 7Х₂ + 0Х₃ + 0Х₄ + 0Х₅

      Перепишем систему (5) и (6) в виде:

Х₃ = 400-(4Х₁ +10Х₂) 
Х₄=540-(6Х₁ + 9Х₂) (7)

Х₅ = 480 –(8Х₁ + 6Х₂)

Z = 0 - (- 6Х₁ - 7Х₂ - 0Х₃ - 0Х₄ - 0Х₅)

    Переменные  Х₃, Х₄, Х₅ - базисные, X₁, Х₂ - небазисные (свободные). Положив Х₁= Х₂= 0, получим значения базисных неизвестных:      Х₃=400, Х4= 540,Х₅ = 480.                                                                          Таким образом, базисное решение системы (О, О, 400, 540, 400). Для этих значений переменных целевая функция примет значение    Z = 0.

Определение оптимального решения.           Систему (7) представим в виде симплекс-таблицы С-Т1 (табл. 3). 

Таблица 3

    После заполнения (С-Т1) начнем подготовку к  составлению второй симплекс-таблицы (С-Т2). Для этого выполним следующие действия.

1. Выбираем из Z максимальное по модулю  число.
2. Делим столбец свободных членов на столбец с максимальным значением.

400/10=40,   540/9=60,    480/6=80,  и выбираем наименьшее (40).

3.  Элементы  этой строки разделим на разрешающий  элемент. Получим 1-ю строчку  С-Т2.

4.  Элементы  полученной 1-й строки С-Т 2 умножаем  на  коэффициент  первого элемента  и вычтем из соответствующего  элемента первой строки С-Т1. Получили  вторую строку С-Т 2.

Таким же образом, получим четвертую строку С-Т2 - строку целевой функции (табл. 4).

Таблица 4

5. Определим, является ли полученное решение допустимым.

В   столбце   свободных   членов   все   величины   неотрицательные, следовательно, полученное решение является допустимым.

6. Определим, является ли полученное решение оптимальным. 
Целевая функция имеет максимальное значение в том случае, когда все элементы в строке целевой функции будут положительными. В нашем   случае   не    все   элементы   в   строке   целевой   функции  положительны, поэтому оптимальный план не найден.  Продолжим решение. Перейдем к  построению новой симплекс-таблицы  С-ТЗ (табл. 5).

Таблица 5

    Определим, является ли полученное решение допустимым.

    В   столбце   свободных   членов   все   величины   неотрицательные, следовательно, полученное решение является допустимым.           Определим, является ли полученное решение оптимальным. 
Все   элементы   в   строке   целевой   функции   положительны,   поэтому оптимальный план найден.     Таким образом, оптимальным будет решение:    X₁ = 42,8;   Х₂ =22,88;    целевая функция   Z  =   417.   Результаты, полученные при решении задачи графическим методом и симплекс-методом, совпадают.

     Анализ оптимального решения.

    Для исходной задачи линейного программирования:

    4Х₁ + 10Х₂  + Х ₃ <=400

     6Х₁ +9Х₂  + Х₄ <=540   

            8Х₁ + 6Х₂ + Х₅ <=480

    X₁ >= О, Х₂ >= О,                                   составим двойственную задачу.

4Y1 + 6Y2 + 8Y3 >= 6                          10Y1 + 9Y2 +6Y3 >= 7

Zd = 400Y₁ +460Y₂ + 400Y₃                min      Y₂>=0, Y₁>=0.

    Важным  свойством двойственной задачи является:         max Z = min Zd.                              Таблица 6

Y^*= (0,35; 0 ;0,577 ; 0 ; 0 )                        g (Y^*) = 400*0,35 + 480*0,577 = 417 у.е.                        РЕШЕНИЕ ЗАДАЧИ В EXCEL

    Для решения задачи составим электронную таблицу, отражающую ее математическую модель (рис. 2, 3). На рис. 2 показана электронная таблица в режиме отображения вычислений (исходное состояние), на рис. 3 - в режиме отображения формул. На рисунках введены сокращения: «нижн.гран.» - нижняя граница значений переменных, ЦФ - целевая функция.

Работа  в диалоговом окне «Поиск решения»

    Для подготовки к решению задачи оптимизации  выполним команду: Сервис - Поиск решения. Па экране появится диалоговое окно Поиск решения  Выполним следующие действия:

1.    В поле Установить целевую ячейку введем адрес $G$6.

2. Для  выбора направления изменения  целевой функции установим переключатель в положение Максимальному значению.

3.   В поле Изменяя ячейки введем адрес блока ячеек $В$3: $F$3.

4.   Введем граничные условия и ограничения: щелкнем по кнопке Добавить.   На   экране   появится диалоговое   окно   Добавление ограничения. Для ввода граничных условий X1 - Х5 > 0 в поле Ссылка   на   ячейку  введем  левую часть отношения (B3:F3),  в следующее поле - его знак (>) и в последнее поле - правую часть 
(B4:F4); щелкнем по клавише Добавить. На экране опять появится диалоговое окно Добавление ограничения. Введем ограничения по ресурсам    (G9:G11  < I9:I11) аналогичным образом и щелкнем по кнопке ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями.

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

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

1. Щелкнем  по кнопке Параметры. Появится   диалоговое окно Параметры поиска решения.

2. Установим  Максимальное время решения задачи (оставим предлагаемое по умолчанию - 100 с), Предельное число итераций (оставим предлагаемое по умолчанию - 100).

3. Установим флажок Линейная модель.
4. Нажмем ОК. Появится диалоговое окно Поиск решения.
5. Щелкнем по кнопке Выполнить. Появится      диалоговое окно. Результаты поиска решения  Решение найдено.

    Если  закроем   это  окно,  нажав  ОК, то увидим  оптимальное решение задачи. На экране появится исходная таблица, где в блоке ячеек В3:F3  находятся результаты решения – значения переменных Х1 – Х5.

Отчет по результатам

    Щелкнем мышью по ярлычку Отчет по результатам. На экране появится лист данного отчета.

    В верхней таблице отчета указан номер  ячейки - $G$6 (целевой ячейки), в которой находится значение целевой функции, исходное, равное 0, и результирующее - максимальное значение целевой функции — 800, полученное в результате решения задачи оптимизации.

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

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

    Ниже  приводятся номера ячеек, в которых  располагаются искомые переменные - основные и вспомогательные, их исходные и результирующие значения, при которых целевая функция достигает максимального значения, и их статус.

Отчет по устойчивости

Щелкнем мышью  по ярлычку Отчет по устойчивости. На экране появится лист данного отчета.

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

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

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

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

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

Отчет по пределам

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

     Анализ влияния изменения b_i (запасов ресурсов) 

B₁

22.8+8/56      b₁>=0                  8/56      b₁>= -22.8               b₁>= -159.6

         77.3-0.64      b₁>=0                  0.64     b₁<=77.3             b₁<= 120.78

        42.8-6/56      b₁>=0                    6/56      b₁<=42.8                b₁<=399

-160<=      b₁<=120

240<=b₁<=520

B₂

22.8+0    b₂>=0                                      

77.3+     b₂>=0                                     b₂>= -77.3

42.8+0    b₂>=0

b₂<=462.7

B₃

22.8-1/14       b₃>=0                           1/14     b₃<=22.8                    b₃<=319.2

77.3-0.42       b₃>=0                            0.42      b₃<=77.3                     b₃<=184.04

42.8+10/56       b₃>=0                          10/56      b₃>= -42.8                b₃>= -239.68

-240<=b₃<=184 

    Анализ  влияния изменения Сj (прибыль) 

0.35+8/56       С₁>=0                         8/56      C₁>= -0.35                     C₁>= -2.45

0.577+10/56    C₁>=0                     10/56      C₁= -0.577                      C₁>= -3.2            

Пределы приращения:                 -3.2<=       С₁<=3.3

Пределы изменения                            2.8<=C₁<=9.3

C₂

0.35+8/56       C₂>=0                                  8/56      C₂>= - 0.35                       C₂>= -2.45

0.577-1/14     C₂>=0                                 1/14      C₂<=0.577                        C₂<=8

Пределы приращения     -2.45<=      C₂<=8                     Пределы изменения        4.55<=C₂<=15

Оптимальный план выпуска продукции не изменится, при изменении прибыли на ед. продукции  А в диапазоне от 2.8 до 9.3 у.е., и прибыли на ед. продукции В в диапазоне от 4.55 до 15 у.е.