ВАРИАНТ 7

   1. Макаронная фабрика производит два вида изделий А и В, используя три вида сырья: муку, яйца, соль. Общие запасы каждого вида сырья соответственно равны 3000, 252, 120 усл. ед. Норма расхода сырья

   на  единицу веса изделия А - 120; 3; 4 усл. ед.,

   на  единицу веса изделий В - 40; 12; 4 усл. ед.

   Составить план производства, обеспечивающий максимальную прибыль, если единица веса изделий  А дает прибыль 300 р., а В - 400 р.:

а) записать математическую модель;

б) решить задачу графическим методом;

в) решить задачу симплекс-методом;

   г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной. 

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

   X1 –изделие первого вида

   X2 –изделие второго вида

   Тогда компоненты производственного плана должны (X1;X2) должны удовлетворять следующим условиям ограничениям

   С другой стороны пара величин X1 и X2 может рассматриваться как некоторый вариант производственного плана.

   Нужно найти план, приносящий наибольший доход

   Пришли  к задаче линейного программирования

   Графическое решение задачи

В декартовой системе  координат находим  решение системы  неравенств.

Для этого строим прямые.

120x1+40x2=3000  по точкам  (0;75)  (25;0)

3x1+12x2=252  по точкам  (0;84)  (21;0)

4x1+4x2=120  по точкам  (0;30)  (30;0)

OABCD многоугольник решений

Вектор  (30; 40) вектор целевой функции.

Проведём через  любую точку.  например (0;10) прямую P’, перпендикулярно вектору  .

Перемещаем прямую Р’ параллельно самой себе по направлению вектора , пока   она не займёт относительно области OABCD крайнего верхнего положения.

Это произойдёт, когда она пройдёт через точку  B(19.64;16.09).

Оптимальное решение  определяется координатами точки B(19.64;16.09) точка пересечения прямых  3x1+12x2=252    4x1+4x2=120

Zmax=300*19.6364+400*16.09=12327.27 
 
 

Решить  задачу симплекс-методом

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

120x1+40x2+x3=3000 

3x1+12x2+x4=252 

4x1+4x2+x5=120   

эти дополнительные переменные  по экономическому смыслу

означают неиспользуемое сырьё при данном плане производства

Преобразованную систему уравнений запишем в  векторной 

форме:

          x1*P1+x2*P2+x3*P3+x4*P4+x5*P5=P0, где        

P1= P2=   P3=   P4=   P5=    P0=  

Cимплекс-таблица 

Определяем  вектор подлежащий, который нужно ввести в базис, очевидно – это P2 (ему соответствует большее отрицательное значение).

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

Вектор, который  необходимо исключить P4. 

Определяем наименьшее, среди отношений  Bi/Pi2, разрешающий элемент -12.  

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

Из первой строки вычитаем вторую строку, умноженную на  (40/12)

Из третьей  строки вычитаем вторую строку, умноженную на  (4/12)

Получим следующую  таблицу.

Определяем вектор подлежащий, который нужно ввести в базис, очевидно – это P1 (ему соответствует большее отрицательное значение).

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

Вектор, который  необходимо исключить P5. 

Определяем наименьшее, среди отношений  Bi/Pi1, разрешающий элемент -3.

Преобразуем исходную симплекс-таблицу относительно разрешающего элемента.

Из первой строки вычитаем третью строку, умноженную на  (110/3)

Из второй строки вычитаем третью строку, умноженную на  (0,25/3)

Получим следующую  таблицу.

   Все ΔZi>0,  поэтому, полученное базисное решение

   X1=12 X2=18 X3=840 является оптимальным, значение целевой функции для него равняется 10800 усл. единиц.     
 
 

                  Построение  двойственной задачи

                  Исходная задача (L):

Найти

При ограничениях. 

Двойственная  ей задача (L*), будет иметь вид: найти

при ограничениях

При этом оптимальное решение (X1;X2) задачи (L) и оптимальное решение (u1;u2;u3)

Задачи (L*) связаны соотношениями:

Которые называются отношениями двойственности, в линейном программировании,

 или  соотношениями  «дополняющей  нежесткости».

