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

При этом оптимальное решение (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 единиц.