Расчётно-графическое задание

Отрицательных  оценок  в  оценочной  строке  нет;  решение оптимально. Оптимальный опорный план:

 

Х_опт=(33,06; 2,2; 0; 1,173; 0; 0; 0; 0; 0)^Т 

F_max=4696,05 руб. 

             Для  получения  максимальной  прибыли  4696,05 руб.  необходимо  выпустить продукции вида Р1  33,06 м ткани,  Р2 2,2 м и Р4 1,173 м.

             Продукция  видов  Р₃ является   убыточным; его  производство  является  нерентабельным.

составим  двойственную задачу.

- теневая цена ресурса   I

- теневая цена ресурса II

- теневая цена ресурса Ш

- теневая цена ресурса IV

  - теневая цена ресурса V

→min

   

≥

Т.к. в  прямой задаче все неравенства в  системе сильных ограничений вида “≤”, найдем решение двойственной задачи по результатам решения прямой задачи.

=4696,05 руб.

y₁=0

y₂=0

y₃=10,22

y₄=2,99

y₅=5,5

Дефицитным  являются ресурсы III, IV и V.

Недефицитными являются ресурсы I, II.

Недефицитные  ресурсы недоиспользуются:

I ресурс на 230,7 кг;

II  ресурс на 1057,07 кг

    При увеличении запаса III ресурса на 1 ед. (204 кг) можно получить увеличение прибыли на 10,22 руб. она составит F=4706,27 руб. При этом план выпуска продукции 4 надо увеличить на 0,065 т.е. x₄=1,238, продукции 1 надо увеличить на -0,1 т.е. x₁=2,1, продукции 2 надо увеличить на 0,038 т.е. x₂=33,098. В этом случае недефицитные ресурсы будут недоиспользоваться:

1 ресурс на 0,89; его недоиспользование составит 231,69 кг;

2 ресурс на 0,64; его недоиспользование составит 1057,71 кг

    Покажем допустимые пределы изменения запасов  ресурсов.

                         

Составим матрицу  Р 

       

и вектор столбец 

   

Найдем  матрицу P  

 

Р^-1(b+∆b)= = 

 

    Покажем допустимые пределы изменения цен  на выпускаемые виды продукции.

    p^-1(c+∆c)  

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

     Приводим задачу к каноническому виду

     F*= - 500y₁-1402y₂-203y₃-600y₄-150y₅+0y₆+0y₇+0y₈+0y₉→max

     7y₁+9y₂+5y₃+17y₄+4y₅-y₆=124

     6y₁+13y₂+7y₃+5y₄+7y₅-y₇=125

     5y₁+17y₂+15y₃+24y₄+23y₅-y₈=195

     21y₁+16y₂+19y₃+23y₄+2y₅-y₉=274

       i=  

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

     G=0y₁+0y₂+0y₃+0y₄+0y₅+0y₆+0y₇+0y₈+0y₉-y₁₀-y₁₁-y₁₂-y₁₃→min

     7y₁+9y₂+5y₃+17y₄+4y₅-y₆+y₁₀=124

     6y₁+13y₂+7y₃+5y₄+7y₅-y₇+y₁₁=125

     5y₁+17y₂+15y₃+24y₄+9y₅-y₈+y₁₂=195

     21y₁+16y₂+19y₃+23y₄+2y₅-y₉+y₁₃=274

      

        i=  

     

Заключительная  симплекс-таблиц 

     Составим  матрицу P и вектор-столбец  

   P = ; 

    =  

   Найдём  матрицу   

=  

∆c)= * =

      Покажем целесообразность введения в план производства выпуск ткани с разновидностью рисунка  Р5:

     ∆p₅=6*0+2*0+1*10,22+4*2,99+4*5,5-5000=-4955,82

     Т.к. ∆р₅<0, то есть смысл ввести в план производства выпуск ткани с разновидностью рисунка р₅.

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

     Дефицитным является краситель А₃, А₄ и А₅. Значит Db₃=10, Db₄=10 и Db₅=10. Остальные Db₁=Db₂ =0, тогда

     Увеличение  дефицитных красителей не приводит к  изменению плана производства тканей. 
 
 

     Задание №2

 

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

 

     F= 1523x₁₂ + 1523₂₁ + 863x₁₃ + 863x₃₁ + 1899x₁₄ + 1899x₄₁ + 1809x₁₅ + 1809x₅₁ + 1578x₁₆ + 1578x₆₁ + 2329x₃₂ + 2329x₂₃ + 1622x₂₄ +1622x₄₂ + 3275x₂₅ + 3275x₅₂ + 3044x₂₆ + 3044x₆₂ + 1801x₃₄ + 1801x₄₃ + 1208x₃₅ + 1208x₅₃ + 977x₃₆ + 977x₆₃ + 2023x₄₅ + 2023x₅₄ + 1792x₄₆ + 1792x₆₄ + 247x₅₆ + 247x₆₅ min 

     x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ = 1

     x₂₁ + x₂₃ + x₂₄ + x₂₅ + x₂₆ = 1

     x₃₁ + x₃₂ + x₃₄ + x₃₅ + x₃₆ = 1

     x₄₁ + x₄₂ + x₄₃ + x₄₅ + x₄₆ = 1

     x₅₁ + x₅₂ + x₅₃ + x₅₄ + x₅₆ = 1

     x₆₁ + x₆₂ + x₆₃ + x₆₄ + x₆₅ = 1 

     x₂₁ + x₃₁ + x₄₁ + x₅₁ + x₆₁ = 1

     x₁₂ + x₃₂ + x₄₂ + x₅₂ + x₆₂ = 1

     x₁₃ + x₂₃ + x₄₃ + x₅₃ + x₆₃ = 1

     x₁₄ + x₂₄ + x₃₄ + x₅₄ + x₆₄ = 1

     x₁₅ + x₂₅ + x₃₅ + x₄₅ + x₆₅ = 1

     x₁₆ + x₂₆ + x₃₆ + x₄₆ + x₅₆ = 1

Решение задачи методом ветвей и границ.

  Преобразуем  матрицу s 

 
 

 

Определяем сумму приводимых элементов

     h¹=863+1523+863+1622+247+247+99=5464

Определяем претендентов для ветвления в множестве Y

Претендентами на ветвление могут быть S₁₃, S₂₁, S₂₄, S₃₁, S₄₂, S₅₆, S₆₅

Q₁₃ = 660+179=839;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₄₂ =660+170=830;

Q₅₆ = 170+961=1131;

Q₆₅ = 345+730=1075

Максимальную оценку имеет маршрут: Q42=830

w = h¹+Q42= 5464 + 830 = 6294

Преобразуем матрицу:

Определяем  h²= 0;

Оценка  по {4,2}=5464      

Определяем пару для ветвления

Q₁₃ = 715+730=1445;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₅₆ = 114+961=1075;

Q₆₅ = 345+730=1075

Подходящую  оценку имеет маршрут: Q21=0

w = w(4;2)+ Q21= 6294

Преобразуем матрицу:

Определяем  h³= 114+725=839;

Оценка  по {2,1}=5464+839=6303

Определяем пару для ветвления

Q₁₃ = 212+730=942;

Q₃₄ = 212;

Q₃₆ = 0;

Q₅₆ = 952;

Q₆₅ = 231+721=952

Подходящую  оценку имеет маршрут: Q13=942

w = w(2;1)+ Q13= 6294+942=7236

Преобразуем матрицу:

 

Определяем  h⁴= 0;