|
1 2
3 . n
|
Cx
Bx A0 A1. Am
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1. m
|
де: Bx - базисні змінні;
Cx - коефіцієнти цільової
функції при базисних змінних;
симплекс різниця;
A1. Am - коефіцієнти в
обмеженнях;
A0 - права частина.
Кожна ітерація полягає в заміні (перерахунку)
базисної змінної.
4.
Алгоритм двоїстого симплекс-методу рішення задачі та опис програми
1. Зведення ЦФ до максимуму, а обмежень до
рівностей (канонічний вигляд).
. Запис двоїстої задачі
. Побудова незалежних векторів на підставі рядків ДЗ.
. Вибір спряженого базису:
ü Довільний вибір m
рівнянь;
ü Розв’язання цієї
системи m з рівнянь;
ü Підстановка
розв’язку в кожне із залишених обмежень та перевірка: чи задовольняє спряжений
базис;
ü Якщо спряжений
базис задовольняє, то формування псевдолану (розрахунок симплекс-таблиці);
ü Якщо спряжений
базис не задовольняє, то треба обрати новий. Якщо на генерації нових сполучень
не буде знайдено спряжений базис, то немає розв’язку.
Спряжений базис (А1А4А5А6)
. Заповнення симплекс-таблиці.
. Вибір направляючого елементу.
. Всі інші симплекс-перетворення в ДСМ аналогічні
прямому СМ.
Рис. 1 Алгоритм двоїстого симплекс-методу
5.
Ітерації програмного рішення задачі
(C*) Leonchenko Anna. PNK-41
Условие считывается из файла <in. txt>
Вывод выполняется в файл <out. txt>
Размерность задачи 4x6:
(20x1+0.50x2+0x3+0x4+0x5+0x6)
{1} 1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53
{2} 0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60
{3} 0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59
{4} 0x1-1x2+0x3+0x4+0x5+1x6=-1000
Опис процедур програми:value - "," міняє на". ”;
Procedure prov - Обрізання пробілів на початку та в кінці
рядку;
Procedure error - недопустимий символ;
Function ReadData - зчитування з файлу;
Function Druk - перетворює real в integer, знаходить
дробову частину, перетворює число в рядок;
Procedure WriteUmovu - вивід даних зчитаних з вхідного
файлу;
Procedure vivod - вивід ітерацій;
Procedure RozDelta - розрахунок дельта та запис в
симплекс-таблицю;
Function napr_str - визначення спрямовуючого рядка;
Function napr_st - визначення спрямовуючого
стовпчика;
Procedure pererah - перерахунок симплекс-таблиці за
формулою прямокутника;
Function simpl - перевірка.
.
Алгоритм методу симплекс-таблиць рішення задачі
1. Визначення спрямовуючого стовпчика j*
Якщо відсутнє, то розв’язок знайдено: базисні
змінні дорівнюють, а небазисні - 0
. Визначення спрямовуючого рядка і*
Якщо і* відсутнє, тобто в
стовпчику знаходиться значення не більше 0, то розв’язок відсутній (ОДР не
обмежена зверху), інакше фіксуємо спрямовуючий елемент: (2 1) =1
. Перерахунок таблиці (власне заміна базисних
змінних):
· ділення значень
спрямовуючого рядка на спрямовуючий елемент:
· обнулення спрямовуючого
стовпця, крім спрямовуючого елемента:
· перерахунок решти значень
за формулою прямокутників:
4. Перевірка ітерації:
· цільова функція має не
зменшуватися;
· номер ітерації має не
перевищувати їхню максимальну кількість:
· базисні змінні мають мати
одиничний вектор;
· розрахунок має співпадати
як за формулою спрямовуючого стовпчика, так і за формулою
"прямокутника".
Розв’язок знайдено, тому що всі 0. Після
розрахунку потрібно виконати наступну перевірку:
· чи всі М-змінні
дорівнюють 0 якщо ні, то розв’язок відсутній або ж вибрано занадто малий
коефіцієнт m.
· Значення Z має
дорівнювати значенню Ci Xi
Рис. 2 Алгоритм симплекс-методу
Канонічна форма, розмірність 4*8
Ітерації рішення задачі вручну.
Размерность задачи НЛП - 4 х 8
(20X1 +0.5X2-200X6-200X8)
{1} 1.04X1 + 0.051X2 + 1X3 = 90
{2} 3X1 + 0.085X2 + 1X4 = 200
{3} 1X1 + - 1X5 + 1X6 = 9
{4} 1X2 + - 1X7 + 1X8 = 1000
7.
Висновок та дослідження на чутливість моделі
|
Модифікація
вхідних значень
|
Пошукові
xі
|
Цільова
функція Z
|
Примітка
|
|
1
|
Лісовий
масив складається з Е=100м3 Р=250м3
|
L1=2,6
L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=20 D2=0,5
|
1520
|
Зі
збільшенням площі лісового масиву сумарний прибуток заводу збільшуються.
|
|
2
|
Прибуток
приносять: Пиломатеріали D1=30грн Фанера D2=2грн
|
L1=2,6
L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=30 D2=3
|
3125,90
|
Сумарний
прибуток збільшуються.
|
|
3
|
Якщо
використовувати менше ялинових лісоматеріалів 1=2,5м3
|
L1=2,5
L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=20 D2=0,5
|
1830,60
|
Сумарний
прибуток збільшуються, так як матеріал використовується менше.
|
Рішення інших задач
Приклад №1
Вхідний файл:
6
0.5 0 0 0 0
0.049 1.04 0 0 0 = 100
- 0.062 - 3.12 1 0 0 = - 40
0.049 1.04 0 1 0 = 77.59
- 1 0 0 0 1 = - 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja
<in1. txt>vukon v file <out1. txt>zadachi 4x6:
(20x1+0.50x2+0x3+0x4+0x5+0x6)
{1} 1x1+0.05x2+1.04x3+0x4+0x5+0x6=100
{2} 0x1-0.06x2-3.12x3+1x4+0x5+0x6=-40
{3} 0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59
{4} 0x1-1x2+0x3+0x4+0x5+1x6=-1000
Приклад №2
Вхідний файл:
6
2 0 0 0 0
0.049 1.04 0 0 0 = 86.53
- 0.062 - 3.12 1 0 0 = - 59.6
0.049 1.04 0 1 0 = 77.59
- 1 0 0 0 1 = - 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja <in2.
txt>vukon v file <out2. txt>zadachi 4x6:
(30x1+2x2+0x3+0x4+0x5+0x6)
{1} 1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53
{2} 0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60
{3} 0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59
{4} 0x1-1x2+0x3+0x4+0x5+1x6=-1000
Приклад №3
Вхідний файл:
6
0.5 0 0 0 0
0.02 1.04 0 0 0 = 86.53
- 0.062 - 3.12 1 0 0 = - 59.6
0.049 1.04 0 1 0 = 77.59
- 1 0 0 0 1 = - 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja <in4.
txt>vukon v file <out4. txt>zadachi 4x6:
{1} 1x1+0.02x2+1.04x3+0x4+0x5+0x6=86.53
{2} 0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60
{3} 0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59
{4} 0x1-1x2+0x3+0x4+0x5+1x6=-1000
8.
Дослідження розробленої програми для великих розмірностей
(c) Leonchenko Anna. PNK-41dlja zchityvannja
<dat2. txt>vukon v file <vvv. txt>zadachi 5x11:
(-17x1-20x2-22x3-25x4-28x5-30x6+0x7+0x8+0x9+0x10+0x11)
{1} -
33x1+0x2-43x3+0x4-60x5+0x6+1x7+0x8+0x9+0x10+0x11=-1050
{2}
0x1-28x2+0x3-40x4+0x5-50x6+0x7+1x8+0x9+0x10+0x11=-600
{3}
1x1+1x2+0x3+0x4+0x5+0x6+0x7+0x8+1x9+0x10+0x11=5
{4}
0x1+0x2+1x3+1x4+0x5+0x6+0x7+0x8+0x9+1x10+0x11=15
{5} 0x1+0x2+0x3+0x4+1x5+1x6+0x7+0x8+0x9+0x10+1x11=15
Найбільша розмірність, яка може бути вирішена
даним програмним продуктом складає матрицю розміром 50*50.
Список
використаної літератури
1. Бабич В.І. Конспект лекцій з дисципліни "Математичні
методи дослідження операцій"
. Культин Н.Б. Программирование в Turbo Pascal 7.0 - Спб.: БХВ -
Санкт-Петербург, 1999 - 240 с.
Додаток
Лістинг програми
program
simplex;crt;=50;=50;, file_input, file_output, iter, zn_max: string;, res,fl:
boolean;, k, n, m, j0, i0, i, j,nom_it: integer;: array [1. mmax] of real;:
array [1. nmax,0. mmax] of real;: array [1. nmax] of byte;: array [0. mmax] of
real;: array [1. nmax] of char;: char;
{ x:
array [1. mmax] of real; }value (var s: string): string;: string;: integer;:
='';s [1] =',' then v: =v+'. ' else v: =v+s [1];(s,1,1);(s [1] =' ') or
(s='');: =v;;prov (var s: string);s [1] =' ' then(s,1,1);s [1] <>' ';s
[length (s)] =' ' then(s,length (s),1);s [length (s)] <>' ';;error (sub:
string);('Недопустимий символ ');i: =1 to length (sub) dosub [i] of
'A'.
'Z','a'. 'z': write ('Буква ');
'0'.
'9',',','. ':;write ('спеціальний символ ');;;;ReadData: boolean;: string;, i,
j: integer;: =true;(input,file_input);(input);ioresult<>0
then('Файл'<+file_input+'>не найдено');;;(s);(s);: =value (s);(sub, n,
code);code<>0 then('Помилка: рядок 1-й число 1-ше ');:
=false;(sub);;(s);: =value (s);(sub, m, code);code<>0 then(' Помилка:
рядок 1-й число 2-ге ');: =false;(sub);;(n>nmax) or (m>mmax) then
begin('Указана розмірність задачі не підходить обмеженням задачі');:
=false;;(s);(s);j: =1 to m do: =value (s);(sub, c [j], code);code<>0
then(Помилка: рядок 2-й', j, 'число);: =false;(sub);;(s);;_max: =value (s);i:
=1 to n do(s);(s);j: =1 to m do: =value (s);(sub,a [i,j],code);code<>0
then('Помилка: рядок', i+2,'-число ',j,');: =false;(sub);;(s);;[i]: =s
[1];(s,1,1);(znak [1] <>'>') and (znak [1] <>'<') and (znak
[1] <>'=') then begin('Ошибка: рядок ', i+2,' - й: не вірно вказаний
знак');: =false;;(s);: =value (s);(sub,a [i,0], code);code<>0
then('Ошибка: рядок ', i+2,' - й',m+1,'оє: ');: =false;(sub);;;;kanon;: real;:
=1;i: =1 to m domax<c [i] then max: =c [i];: =10*max;(length (zn_max) =3)
and ( (zn_max [2] ='I') or (zn_max [2] ='i')) and ( (zn_max [3] ='N') or
(zn_max [3] ='n')) theni: =1 to m do[i]: =-c [i];i: =1 to n doa [i,0] <0
thenj: =0 to m do[i,j]: =-a [i,j];: =false;znak [i] of
'>':
znak [i]: ='<';
'<':
znak [i]: ='>';;;if (a [i,0] =0) and (znak [i] ='<') thenj: =1 to m
do[i,j]: =-a [i,j];[i]: ='>';: =false;;znak [i] of
'>':
begin(m);[m]: =0;[i,m]: =-1;j: =1 to n doi<>j then[j,m]: =0;;
'<':
begin(m);[m]: =0;[i,m]: =1;j: =1 to n doi<>j then[j,m]: =0;;
'=':
begin(m);[m]: =0;[i,m]: =1;j: =1 to n doi<>j then[j,m]: =0;;;: =true;[i]:
='^';;(res=true);;druk (b: real; im: boolean): string;, s1: string;, i, j:
integer;: ='';: =trunc (b);: =1;b<0 then(i);: =abs (cel);;cel div 10 >0
do: =cel div 10;(i);;frac (b) <>0 then: =i+3;(b: 4: 2,s);str (trunc (b),
s);im then: =8-i;: ='';j: =1 to i do: =s1+' ';: =s1+s;;: =s;;vivod;i,j:
integer;('Iteracija #',nom_it:
4);('--------------------------------------------------------------------');('--------------------------------------------------------------------');('Cil.
funk ');i: =1 to m do(druk (c
[i],true));('');('------------------------------------------------------------------');('');('
Bx ');j: =0 to m do(' A',j,' ');('');i: =1 to n do(druk (c [b [i]],true));('
X',b [i]);(druk (a [i,0],true));j: =1 to m do(druk (a [i,j],true));(' ');;('------------------------------------------------------------------');('R
');i: =0 to m do(druk (d [i],true));('
');('-------------------------------------------------------------------');('');_it:
=nom_it+1;;WriteUmovu;, j: integer;;(' (c) Leonchenko Anna. PNK-41');;('File
dlja zchityvannja <'+file_input+'>');file_output='con' then('Vivid vukon
na ekran')writeln ('Vivid vukon v file <'+file_output+'>');('Rozmirnist
zadachi ', n, 'x', m, ': ');;('max (');j: =1 to m do(c [j+1] >=0) and (j<>m)
then write (druk (c [j],false),'x', j,'+')write (druk (c [j],false),'x',j);(')
');i: =1 to n do('{', i,'} ');j: =1 to m do(druk (a [i,j],false),'x',j);(a
[i,j+1] >=0) and (j<>m) then write ('+');;('=',druk (a
[i,0],false));;file_output='con' then: =readkeykey=#13;;RozDelta; {rozraxynok
delta}, j, k: integer;: boolean;i: =1 to n do {zapisyemo ne 0 elementu}j: =1 to
m doa [i,j] =1 then: =false;k: =1 to n do(i<>k) then(a [k,j] =0) then pr:
=truebegin pr: =false; break; end;pr thenb [i]: =j; break; end;;j: =0 to m do
{podchet delta}j=0 then d [j]: =0 else d [j]: =-c [j];i: =1 to n do[j]: =d [j]
+a [i,j] *c [b [i]];;;napr_str (var i0: integer): boolean; {vuznachennja napr-j
stroku}: real;: integer;_str: =false;: =0;: =0;i: =1 to n do(a [i,0]
<value1) then: =a [i,0];: =i; {nomer napr-j stroku}_str: =true;;;napr_st
(i0: integer; var j0: integer): boolean; {viznachennja napr-go stovbchika}:
real;: integer;_st: =false;: =0;: =0;j: =1 to m do(a [i0,j] <0) and (abs (d
[j] /a [i0,j]) >value1) then: =abs (d [j] / (a [i0,j]));: =j; {zapusyemo
nomer stovbchika}_st: =true;;;pererah; {pererahovyemo matrucy}, j: integer;j:
=0 to m doj<>j0 theni: =1 to n doi<>i0 then[i,j]: =a [i,j] - (a
[i0,j] *a [i,j0] /a [i0,j0]);[j]: =d [j] - (a [i0,j] *d [j0] /a [i0,j0]);;j: =0
to m doj<>j0 then a [i0,j]: =a [i0,j] /a [i0,j0]; {rozrahynok napr.
stoku}i: =1 to n doi<>i0 then a [i,j0]: =0; {rozrahynok napr. stovb.
}[j0]: =0;[i0,j0]: =1;[i0]: =j0; {zapis nomera stovb. };simpl: boolean; {}:
=true;napr_str (i0) donapr_st (i0,j0) then;;: =false;;;;
{file_input:
='in. txt';_output: ='out. txt';: =true; }_input: =paramstr (1);_output:
=paramstr (2);: =paramstr (3);;(file_input='') or (file_output='') then('Vvedit
pravilno dani');('DUOSIMPL. exe inputfile outputfile/con [Y/y] ');;;(iter='Y')
or (iter='y') then it: =true;file_output<>'con'
then(output,file_output);(output);;: =true;not ReadData then halt;
{Kanon;
};;;;_it: =1;;not simpl then {nema rishennja}('Rishen nemaje');;('Rishennja
znajdeno!!! Param-pam-pam');('Z=',druk (d [0],true));('X = (');i: =1 to m do: =false;j:
=1 to m dob [j] =i then begin write (druk (a [j,0],false),' '); fl: =true;
end;fl=false then write ('0 ');;(') ');.