Контрольная работа по "Прикладной математике"

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

 

Исходные данные:

 

59	27	20	35
1	3	2	2	102
3	2	0	3	204
4	2	3	1	188

 

Задание:

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

        a₁₁    a₁₂    a₁₃    a₁₄                          b₁

A =  a₂₁    a₂₂    a₂₃    a₂₄   ,   B =   b₂    ,  C = ( c₁         c₂     c₃     c₄ )

        a₃₁    a₃₂    a₃₃    a₃₄                          b₃

 

которые компактно записаны в виде

  c₁         c₂     c₃     c₄

a₁₁    a₁₂    a₁₃    a₁₄       b₁

a₂₁    a₂₂    a₂₃    a₂₄       b₂

a₃₁    a₃₂    a₃₃    a₃₄       b₃

 

Преобразовать исходную задачу к виду основной задачи линейного  программирования.

2. Решить ее симплекс методом, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и указать «узкие места» производства.

 

Решение:

1.Из исходных данных  получаем: матрица А удельных  затрат ресурсов, вектор В объемов  ресурсов и вектор С удельной  прибыли имеют вид

           1   3   2   2             102

А =  3   2  0   3   ;   В =  204   ;   С = ( 59   27   20   35 ).

        4   2   3   1               188

 

Математическая же модель задачи: найти производственную программу 

(x₁, x₂ ,x₃,,x₄), максимизирующую прибыль

                Z(x₁, x₂ ,x₃,,x₄) = 59 x₁ + 27 x₂ + 20x₃ +35 x₄ → max ,

при ограничениях по ресурсам    

1x₁ + 3x₂ + 2x₃ + 2x₄  ≤ 102

3x₁ + 2x₂ + 0x₃ + 3x₄ ≤ 204

4x₁ + 2x₂ + 3x₃ + 1x₄  ≤ 188

где по смыслу задачи x₁, x₂, x₃, x₄ ≥ 0.

Получили задачу линейного  программирования. Чтобы решить ее, заменяем неравенства системы уравнениями при помощи дополнительных неотрицательных неизвестных x₅, x₆ , x₇, называемых балансовыми, оптимальные значения которых имеют экономический смысл остатков ресурсов. Получается каноническая задача ЛП:

59 x₁ + 27 x₂ + 20x₃ +35 x₄ → max,

1x₁ + 3x₂ + 2x₃ + 2x₄  + x₅ = 102,

3x₁ + 2x₂ + 0x₃ + 3x₄ + x₆ = 204,

4x₁ + 2x₂ + 3x₃ + 1x₄  + x₇ =188,

x₁,…, x₇ ≥ 0.

2.Будем решать эту  задачу симплексным методом.

 

 

			59	27	20	35	0	0	0
СБ	Б	Н	X1	X2	X3	X4	X5	X6	X7
0 0 0	X5    X6    X7	102 204 188	1    3    4	3    2    2	2    0    3	2    3    1	1    0    0	0    1    0	0    0    1
	Z	0	-59	-27	-20	-35	0	0	0
0 0 59	X5    X6    X1	55   63   47	0    0    1	5/2   1/2   1/2	5/4 -9/4   3/4	7/4   9/4   1/4	1    0    0	0    1    0	-1/4 -3/4   1/4
	Z	2773	0	5/2	97/4	-81/4	0	0	59/4
0 35 59	X5    X4    X1	6   28   40	0    0    1	19/9   2/9   4/9	3   -1    1	0    1    0	1    0    0	-7/9   4/9 -1/9	1/3 -1/3   1/3
	Z	3340	0	7	4	0	0	9	8

 

 

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

                b_i                      102     204     188        188

  min  —―̶̶̶̶̶̶  ̶ ̶̶̶ ̶ = min    ―̶̶̶̶̶̶  ̶ ̶̶̶ ; ―̶̶̶̶̶̶  ̶ ̶̶̶ ; ―̶̶̶̶̶̶  ̶ ̶̶̶        = ―̶̶̶̶̶̶ ̶ ̶̶̶ .

            a_i1>0                   1         3         4            4

 

Оно соответствует третьему уравнению. Это означает, что за решающее уравнение в системе принимается  третье. Коэффициент а₃₁ = 4 будет разрешающим. Применив формулы исключения, переходим к новому предпочитаемому виду системы с соответствующим базисным допустимым решением. При этом неизвестная х₁ становится базисной. Придется ее исключить из целевой функции, чтобы иметь возможность исследовать новое базисное допустимое решение на оптимальность. Получаем первую симплексную таблицу. Аналогично поступаем и далее, пока в последней строке третьей таблицы не осталось ни одного отрицательного оценочного коэффициента Δ _j , т.е. выполняется критерий оптимальности для максимизируемой функции цели.

Производная программа

х₁ = 40, х₂ = 0, х₃ = 0, х₄ = 28

является оптимальной  и обеспечивает предприятию наибольшую возможную прибыль Z_max = 3340. При этом второй и третий ресурсы будут использованы полностью х₆ = 0, х₇ = 0, а первый ресурс будет иметь остаток х₅ = 6, т.е. второй     и третий ресурсы образуют “узкие места производства”.

                             

 

 

 

 

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

 

Исходные данные:

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

          59 x₁ + 27 x₂ + 20x₃ +35 x₄ → max ,

1x₁ + 3x₂ + 2x₃ + 2x₄  ≤ 102,

3x₁ + 2x₂ + 0x₃ + 3x₄ ≤ 204,