Решение задачи (L) известно x1= 12   x2= 18  Z(мах)=10800

Найдём  решение задачи (L*) не прибегая к симплекс-методу, используя соотношение двойственности.

Так как x1=12>0 то для оптимальных решений задачи (L*) первое ограничение должно выполняться как равенство:  120u1+3u2+4u3=300

Так как x2=18>0 то для оптимальных решений задачи (L*) первое ограничение должно выполняться как равенство:  40u1+12u2+4u3=400

Подставляем оптимальное решение x1=12 x2=18 в первое неравенство задачи (L), видим, что 120*12+40*18=2160<3000 т.е. оно выполняется строго. Значит для оптимальных решений задачи (L*) u1=0

Подставляем оптимальное решение x1=12 x2=18 во второе неравенство задачи (L), видим, что 3*12+12*18=252 сказать, что u2=0 нельзя.

Подставляем оптимальное решение x1=12 x2=18 в третье неравенство задачи (L), видим, что 4*12+4*18=120 сказать, что u3=0 нельзя.

 Таким  образом, оптимальное решение  двойственной задачи (L*)  удовлетворяет системе уравнений

    Решая систему получаем 

Оптимальное значение задачи (L*) равно Zmin=3000*0+252*100/9+120*200/3=10800

Т.е  выполнено второе условие, связывающее  оптимальные решения задач (L) и (L*).

Zmin= Zmax=10800  
 

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

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

Решить транспортную задачу методом потенциалов. 

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

Алгоритм нахождения базисного плана перевозок методом Фогеля   

1. по каждой строке и каждому столбцу определяют разность между двумя наименьшими тарифами и записывают её в дополнительные к исходной таблице строки и столбцы.
2. из полученных разностей выбирают наибольшую и отмечают её (жирный шрифт).
3. в стоке или столбце, где имеется наибольшая разность, выбирается клетка с наименьшим тарифом C_IJ и загружается наибольшей возможной перевозкой    X_ij=min(a_i,b_j)
4. производится перерасчёт запасов и заявок на груз, клетки соответствующие тарифам, по которым уже невозможно что-либо перевезти, прочёркиваются, что соответствует нулевым значениям матрицы перевозок.
5. пункты 1-4 выполняются до тех пор, пока вся таблица не будет заполнена элементами матрицы перевозок

Стоимость плана  S=2*16+1*34+5*22+7*16+3*14+4*6= 354 единицы

Определим, является ли этот план оптимальным

Метод потенциалов 

Сосчитаем потенциалы  по формуле 

Формуле  vj -ui=Cij  i=1,2,3  j=1,2,3,4

В расчёте участвуют  только занятые клетки

Предполагаем  u1=0  и постепенно вычисляем остальные числа

Клетка А1В1:  v1 -u1=C11   v1 -0=2    v1 =2   

Клетка А1В2:  v2 –u1=C12  v2 -0=1     v2 =1   

Клетка А3В1:  v1 –u3=C31  2-u3=3      u3=-5   

Клетка А3В4:  v4 –u3=C34  v4 –(–5)=4     v4=-1  

Клетка А2В4:  v4 –u2=C24  -1-u2=7    u2 =-8   

Клетка А2В3:  v3 –u2=C33  v3 –(-8)=5      v3 =-3   

После того  как  все  потенциалы  найдены  для  каждой  из свободных  клеток  определяем  числа: aij=vj -ui -Cij

Клетка А1В3:  a13=v3 –u1 –C13   a13=-3-3-0 = -6   

Клетка А1В4:  a14=v4 –u1 –C14   a14=-1-6-0 = -7  

Клетка А2В1:  a21=v1 -u2–C21   a21=2-(-8)-10 =0   

Клетка А2В2:  a22=v2 -u2–C22   a22=1-(-8)-11 =-2   

Клетка А3В2:  a32=v2 -u3 –C32   a32=1-(-5)-4 =0

Клетка А3В3:  a33=v3 –u3 –C33   a33=-3-(-5)-2 =0    

Среди чисел  aij  нет положительных чисел .

Значит план  оптимальный.   

S=2*16+1*34+5*22+7*16+3*14+4*6= 354 единиц.