p align="left">c2,4+с3,5>c2.5+c3.4 (30+40>30+100) Количество единиц товара, перемещаемых по циклу: min (с2,4 ; с3,5)=15 В результате получится следующий план: |
| B1 | B2 | B3 | B4 | B5 | a | | A1 | | 45 | | 60 | | 40 | | 60 | | 95 | 90 | | | 15 | | 30 | | 45 | | | | | | | | A2 | | 35 | | 30 | | 55 | | 30 | | 40 | 50 | | | | | 15 | | | | 20 | | 15 | | | | A3 | | 50 | | 40 | | 35 | | 30 | | 100 | 30 | | | | | | | | | 30 | | | | | | b | 15 | 45 | 45 | 50 | 15 | 170 | | |
Больше циклов с «отрицательной ценой» нет, значит, это оптимальное решение. Проверим методом потенциалов: Примем б1=0, тогда вj = cij - бi (для заполненных клеток). Если решение верное, то во всех пустых клетках таблицы Дij = cij - (бi+ вj) ? 0 Очевидно, что Дij =0 для заполненных клеток. В результате получим следующую таблицу: |
| в1=45 | в2=60 | в3=40 | в4=60 | в5=70 | | | б1=0 | | 45 | | 60 | | 40 | | 60 | | 95 | 90 | | | 15 | | 30 | | 45 | | 0 | | + | | | | б2= -30 | | 35 | | 30 | | 55 | | 30 | | 40 | 50 | | | + | | 15 | | + | | 20 | | 15 | | | | б3= -30 | | 50 | | 40 | | 35 | | 30 | | 100 | 30 | | | + | | + | | + | | 30 | | + | | | | | 15 | 45 | 45 | 50 | 15 | 170 | | |
Д1,4=0 показывает, что существует еще один цикл с такой же ценой (1,2)-(1,4)-(2,4)-(2,2). Но так как при этом общая стоимость не изменится, то нет смысла менять перевозки. Таким образом, решение верное, т.к. Дij ?0. ОТВЕТ: |
| B1 | B2 | B3 | B4 | B5 | a | | A1 | | 45 | | 60 | | 40 | | 60 | | 95 | 90 | | | 15 | | 30 | | 45 | | | | | | | | A2 | | 35 | | 30 | | 55 | | 30 | | 40 | 50 | | | | | 15 | | | | 20 | | 15 | | | | A3 | | 50 | | 40 | | 35 | | 30 | | 100 | 30 | | | | | | | | | 30 | | | | | | b | 15 | 45 | 45 | 50 | 15 | 170 | | |
Задача 4 №59 Условие: Определить экстремум целевой функции вида = 1112+2222+1212+11+22 при условиях 111+122<=>1 211+222<=>2 . Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки. Составить функцию Лагранжа. Получить систему неравенств в соответствии с теоремой Куна-Таккера. Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования. Дать ответ с учетом условий дополняющей нежесткости. |
№ | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 | Знаки огр. 1 2 | | 59 | 4.5 | 1.5 | -5 | -2 | -1 | max | 2 | -3 | 5 | 4 | 9 | 13 | | | | |
Решение: Целевая функция: F=-5x12-x22-2x1x2+4.5x1+1.5x2 Ограничения g1(x) и g2(x): > 1) определим относительный максимум функции, для этого определим стационарную точку (х10, х20): > > 2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции F11 (х10, х20) = -10 < 0 F12 (х10, х20) = -2 F21 (х10, х20) = -2 F22 (х10, х20) = -2 Т.к. условие выполняется, то целевая функция является строго вогнутой в окрестности стационарной точки 3) Составляем функцию Лагранжа: L(x,u)=F(x)+u1g1(x)+u2g2(x)= =-5x12-x22-2x1x2+4.5x1+1.5x2+u1(2x1-3x2-9)+u2(5x1+4x2-13) Получим уравнения седловой точки, применяя теорему Куна-Таккера: i=1;2 Объединим неравенства в систему А, а равенства в систему В: Система А: Система В: Перепишем систему А: 4)Введем новые переменные V={v1,v2}?0; W={w1,w2}?0 в систему А для того, чтобы неравенства превратить в равенства: Тогда . Следовательно, система В примет вид: - это условия дополняющей нежесткости. 5) Решим систему А с помощью метода искусственных переменных. Введем переменные Y={y1; y2} в 1 и 2 уравнения системы и создадим псевдоцелевую функцию Y=My1+My2>min Y'=-Y= -My1-My2>max. В качестве свободных выберем х1, х2, v1, v2, u1, u2; а в качестве базисных y1, y2, w1, w2. Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы: Решим с помощью симплекс-таблицы. Найдем опорное решение: Примечание: вычисления производились программно, см Приложение |
| b | x1 | x2 | u1 | u2 | v1 | v2 | | Y' | -6M | | -12M | | -4M | | -M | | 9M | | M | | M | | | | | | | | | | | | | | | | | | | y1 | 4,5 | | 10 | | 2 | | -2 | | -5 | | -1 | | 0 | | | | | | | | | | | | | | | | | | | y2 | 1,5 | | 2 | | 2 | | 3 | | -4 | | 0 | | -1 | | | | | | | | | | | | | | | | | | | w1 | -9 | | -2 | | 3 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | w2 | -13 | | -5 | | 4 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | b | w1 | x2 | u1 | u2 | v1 | v2 | | Y' | 48M | | -6M | | -22M | | -1M | | 9M | | 1M | | 1M | | | | | | | | | | | | | | | | | | | y1 | -40,5 | | 5 | | 17 | | -2 | | -5 | | -1 | | 0 | | | | | | | | | | | | | | | | | | | y2 | -7,5 | | 1 | | 5 | | 3 | | -4 | | 0 | | -1 | | | | | | | | | | | | | | | | | | | x1 | 4,5 | | -0,5 | | -1,5 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | w2 | 9,5 | | -2,5 | | -3,5 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | b | w1 | x2 | y1 | u2 | v1 | v2 | | Y' | 68,25M | -8,5M | | -30,5M | -0,5M | | 11,5M | 1,5M | | 1M | | | | | | | | | | | | | | | | | | | u1 | 20,25 | | -2,5 | | -8,5 | | -0,5 | | 2,5 | | 0,5 | | 0 | | | | | | | | | | | | | | | | | | | y2 | -68,25 | | 8,5 | | 30,5 | | 1,5 | | -11,5 | | -1,5 | | -1 | | | | | | | | | | | | | | | | | | | x1 | 4,5 | | -0,5 | | -1,5 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | w2 | 9,58 | | -2,5 | | -3,5 | | 0 | | 0 | | 0 | | 0 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | b | w1 | x2 | y1 | y2 | v1 | v2 | | Y' | 0 | | 0 | | 0 | | M | | M | | 0 | | 0 | | | | | | | | | | | | | | | | | | | u1 | 5,413043 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | u2 | 5,934783 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | x1 | 4,5 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | w2 | 9,5 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Т. о, w1=x2=y1=y2=v1=v2=0; u1=5,413043; u2=5,934783; x1=4.5; w2=9.5. б) Условия дополняющей нежесткости не выполняются (u2w2?0), значит решения исходной задачи квадратичного программирования не существует. ОТВЕТ: не существует. Приложение #include <math.h> #include <stdio.h> main() { int i,j,k,m; double h,n,a[5][7],b[5][7]; clrscr(); printf ("Введите числа матрицы А "); for (i=0; i<5; i++){for(j=0; j<7; j++) {scanf ("%lf",&n); a[i][j]=n;}} printf ("Введите координаты разрешающего элемента\n"); scanf("%d",&k) ; scanf ("%d",&m); printf (" матрицa A \n"); for (i=0; i<5; i++) {for(j=0; j<7; j++) printf (" %lf",a[i][j]);printf ("\n");} printf (" координаты \n "); printf("%d %d",k,m) ; h=1/a[k][m]; b[k][m]=h; printf ("\n h=%lf",h); for (i=0; i<7; i++) { if (i!=m) b[k][i]=a[k][i]*b[k][m]; } for (i=0;i<5; i++) { if (i!=k) b[i][m]=-a[i][m]*b[k][m];} for (i=0;i<5;i++) { for (j=0;j<7;j++) if ((i!=k)&&(j!=m)) b[i][j]=a[i][j]+a[k][j]*b[i][m]; } printf ("\n результат "); printf (" матрицa B \n"); for (i=0; i<5; i++) {for(j=0; j<7; j++) printf (" %lf",b[i][j]);printf ("\n");} getch(); }
Страницы: 1, 2, 3
|