4x₁ + 2x₂ + 3x₃ + 1x₄  ≤ 188,

                                 x_1-4  ≥ 0.

 

Задание:

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

 

Решение:

Необходимо найти оценку единицы каждого вида ресурса, т.е. необходимо найти вектор двойственных оценок (y₁, y₂, y₃), минимизирующий общую оценку ресурсов всех ресурсов

102y₁ + 204y₂ + 188y₃ → min,

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

1y₁ + 3y₂ + 4y₃ ≥59,

3y₁ + 2y₂ + 2y₃ ≥27,

2y₁ + 0y₂ + 3y₃ ≥20,

2y₁ + 3y₂  + 1y₃ ≥35,

причем оценки ресурсов не могут быть отрицательными y_1-3 ≥0.

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

  x_i  (  ∑ a_ij·y_i  –  c_j ) = 0                  y_i   ( b_i  – ∑ a_ij·x_j ) = 0

              ^{i                                                                                                   i}

      x₁ (1y₁ + 3y₂ + 4y₃ –59) = 0           y₁ (1x₁ + 3x₂ + 2x₃ + 2x₄ –102 ) = 0

x₂ (3y₁ + 2y₂ + 2y₃ –27) = 0           y₂ (3x₁ + 2x₂ + 0x₃ + 3x₄ –204 ) = 0

x₃ (2y₁ + 0y₂ + 3y₃ –20) = 0           y₃ (4x₁ + 2x₂ + 3x₃ + 1x₄ –188 ) = 0

x₄ (2y₁ + 3y₂  + 1y₃ –35) = 0      

В предыдущей задаче было найдено 

x₁ = 40, x₂ = 0, x₃ = 0, x₄ = 28, т.е. x₁ >0, x₄ >0. Поэтому

1y₁ + 3y₂ + 4y₃ –59 = 0,

2y₁ + 3y₂  + 1y₃ –35 = 0.

 

Если же учесть, что  первый ресурс был избыточным и, согласно той же теореме двойственности, его  двойственная оценка равна нулю y₁ = 0, то

 y₁ = 0                                       y₁ = 0                              y₁ = 0   

 y₁ + 3y₂ + 4y₃ –59 = 0            3y₂ + 4y₃ = 59                  y₂ = 9

2y₁ + 3y₂  +  y₃ –35 = 0             3y₂  +  y₃ =35                    y₃ = 8

Таким образом, получили двойственные оценки ресурсов

y₁ = 0, y₂ = 9, y₃ = 8, причем общая оценка всех ресурсов равна 3340.

   

Экономический смысл  двойственных оценок:

• двойственная оценка второго ресурса у₂=9 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 9 единиц;
• двойственная оценка третьего ресурса у₃=8 показывает, что добавление одной единицы третьего ресурса обеспечит прирост прибыли в 8 единиц.

 

 

 

 

 

 

 

 

 

 

 

                    

 

 

 

                                                Задача о “расшивке узких мест”.

 

Исходные данные:

из задачи 1.1. получили следующие данные

	X5    X4    X1	6   28   40	0    0    1	19/9   2/9   4/9	3   -1    1	0    1    0	1    0    0	-7/9   4/9 -1/9	1/3 -1/3   1/3
	Z	3340	0	7	4	0	0	9	8

 

Задание:

Решить задачу о “расшивке  узких мест”.

 

Решение:

При выполнении оптимальной  производственной программы второй и третий ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть Т(0, t₂, t₃) – вектор дополнительных объемов ресурсов. Так как используются найденные двойственные оценки, то должно выполняться следующее условие:

H + Q^-1T ≥ 0.

Задача состоит в  том, чтобы найти вектор , максимизирующий суммарный прирост прибыли:

W = 9 t₂ + 8 t₃

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры  производственной программы), предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

0                  102

t₂         ≤  1/3   204

   t₃                  188  ,

причем по смыслу задачи  t₂ ≥0, t₃ ≥ 0.

Следовательно, получаем

6              1   -7/9   1/3          0                 0

28   +      0    4/9  -1/3    •    t₂      ≥       0

40            0   -1/9   1/3         t₃           0    .

Перемножим матрицы  и получим следующую систему  неравенств:

-7/9t₂  + 1/3t₃  ≥ -6,                  -7t₂  + 3t₃  ≥ -54,         (I)        

4/9t₂    – 1/3t₃   ≥ -28,                  4t₂   – 3t₃   ≥ -252,      (II)

-1/9t₂  + 1/3t₃   ≥ -40,     Þ        - t₂   + 3t₃    ≥ -360;      (III)

  t₂ ≤ 204/3, t₃ ≤ 188/3,                t₂ ≤204/3, t₃ ≤ 188/3,

       t₂  ≥ 0, t₃  ≥ 0;                           t₂  ≥ 0, t₃  ≥ 0.

 

Решим данную задачу графически.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                   

                Программа “расшивки” имеет  вид

t₂  = 0, t₂  = 242/7 , t₃ = 188/3,

и прирост прибыли  составит maxW = 9∙242/7+ 8∙188/3 =17062/21 ≈ 812,48 в точке М(242/7,188/3)

 

                                                Транспортная задача.

   

Кондитерской фабрике  необходимо распределить между 4 (n) магазинами шоколадные конфеты из 3-х (m) фабрик-филиалов в количестве 45, 55, 70 единиц, которым необходимо соответственно 59, 27, 40, 35 единиц. Стоимости перевозок единицы продукта из пункта отправления в пункт назначения равна:

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