Зміст:
Введення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Постановка завдання
Опис методу
Математична постановка задачі ... ... ... ... ... ... ... ....
Лістинг програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Блок-схема ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....
Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Введення
Метою даної курсової роботи є вирішення конкретної задачі лінійного програмування методом поліпшеного симплекс-методу. У всіх таких завданнях потрібно знайти максимум або мінімум лінійної функції за умови, що її змінні приймають невід'ємні значення і задовольняють деякій системі лінійних рівнянь або лінійних нерівностей якій системі, що містить як лінійні рівняння, так і лінійні нерівності. Кожна з цих завдань є окремим випадком загальної задачі лінійного програмування.
Для вирішення завдань лінійного програмування створені спеціальні методи. Вивченню одного з них, а саме поліпшеному симплекс-методу, присвячена ця курсова робота.
Постановка завдання
На основі вивченого алгоритму симплекс-методу розробити програму з наступного завдання: Вихідна матриця коефіцієнтів заноситься в пам'ять як матриця А, праві частини обмежень в колонці 0. Таким чином, в матрицю входять М +2 рядків, М обмежень, цільова функція і штучна цільова функція. Вона має P рядків крім рядка 0, які містять вихідні, нові й штучні змінні. Матриця B складається із стовпців значень змінних і значень цільової функції, матриці звернення розмірністю mxm, двох рядків симплекс - множників і останнього стовпця, в якому всі елементи, крім останніх двох, рівні 0, а останні два рівні - 1:
b1 β11 β 1m 0
b2 β21 β 2m 0
B = bm βm1 β mm 0
-Z0 π1 πm 1
-W0 ơ1 ơ m 1
Необхідно перевести дану програму за допомогою мови Turbo Pascal.
Для перевірки працездатності програми необхідно ввести дані з наступного завдання:
Знайти такі невід'ємні x 1, x 2, що
2х 1 - х 2 ≤ 4,
x 1 - 2x 2 ≤ 2,
x 1 + x 2 ≤ 5,
і мінімізувати функцію-3x 1 + x 2 = z.
Зробимо декілька зауважень щодо переваг і недоліків поліпшеного симплекс-методу і симплекс-методу. При використанні поліпшеного симплекс-методу вихідна матриця обмежень запам'ятовується. У симплекс методі її елементи змінюються при проходженні ітерацій. Таким чином, оскільки в покращеному симплекс-методі потрібні також звернення базису і симплекс - множники, недоліком поліпшеного симплекс-методу є велика потреба в машинній пам'яті.
Великою перевагою поліпшеного симплекс-методу є зменшення кількості обчислень. Таким чином, кількість обчислень в задачі лінійного програмування безпосередньо пов'язане, скоріше, з кількістю обмежень, ніж з кількістю змінних, які в загальному випадку значно більше.
Поліпшений симплекс-метод безпосередньо обчислює звернення базису і симплекс - множники. Ці величини не треба витягати з остаточної таблиці. Це може допомогти при подальшому стійкості рішення.
Опис методу
Для вирішення завдань лінійного програмування існує безліч методів. Розглянемо один з них.
Покращений (модифікований) симплекс-метод
Для початку розповімо, що таке симплекс-метод. Слово SIMPLEX у звичайному розумінні означає простий, несоставной, на противагу слову COMPLEX.
Даний метод отримав кілька різних форм (модифікацій) і був розроблений в 1947 році Г. Данцигом.
Сутність симплекс-методу полягає в тому, що якщо число невідомих більше числа рівнянь, то дана система невизначена з незліченною безліччю рішень. Для вирішення системи всі невідомі довільно підрозділяють на базисні і вільні. Число базисних змінних визначається числом лінійно-незалежних рівнянь. Решта невідомі вільні. Їм надають довільні значення і підставляють в систему. Будь-якому набору вільних невідомих можна надати незліченна безліч довільних значень, які дадуть незліченна безліч рішень. Якщо всі вільні невідомі прирівняти до нуля, то рішення буде складатися із значень базисних невідомих. Таке рішення називається базисним.
У теорії лінійного програмування існує теорема, яка стверджує, що серед базисних рішень системи можна знайти оптимальне, а в деяких випадках і кілька оптимальних рішень, але всі вони забезпечать екстремум цільової функції. Таким чином, якщо знайти будь-якої базисний план, а потім поліпшити його, то вийде оптимальне рішення. На цьому принципі і побудований симплекс-метод.
Одним з модифікацій симплекс-методу є покращений симплекс-метод.
У літературі цей метод зустрічається також під назвою методу оберненої матриці або модифікованого симплекс-методу.
При вирішенні завдань лінійного програмування, в яких n (кількість змінних) значно більше m (кількість обмежень), покращений симплекс-метод вимагає в порівнянні з іншими значно меншої кількості обчислювальних операцій та обсягу пам'яті ЕОМ.
У поліпшеному симплекс-методі реалізується та ж основна ідея, що і в звичайному симплекс-методі, але тут на кожній ітерації перераховується не вся матриця A -1, зворотна матриці обмежень A, а лише та частина, яка відноситься до поточного базису A x.
Розглянемо поетапно кроки рішення задачі лінійного програмування поліпшеним симплекс-методом:
1.В початку першого циклу нам відомі зворотна матриця EQ A \ sp (-1; \ s \ do (x)) (одинична матриця), базисне рішення x b = EQ A \ sp (-1; \ s \ do (x )) b.
2.Образуем для кожної небазисной змінної характеристичну різниця D j, використовуючи рівняння:
D j = c j - EQ \ i \ su (i = 1; n; p i * A ij) = c j - pP j,
Де p - двоїсті змінні, які можна знайти наступним чином:
p = c x * EQ A \ sp (-1; \ s \ do (x)),
Де c x - вектор коефіцієнтів цільової функції при базисних змінних.
3.Предполагая, що використовується стандартне правило вибору вводиться стовпця, знаходимо:
EQ min \ d \ ba10 () j D j = D s.
4.Якщо D s ³ 0 - процедура зупиняється. Поточне базисне рішення є оптимальним.
5.Якщо D s £ 0, обчислюємо перетворений стовпчик:
EQ (P ;-) s = EQ A \ sp (-1; \ s \ do (x)) P s
6.Пусть
EQ (P ;-) s = (EQ (a ;-) 1s, EQ (a ;-) 2s, ..., EQ (a ;-) ms).
Якщо все EQ (a ;-) is £ 0 - процедура зупиняється: оптимум необмежений.
7.В іншому випадку знаходимо виведену з базису змінну:
EQ \ f (x br; (a ;-) rs) = min \ d \ ba20 () (a ;-) rs ³ 0 = q.
8.Строім збільшену матрицю:
EQ \ b \ bc \ [(A \ sp (-1; \ s \ do (x)) \ ac (:;:;:) (P ;-) s) -1; \ s \ do (x:; :;:
і трансформуємо її з провідним елементом EQ (a ;-) rs. Перші m стовпців результат дають матрицю, зворотну новому базису. Перетворимо базисне рішення:
x bi Ü x bi - q * EQ (a ;-) is, i ¹ r,
x br Ü q
і переходимо до етапу 2.
Цей варіант називають також модифікованим симплекс-методом, оскільки він зменшує обсяг обчислень на кожному кроці. Ідея полягає в тому, що на кожному кроці конаніческую форму завдання для поточного базису можна отримати незалежно від інших таких форм безпосередньо з вихідного запису стандартної завдання ЛП. Для цього потрібно: (1) зберігати вихідну запис задачі протягом всієї роботи методу, це та ціна, яку доводиться платити за більше швидкодію;
(2) використовувати так звані симплекс - множники π - коефіцієнти для безпосереднього переходу від вихідної запису задачі до її поточної конаніческой формі базису; і (3) використовувати звернений базис У-№ - матрицю розміру mxm, що дозволяє обчислювати на кожному кроці провідний стовпець a s і оновлювати симплекс - множники π.
Звичайною є щільність 5% або менше. Покращена форма симплекс-методу в більшій мірі здатна використовувати переваги, що випливають з цього факту. У цій формі характеристичні різниці і ведучий вектор обчислюються безпосередньо за вихідними даними. Оскільки вихідна матриця слабозаполнена, а перемножування варто робити тільки тоді, коли обидва співмножники відмінні від нуля, то час обчислень значно скорочується.
На додаток до цього використання тільки вихідних даних призводить до того, що зменшується можливість накопичення помилок округлення. Навпаки, стандартні симплексних таблиці, навіть якщо вони спочатку є слабозаполненнимі, в ході ітеративного процесу швидко заповнюються ненульовими елементами. Таким чином, час обчислень збільшується, і, оскільки кожна таблиця обчислюється з попередньої, нагромадження помилок може почати грати більш серйозну роль.
Математична постановка задачі
Завдання: Знайти такі невід'ємні x1, x2, що
2х 1 - х 2 ≤ 4,
x 1 - 2x 2 ≤ 2,
x 1 + x 2 ≤ 5,
і мінімізувати функцію-3x 1 + x 2 = z.
Графічне рішення (див. малюнок) показує, що точка мінімуму - це точка (3,2), де z = -7. Виродженість (при зверненні кількох змінних в 0, базис називають виродженим) виникає, оскільки прямі, відповідні обмеженням, перетинаються в одній точці (2,0). У нашій задачі у вершині перетинаються три прямі (зазвичай вершина є перетином всього двох прямих).
Малюнок 1.
При використанні симплекс-методу перша таблиця має наступний вигляд:
Таблиця 1.
Змінна х 1 входить в базис. У стовпці х 1 коефіцієнти 2 і 1 пометим зірочкою, так як в точці мінімуму вони мають точку співпадіння 4 / 2 = 2 / 1.
При виборі інших змінних все одно ітерація перетворюється в 0, отже, базис буде виродилися. Виберемо змінну х3 і отримаємо наступну таблицю:
Таблиця 2.
З таблиці видно що мінімум функції z дорівнює -7 (при х 1 = 3, х 2 = 2).
Якщо вибрати змінну х4, то отримаємо те ж саме рішення.
Для продовження рішення необхідно змінити обмеження, це дозволить змінити положення точки А, а так само уникнути виродження. Для це візьмемо деяку змінну ε - мала величина (тому що обмеження в точці А не будуть виконуватися одночасно, див. малюнок 2).
Отримаємо наступне:
2х 1 - х 2 ≤ 4 + ε
x 1 - 2x 2 ≤ 2 + ε 2.
У остаточне рішення буде входити ε. Потім ε слід звернути в 0.
Якщо вирожденність немає, то симплекс-методом завдання лінійного програмування вирішується за кінцеве число кроків (за умови, що рішення існує).
Таким чином, функція z убуває на кожному кроці. Оскільки є не більше (n / m) допустимих рішень, мінімум буде дорівнювати не більш ніж за (n / m) ітерацій.
Лістинг програми
{Reshenie zadachi lin prog-ya modifiz simplex-metodom}
Program Simpl_ST;
uses crt;
label 500, 1800, 1900, 2000, Zikl, {} 2500, 1960;
const M1_K = 30; M2_K = 30; P_K = 30; M_K = 30;
var i, j, k, zz, GC, EC, LC, N, MM, M, MK, N1, P, M1, M2, N0: integer;
A: array [1 .. M2_K, 0 .. P_K] of integer;
B: array [1 .. M2_K, 0 .. M1_K] of integer;
BS: array [1 .. M_K] of integer;
V: array [1 .. M2_K] of integer;
NB, SL, C: array [1 .. P_K] of integer;
PB, PA, L, ML, NI, SS: integer;
Zero, NILL, MIN, RT, DF: real;
S, PV, R: integer;
P_str, PE_str: string;
cc: integer;
Dop: boolean;
buf: array [1 .. 36] of byte absolute 0: $ 41a;
procedure clearkeybuf; {ochistka bufera klaviatury}
begin
inline ($ fa); {cli - divryvaniya nado zadivtit pri}
buf [1]: = buf [3]; {vmeshatelstve v bufer}
inline ($ fb); {sti}
end;
procedure Init;
begin
for i: = 1 to M2_K do for j: = 0 to P_K do A [i, j]: = 0;
end;
function DelZero (X: Real): string; {Udalenie nulei posle zapyatoi}
var i, l, sp: integer;
Drob, Space: boolean;
Xst, Res: string;
begin
Xst :=''; Drob: = False;
Str (X: 13:10, Xst);
for i: = 1 to Length (Xst) do if Xst [i ]='.' then Drob: = True;
if Drob then begin
for i: = Length (Xst) downto 1 do begin
if Xst [i] = "0" then Xst [i]: = 'Z';
if Xst [i ]='.' then begin Xst [i]: = 'Z'; Break end;
if Xst [i] in ['1 '.. '9'] then Break;
{Case XS [j] of
"0": XS [j]: = 'Z';
'.': XS [j]
1 .. 9: Break;
end;}
end;
for i: = 1 to Length (Xst) do if Xst [i] = 'Z' then begin l: = i; Break end;
Res: = Copy (Xst, 1, l-1);
end
else Res: = Xst;
Space: = False;
for i: = 1 to Length (Res) do if Res [i] = '' then
begin l: = i; Space: = True end; {del spaces}
if Space then Res: = Copy (Res, l +1, Length (Res)-l);
{Sp: = 0;
for i: = 1 to Length (Res) do begin
if Res [i] = '' then inc (sp);
end;
if (X> = 0) and (sp = 0) then Res: = '' + Res;}
if X> = 0 then Res: = '' + Res;
DelZero: = Res;
end;
procedure Gosub9000;
var PE, PEint: real;
PC, PD: integer;
MID, RIGHT: string;
begin
PC: = round (int (PB/100));
P_str :='';
if PC = 0 then write ('') else write (Copy (P_str, 1, PC)); {LEFT $ (P $, PC)}
PC: = PB - 100 * PC;
PD: = round (int (PC/10));
PC: = PC - 10 * PD;
if PD = 0 then PD: = 1;
if PA <0 then P_str: = P_str +'-';
PE: = abs (PA); {A ^ X = EXP (X * LN (A))}
PE: = PE + 5 * EXP ((-1-PC) * LN (10)); {PE: = PE + 5 * 10 ^ (-1-PC)}
if PE> = EXP (PD * LN (10)) then begin write (PA); Exit end; {PE> = 10 ^ PD}
{Str (PE: 13:10, PE_str); {Copy (Str, 1, N); Left}
PEint: = int (PE);
PE_str: = DelZero (PEint);
MID: = Copy (PE_str, 2, PD); {MID $ (PE_str, 2, PD)}
P_str: = P_str + MID;
{PRINT RIGHT $ (P $, PD +1)}
RIGHT: = Copy (P_str, Length (P_str) - (PD +1) +1, PD +1);
GotoXY (WhereX +3, WhereY);
write (RIGHT); {RIGHT $ (P $, PD +1) Copy (Astr, Length (Astr)-N +1, N); Right}
if PC = 0 then Exit;
write ('.');
PE: = int ((PE-int (PE)) * EXP (PC * LN (10)));
P_str: = '000000000 ';
PE_str: = DelZero (PE);
{PE_str: = KillZero (PE_Str);}
{P_str: = P_str + Copy (KillZero (PE_str), 2, PC);}
MID: = Copy (PE_str, 2, PC);
P_str: = P_str + MID;
RIGHT: = Copy (P_str, Length (P_str)-PC +1, PC); {RIGHT (P $, PC)}
write (RIGHT, '');
end;
procedure Gosub3000;
begin
write ('Bazis Znachenie');
for j: = 1 to N +3 do write ('X', j, '');
writeln;
PB: = 122;
for i: = 1 to ML do begin
if i = M1 then write ('tselev func');
if i = M2 then write ('iskust func');
if (i <> M1) and (i <> M2) then begin write ('', i, ''); PA: = A [i, 0]; Gosub9000 end;
for j: = 0 to N0 do begin
PA: = A [i, j];
Gosub9000;
end;
writeln ('');
end;
write ('');
end;
procedure Gosub3500;
begin
If L = 1 then writeln ('ETAP 1 vsyo esho prodolzhaetsya');
PB: = 122;
for j: = 1 to N0 do write ('C', j, '');
writeln;
for j: = 1 to N0 do begin PA: = C [j]; Gosub9000 end;
writeln;
if SS <> 1 then writeln ('X', S, 'Vhodit B, X', BS [R], 'v uslovii', R, 'vyveden iz bazisa');
writeln ('Bazis Znachenie Obrashenie Bazisa');
if SS = 1 then write ('');
{Write ('A'iS');}
for i: = 1 to ML do begin
if i = M1 then write ('Reshenie dlya tselevoy functii');
if i = M2 then write ('Reshenie dlya iskustven functii');
if (i <> M1) and (i <> M2) then write ('', BS [i]);
for j: = 0 to M do begin
PA: = B [i, j];
Gosub9000;
end;
if SS <> 1 then begin PA: = V [i]; Gosub9000 end;
writeln ('');
end;
writeln ('');
end;
begin
clearkeybuf;
Init;
textbackground (0); textcolor (15);
Введення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Постановка завдання
Опис методу
Математична постановка задачі ... ... ... ... ... ... ... ....
Лістинг програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Блок-схема ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....
Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Введення
Метою даної курсової роботи є вирішення конкретної задачі лінійного програмування методом поліпшеного симплекс-методу. У всіх таких завданнях потрібно знайти максимум або мінімум лінійної функції за умови, що її змінні приймають невід'ємні значення і задовольняють деякій системі лінійних рівнянь або лінійних нерівностей якій системі, що містить як лінійні рівняння, так і лінійні нерівності. Кожна з цих завдань є окремим випадком загальної задачі лінійного програмування.
Для вирішення завдань лінійного програмування створені спеціальні методи. Вивченню одного з них, а саме поліпшеному симплекс-методу, присвячена ця курсова робота.
Постановка завдання
На основі вивченого алгоритму симплекс-методу розробити програму з наступного завдання: Вихідна матриця коефіцієнтів заноситься в пам'ять як матриця А, праві частини обмежень в колонці 0. Таким чином, в матрицю входять М +2 рядків, М обмежень, цільова функція і штучна цільова функція. Вона має P рядків крім рядка 0, які містять вихідні, нові й штучні змінні. Матриця B складається із стовпців значень змінних і значень цільової функції, матриці звернення розмірністю mxm, двох рядків симплекс - множників і останнього стовпця, в якому всі елементи, крім останніх двох, рівні 0, а останні два рівні - 1:
b1 β11 β 1m 0
b2 β21 β 2m 0
B = bm βm1 β mm 0
-Z0 π1 πm 1
-W0 ơ1 ơ m 1
Необхідно перевести дану програму за допомогою мови Turbo Pascal.
Для перевірки працездатності програми необхідно ввести дані з наступного завдання:
Знайти такі невід'ємні x 1, x 2, що
2х 1 - х 2 ≤ 4,
x 1 - 2x 2 ≤ 2,
x 1 + x 2 ≤ 5,
і мінімізувати функцію-3x 1 + x 2 = z.
Зробимо декілька зауважень щодо переваг і недоліків поліпшеного симплекс-методу і симплекс-методу. При використанні поліпшеного симплекс-методу вихідна матриця обмежень запам'ятовується. У симплекс методі її елементи змінюються при проходженні ітерацій. Таким чином, оскільки в покращеному симплекс-методі потрібні також звернення базису і симплекс - множники, недоліком поліпшеного симплекс-методу є велика потреба в машинній пам'яті.
Великою перевагою поліпшеного симплекс-методу є зменшення кількості обчислень. Таким чином, кількість обчислень в задачі лінійного програмування безпосередньо пов'язане, скоріше, з кількістю обмежень, ніж з кількістю змінних, які в загальному випадку значно більше.
Поліпшений симплекс-метод безпосередньо обчислює звернення базису і симплекс - множники. Ці величини не треба витягати з остаточної таблиці. Це може допомогти при подальшому стійкості рішення.
Опис методу
Для вирішення завдань лінійного програмування існує безліч методів. Розглянемо один з них.
Покращений (модифікований) симплекс-метод
Для початку розповімо, що таке симплекс-метод. Слово SIMPLEX у звичайному розумінні означає простий, несоставной, на противагу слову COMPLEX.
Даний метод отримав кілька різних форм (модифікацій) і був розроблений в 1947 році Г. Данцигом.
Сутність симплекс-методу полягає в тому, що якщо число невідомих більше числа рівнянь, то дана система невизначена з незліченною безліччю рішень. Для вирішення системи всі невідомі довільно підрозділяють на базисні і вільні. Число базисних змінних визначається числом лінійно-незалежних рівнянь. Решта невідомі вільні. Їм надають довільні значення і підставляють в систему. Будь-якому набору вільних невідомих можна надати незліченна безліч довільних значень, які дадуть незліченна безліч рішень. Якщо всі вільні невідомі прирівняти до нуля, то рішення буде складатися із значень базисних невідомих. Таке рішення називається базисним.
У теорії лінійного програмування існує теорема, яка стверджує, що серед базисних рішень системи можна знайти оптимальне, а в деяких випадках і кілька оптимальних рішень, але всі вони забезпечать екстремум цільової функції. Таким чином, якщо знайти будь-якої базисний план, а потім поліпшити його, то вийде оптимальне рішення. На цьому принципі і побудований симплекс-метод.
Одним з модифікацій симплекс-методу є покращений симплекс-метод.
У літературі цей метод зустрічається також під назвою методу оберненої матриці або модифікованого симплекс-методу.
При вирішенні завдань лінійного програмування, в яких n (кількість змінних) значно більше m (кількість обмежень), покращений симплекс-метод вимагає в порівнянні з іншими значно меншої кількості обчислювальних операцій та обсягу пам'яті ЕОМ.
У поліпшеному симплекс-методі реалізується та ж основна ідея, що і в звичайному симплекс-методі, але тут на кожній ітерації перераховується не вся матриця A -1, зворотна матриці обмежень A, а лише та частина, яка відноситься до поточного базису A x.
Розглянемо поетапно кроки рішення задачі лінійного програмування поліпшеним симплекс-методом:
1.В початку першого циклу нам відомі зворотна матриця EQ A \ sp (-1; \ s \ do (x)) (одинична матриця), базисне рішення x b = EQ A \ sp (-1; \ s \ do (x )) b.
2.Образуем для кожної небазисной змінної характеристичну різниця D j, використовуючи рівняння:
D j = c j - EQ \ i \ su (i = 1; n; p i * A ij) = c j - pP j,
Де p - двоїсті змінні, які можна знайти наступним чином:
p = c x * EQ A \ sp (-1; \ s \ do (x)),
Де c x - вектор коефіцієнтів цільової функції при базисних змінних.
3.Предполагая, що використовується стандартне правило вибору вводиться стовпця, знаходимо:
EQ min \ d \ ba10 () j D j = D s.
4.Якщо D s ³ 0 - процедура зупиняється. Поточне базисне рішення є оптимальним.
5.Якщо D s £ 0, обчислюємо перетворений стовпчик:
EQ (P ;-) s = EQ A \ sp (-1; \ s \ do (x)) P s
6.Пусть
EQ (P ;-) s = (EQ (a ;-) 1s, EQ (a ;-) 2s, ..., EQ (a ;-) ms).
Якщо все EQ (a ;-) is £ 0 - процедура зупиняється: оптимум необмежений.
7.В іншому випадку знаходимо виведену з базису змінну:
EQ \ f (x br; (a ;-) rs) = min \ d \ ba20 () (a ;-) rs ³ 0 = q.
8.Строім збільшену матрицю:
EQ \ b \ bc \ [(A \ sp (-1; \ s \ do (x)) \ ac (:;:;:) (P ;-) s) -1; \ s \ do (x:; :;:
і трансформуємо її з провідним елементом EQ (a ;-) rs. Перші m стовпців результат дають матрицю, зворотну новому базису. Перетворимо базисне рішення:
x bi Ü x bi - q * EQ (a ;-) is, i ¹ r,
x br Ü q
і переходимо до етапу 2.
Цей варіант називають також модифікованим симплекс-методом, оскільки він зменшує обсяг обчислень на кожному кроці. Ідея полягає в тому, що на кожному кроці конаніческую форму завдання для поточного базису можна отримати незалежно від інших таких форм безпосередньо з вихідного запису стандартної завдання ЛП. Для цього потрібно: (1) зберігати вихідну запис задачі протягом всієї роботи методу, це та ціна, яку доводиться платити за більше швидкодію;
(2) використовувати так звані симплекс - множники π - коефіцієнти для безпосереднього переходу від вихідної запису задачі до її поточної конаніческой формі базису; і (3) використовувати звернений базис У-№ - матрицю розміру mxm, що дозволяє обчислювати на кожному кроці провідний стовпець a s і оновлювати симплекс - множники π.
Переваги методу
Поліпшений симплекс-метод, має значні переваги в порівнянні зі стандартною формою. Це відноситься до точності, швидкості і вимогам до пам'яті. Велика частина цих переваг визначається тим чинником, що, як правило, матриці великих лінійних задач (тобто з n> m> 100) є слабозаполненнимі, містять малий відсоток ненульових елементів.Звичайною є щільність 5% або менше. Покращена форма симплекс-методу в більшій мірі здатна використовувати переваги, що випливають з цього факту. У цій формі характеристичні різниці і ведучий вектор обчислюються безпосередньо за вихідними даними. Оскільки вихідна матриця слабозаполнена, а перемножування варто робити тільки тоді, коли обидва співмножники відмінні від нуля, то час обчислень значно скорочується.
На додаток до цього використання тільки вихідних даних призводить до того, що зменшується можливість накопичення помилок округлення. Навпаки, стандартні симплексних таблиці, навіть якщо вони спочатку є слабозаполненнимі, в ході ітеративного процесу швидко заповнюються ненульовими елементами. Таким чином, час обчислень збільшується, і, оскільки кожна таблиця обчислюється з попередньої, нагромадження помилок може почати грати більш серйозну роль.
Математична постановка задачі
Завдання: Знайти такі невід'ємні x1, x2, що
2х 1 - х 2 ≤ 4,
x 1 - 2x 2 ≤ 2,
x 1 + x 2 ≤ 5,
і мінімізувати функцію-3x 1 + x 2 = z.
Графічне рішення (див. малюнок) показує, що точка мінімуму - це точка (3,2), де z = -7. Виродженість (при зверненні кількох змінних в 0, базис називають виродженим) виникає, оскільки прямі, відповідні обмеженням, перетинаються в одній точці (2,0). У нашій задачі у вершині перетинаються три прямі (зазвичай вершина є перетином всього двох прямих).
Малюнок 1.
При використанні симплекс-методу перша таблиця має наступний вигляд:
Таблиця 1.
| Ітерація | Базис | Значення | Х 1 | Х 2 | Х 3 | Х 4 | Х 5 |
| 0 | Х 3 Х 4 Х 5 | 4 2 5 | 2 * 1 * 1 | -1 -2 1 | 1 . . | . 1 . | . . 1 |
| -Z | Цільова функція | -3 | 1 | . | . | . |
Змінна х 1 входить в базис. У стовпці х 1 коефіцієнти 2 і 1 пометим зірочкою, так як в точці мінімуму вони мають точку співпадіння 4 / 2 = 2 / 1.
При виборі інших змінних все одно ітерація перетворюється в 0, отже, базис буде виродилися. Виберемо змінну х3 і отримаємо наступну таблицю:
Таблиця 2.
| Ітерація | Базис | Значення | Х 1 | Х 2 | Х 3 | Х 4 | Х 5 |
| 1 | Х 3 Х 4 Х 5 | 2 0 3 | 1 . . | -1 / 2 -3 / 2 3 / 2 * | 1 / 2 -1 / 2 -1 / 2 | . 1 . | . . 1 |
| -Z | 6 | . | -1 / 2 | 3 / 2 | . | . | |
| 2 | Х 1 Х 4 Х 2 | 3 3 2 | 1 . . | . . 1 | 1 / 3 -1 -1 / 3 | . 1 . | 1 / 3 1 2 / 3 |
| -Z | 7 | . | . | 4 / 3 | . | 1 / 3 |
Якщо вибрати змінну х4, то отримаємо те ж саме рішення.
Для продовження рішення необхідно змінити обмеження, це дозволить змінити положення точки А, а так само уникнути виродження. Для це візьмемо деяку змінну ε - мала величина (тому що обмеження в точці А не будуть виконуватися одночасно, див. малюнок 2).
Отримаємо наступне:
2х 1 - х 2 ≤ 4 + ε
x 1 - 2x 2 ≤ 2 + ε 2.
У остаточне рішення буде входити ε. Потім ε слід звернути в 0.
Якщо вирожденність немає, то симплекс-методом завдання лінійного програмування вирішується за кінцеве число кроків (за умови, що рішення існує).
Таким чином, функція z убуває на кожному кроці. Оскільки є не більше (n / m) допустимих рішень, мінімум буде дорівнювати не більш ніж за (n / m) ітерацій.
Лістинг програми
{Reshenie zadachi lin prog-ya modifiz simplex-metodom}
Program Simpl_ST;
uses crt;
label 500, 1800, 1900, 2000, Zikl, {} 2500, 1960;
const M1_K = 30; M2_K = 30; P_K = 30; M_K = 30;
var i, j, k, zz, GC, EC, LC, N, MM, M, MK, N1, P, M1, M2, N0: integer;
A: array [1 .. M2_K, 0 .. P_K] of integer;
B: array [1 .. M2_K, 0 .. M1_K] of integer;
BS: array [1 .. M_K] of integer;
V: array [1 .. M2_K] of integer;
NB, SL, C: array [1 .. P_K] of integer;
PB, PA, L, ML, NI, SS: integer;
Zero, NILL, MIN, RT, DF: real;
S, PV, R: integer;
P_str, PE_str: string;
cc: integer;
Dop: boolean;
buf: array [1 .. 36] of byte absolute 0: $ 41a;
procedure clearkeybuf; {ochistka bufera klaviatury}
begin
inline ($ fa); {cli - divryvaniya nado zadivtit pri}
buf [1]: = buf [3]; {vmeshatelstve v bufer}
inline ($ fb); {sti}
end;
procedure Init;
begin
for i: = 1 to M2_K do for j: = 0 to P_K do A [i, j]: = 0;
end;
function DelZero (X: Real): string; {Udalenie nulei posle zapyatoi}
var i, l, sp: integer;
Drob, Space: boolean;
Xst, Res: string;
begin
Xst :=''; Drob: = False;
Str (X: 13:10, Xst);
for i: = 1 to Length (Xst) do if Xst [i ]='.' then Drob: = True;
if Drob then begin
for i: = Length (Xst) downto 1 do begin
if Xst [i] = "0" then Xst [i]: = 'Z';
if Xst [i ]='.' then begin Xst [i]: = 'Z'; Break end;
if Xst [i] in ['1 '.. '9'] then Break;
{Case XS [j] of
"0": XS [j]: = 'Z';
'.': XS [j]
1 .. 9: Break;
end;}
end;
for i: = 1 to Length (Xst) do if Xst [i] = 'Z' then begin l: = i; Break end;
Res: = Copy (Xst, 1, l-1);
end
else Res: = Xst;
Space: = False;
for i: = 1 to Length (Res) do if Res [i] = '' then
begin l: = i; Space: = True end; {del spaces}
if Space then Res: = Copy (Res, l +1, Length (Res)-l);
{Sp: = 0;
for i: = 1 to Length (Res) do begin
if Res [i] = '' then inc (sp);
end;
if (X> = 0) and (sp = 0) then Res: = '' + Res;}
if X> = 0 then Res: = '' + Res;
DelZero: = Res;
end;
procedure Gosub9000;
var PE, PEint: real;
PC, PD: integer;
MID, RIGHT: string;
begin
PC: = round (int (PB/100));
P_str :='';
if PC = 0 then write ('') else write (Copy (P_str, 1, PC)); {LEFT $ (P $, PC)}
PC: = PB - 100 * PC;
PD: = round (int (PC/10));
PC: = PC - 10 * PD;
if PD = 0 then PD: = 1;
if PA <0 then P_str: = P_str +'-';
PE: = abs (PA); {A ^ X = EXP (X * LN (A))}
PE: = PE + 5 * EXP ((-1-PC) * LN (10)); {PE: = PE + 5 * 10 ^ (-1-PC)}
if PE> = EXP (PD * LN (10)) then begin write (PA); Exit end; {PE> = 10 ^ PD}
{Str (PE: 13:10, PE_str); {Copy (Str, 1, N); Left}
PEint: = int (PE);
PE_str: = DelZero (PEint);
MID: = Copy (PE_str, 2, PD); {MID $ (PE_str, 2, PD)}
P_str: = P_str + MID;
{PRINT RIGHT $ (P $, PD +1)}
RIGHT: = Copy (P_str, Length (P_str) - (PD +1) +1, PD +1);
GotoXY (WhereX +3, WhereY);
write (RIGHT); {RIGHT $ (P $, PD +1) Copy (Astr, Length (Astr)-N +1, N); Right}
if PC = 0 then Exit;
write ('.');
PE: = int ((PE-int (PE)) * EXP (PC * LN (10)));
P_str: = '000000000 ';
PE_str: = DelZero (PE);
{PE_str: = KillZero (PE_Str);}
{P_str: = P_str + Copy (KillZero (PE_str), 2, PC);}
MID: = Copy (PE_str, 2, PC);
P_str: = P_str + MID;
RIGHT: = Copy (P_str, Length (P_str)-PC +1, PC); {RIGHT (P $, PC)}
write (RIGHT, '');
end;
procedure Gosub3000;
begin
write ('Bazis Znachenie');
for j: = 1 to N +3 do write ('X', j, '');
writeln;
PB: = 122;
for i: = 1 to ML do begin
if i = M1 then write ('tselev func');
if i = M2 then write ('iskust func');
if (i <> M1) and (i <> M2) then begin write ('', i, ''); PA: = A [i, 0]; Gosub9000 end;
for j: = 0 to N0 do begin
PA: = A [i, j];
Gosub9000;
end;
writeln ('');
end;
write ('');
end;
procedure Gosub3500;
begin
If L = 1 then writeln ('ETAP 1 vsyo esho prodolzhaetsya');
PB: = 122;
for j: = 1 to N0 do write ('C', j, '');
writeln;
for j: = 1 to N0 do begin PA: = C [j]; Gosub9000 end;
writeln;
if SS <> 1 then writeln ('X', S, 'Vhodit B, X', BS [R], 'v uslovii', R, 'vyveden iz bazisa');
writeln ('Bazis Znachenie Obrashenie Bazisa');
if SS = 1 then write ('');
{Write ('A'iS');}
for i: = 1 to ML do begin
if i = M1 then write ('Reshenie dlya tselevoy functii');
if i = M2 then write ('Reshenie dlya iskustven functii');
if (i <> M1) and (i <> M2) then write ('', BS [i]);
for j: = 0 to M do begin
PA: = B [i, j];
Gosub9000;
end;
if SS <> 1 then begin PA: = V [i]; Gosub9000 end;
writeln ('');
end;
writeln ('');
end;
begin
clearkeybuf;
Init;
textbackground (0); textcolor (15);
clrscr; {promezhut tablitsa pri zz = +1 vyvod, -1 net}
writeln ('Reshenie zadachi lin prog-ya simplex-metodom');
{Write ('Vvedite zz'); readln (zz);} zz: = 1;
{Vvesti kol-vo vidov ogranicheniy i kolvo peremennyh}
{Write ('Vvedite cherez probel GC, EC, LC, N');
Readln (GC, EC, LC, N); {2, 0, 2, 2}
GC: = 0; EC: = 0; LC: = 3; N: = 2;
MM: = GC + EC; M: = MM + LC; MK: = GC + LC; N1: = MK + N;
P: = N1 + MM; M1: = M +1; M2: = M +2; N0: = N1;
{Vvesti koeff-ty dlya ogranicheniy i tselevoy functii}
{Matriza: vvodit stroku matrizy cherez probel, v konze stroki divss Enter}
{Writeln ('Input matrix', M1, 'x', N);
for i: = 1 to M1 do begin
for j: = 1 to N do read (A [i, j]);
readln;
end;}
A [1,1]: = 1; A [1,2]: =- 2; A [2,1]: = 2; A [2,2]: =- 1; A [3,1]: = 1; A [3,2]: = 1;
A [4,1]: =- 3; A [4,2]: = 1; {A [5,1]: = 0; A [5,2]: = 0;}
{Vyvod matrix na ekran}
writeln ('Matrix', M1, 'x', N);
for i: = 1 to M1 do begin
for j: = 1 to N do write (A [i, j], '');
writeln;
end;
cc: = 0;
{Zadat oslablennye, iskustvenye peremennye, pometit bazis i vvesti
peremennye v nulevoi stolbez}
writeln ('Zadaite oslablennye, iskustvennye peremennye'); {10, 5, 20, 20}
if GC <> 0 then begin
for i: = 1 to GC do begin {1 2}
A [i, N +1]: =- 1; A [i, N1 + i]: = 1; B [M2, i]: =- 1;
B [i, i]: = 1; A [M2, N1 + i]: = 1; BS [i]: = N1 + i;
write ('?'); read (A [i, 0]); B [i, 0]: = A [i, 0]
{If i = 1 then A [i, 0]: = 10;
if i = 2 then A [i, 0]: = 5;}
{Inc (cc)}
end
end;
if EC <> 0 then begin
for i: = GC +1 to MM do begin
A [i, N1 + i]: = 1; B [i, i]: = 1; A [M2, N1 + i]: = 1;
BS [i]: = N1 + i; B [M2, i]: =- 1; write ('?'); Read (A [i, 0]);
B [i, 0]: = A [i, 0]
{Inc (cc);}
end;
end;
if LC <> 0 then begin
for i: = MM +1 to M do begin {3 4}
A [i, N + i-EC]: = 1; B [i, i]: = 1; BS [i]: = N + i-EC; write ('?'); Read (A [i, 0 ]);
B [i, 0]: = A [i, 0]
{If i = 3 then A [i, 0]: = 20;
if i = 4 then A [i, 0]: = 20;}
{Inc (cc);}
end;
end;
if MM = 0 then writeln ('Otsutstvuet ETAP 1 resheniya zadachi');
{Writeln (cc);}
{Zadat iskustvenuyu function for ETAP 1}
L: = 1; N0: = P; {N0 yavlyaetsya nomerom nuzhnogo stolbza}
for i: = 1 to MM do B [M2, 0]: = B [M2, 0] - B [i, 0];
ML: = M1 + L; {ML = M +2 dlya ETAPA 1; ML = M +1 dlya ETAPA 2}
if zz> = 0 then writeln ('Pervonachalnaya tabliza');
Gosub3000;
{Repeat until keydivssed;}
{Vyhod iz progi}
{Pometit nebazisnye peremennye, NB [j] = 0, esli j-nebazisnaya peremennaya}
for i: = 1 to M do NB [BS [i]]: = 1;
Zero: = 0.00000001; NILL: = 1E-20;
{Exit; {Halt (0)}
{Naiti naimenshiy koef-t v stroke zelevoy functii, te stroku ML}
500: MIN: =-Zero; S: = 0; PV: = 0; ML: = M1 + L;
for j: = 1 to N0 do begin
C [j]: = 0;
if NB [j] <> 1 then begin
{Vychislit C [j]}
for i: = 1 to M do C [j]: = C [j] + B [ML, i] * A [i, j];
C [j]: = C [j] + A [ML, j];
if C [j] <MIN then begin MIN: = C [j]; S: = j end
end
end;
{Esli S = 0, to vse koef-ty polozhitelny i minimum naiden}
if S = 0 then goto 1900;
{Naiti stroku peremennyh, kotoruyu sleduet iskluchit iz bazisa
po usloviyu minimuma BI / A '[iS]}
MIN: = 1E20; R: = 0;
{Vychislit A '[iS] i pomestit v stolbez V}
for i: = 1 to M1 do begin
V [i]: = 0;
for k: = 1 to M1 do V [i]: = V [i] + B [i, k] * A [k, s]
end;
V [ML]: = C [S];
for i: = 1 to M do begin
if V [i] <= Zero then Continue;
k: = 0;
Zikl:
RT: = B [i, k] / V [i];
DF: = RT-MIN;
if DF <0 then begin
R: = i;
MIN: = B [i, 0] / V [i];
Continue
end;
if DF <> 0 then Continue;
k: = k +1;
MIN: = B [R, k] / V [R];
goto Zikl
end; {NEXT i}
{Esli R = 0, to imeet mesto reshenie bez ogranicheniy}
if R = 0 then goto 1800;
if zz> = 0 then Gosub3500;
Repeat Until keydivssed; {pervoe reshenie}
{Obnovit obratnyi i simplex-mnozhiteli}
PV: = V [R];
for j: = 0 to M1 do B [R, j]: = Round (B [R, j] / PV);
{Perenaznachit B povtorno pometit bazisnye i nebazisnye peremennye}
NB [BS [R]]: = 0; NB [S]: = 1; BS [R]: = S; NI: = NI +1;
Goto 500;
1800: writeln ('Peremennaya "S" ne imeet ogranicheniy');
Gosub3500; readkey;
Goto 2500;
1900: if L = 0 then Goto 2000;
{Dlya ETAPA 2 eta tochka yavl-sya minimumom. Esli my nahodimsya na ETAPE 1,
to pereiti k ETAPU 2, proverit, chto W stalo ravno 0}
if abs (A [ML, 0])> = 1E-08 then Goto 1960;
writeln ('ETAP 1 uspeshno zavershon');
L: = 0; N0: = N1; {Zadat L i nomer stolbza dlya ETAPA 2}
Goto 500;
1960: writeln ('Ogranicheniya ne imeyut dopustimogo resheniya');
writeln ('summa iskustvennyh peremennyh ravna',-B [ML, 0]);
Gosub3500;
2000: writeln ('Okonchatelnoe reshenie');
writeln ('Ogranichenie Bazis Znachenie');
PB: = 144;
for i: = 1 to M do begin
SL [BS [i]]: = B [i, 0];
write ('', i, '', BS [i], '');
PA: = B [i, 0];
Gosub9000;
writeln ('');
end;
writeln ('Minimum functii Z raven',-B [M1, 0]);
writeln ('Ogranichenie Sostoyanie Dopolnitelnye peremennye');
for i: = 1 to M do begin
Dop: = False;
write ('', i, '');
if (i> GC) and (i <= MM) then begin write ('Uravnenie ne resheno'); Continue end;
if NB [N + i] = 1 then begin write ('dopoln.perem.'); Dop: = True end;
PA: = SL [N + i];
Gosub9000;
write (''); {Continue;}
if not Dop then begin gotoXY (whereX-8, WhereY); writeln ('Ogranichenie 0') end else writeln;
end; writeln;
SS: = 1;
Gosub3500;
2500: writeln ('The End.');
Clearkeybuf;
Repeat until keydivssed
end.
Блок-схема
(Примітка: Якщо ММ = 0,
то отсутствуетЕТАП 1)
(Прімецаніе: Початок рішення)
Висновок
Даний курсовий проект був першим, необхідним для закріплення навичок в умінні програмувати. Тут були закладені основи математичних методів розв'язання задач. Майбутньою спеціалізацією курсового проекту було розробка програми на мові TURBO PASCAL. Тому більшу увагу приділялася наступним розділам:
· Основи математичних методів та їх застосування;
· Рішення задач за допомогою покращеного симплекс - методу;
· Основи програмування (мова Turbo Pascal).
Користувачеві пропонується ввести розрахункові дані, щоб отримати конкретні характеристики.
Програма розроблена на мові Turbo Pascal 7.0, що передбачає мінімальні системні вимоги для роботи з нею.
Список літератури
1. Акулич І.Л. Матеіатіческое програмування в прикладах і завданнях: Навч. Посібник для студ. Вузів. - М.: Вищ. Шк., 1986.
2. Банді Б. Основи лінійного програмування / пров. з англ. Під ред. В.А. Волинського. - М.: Радіо і зв'язок, 1989.
3. Кузнєцов А.В., Сакович В.А., Холод Н.І. Вища математика: Математичне програмування. - Мінськ: Вища школа, 1994.
writeln ('Reshenie zadachi lin prog-ya simplex-metodom');
{Write ('Vvedite zz'); readln (zz);} zz: = 1;
{Vvesti kol-vo vidov ogranicheniy i kolvo peremennyh}
{Write ('Vvedite cherez probel GC, EC, LC, N');
Readln (GC, EC, LC, N); {2, 0, 2, 2}
GC: = 0; EC: = 0; LC: = 3; N: = 2;
MM: = GC + EC; M: = MM + LC; MK: = GC + LC; N1: = MK + N;
P: = N1 + MM; M1: = M +1; M2: = M +2; N0: = N1;
{Vvesti koeff-ty dlya ogranicheniy i tselevoy functii}
{Matriza: vvodit stroku matrizy cherez probel, v konze stroki divss Enter}
{Writeln ('Input matrix', M1, 'x', N);
for i: = 1 to M1 do begin
for j: = 1 to N do read (A [i, j]);
readln;
end;}
A [1,1]: = 1; A [1,2]: =- 2; A [2,1]: = 2; A [2,2]: =- 1; A [3,1]: = 1; A [3,2]: = 1;
A [4,1]: =- 3; A [4,2]: = 1; {A [5,1]: = 0; A [5,2]: = 0;}
{Vyvod matrix na ekran}
writeln ('Matrix', M1, 'x', N);
for i: = 1 to M1 do begin
for j: = 1 to N do write (A [i, j], '');
writeln;
end;
cc: = 0;
{Zadat oslablennye, iskustvenye peremennye, pometit bazis i vvesti
peremennye v nulevoi stolbez}
writeln ('Zadaite oslablennye, iskustvennye peremennye'); {10, 5, 20, 20}
if GC <> 0 then begin
for i: = 1 to GC do begin {1 2}
A [i, N +1]: =- 1; A [i, N1 + i]: = 1; B [M2, i]: =- 1;
B [i, i]: = 1; A [M2, N1 + i]: = 1; BS [i]: = N1 + i;
write ('?'); read (A [i, 0]); B [i, 0]: = A [i, 0]
{If i = 1 then A [i, 0]: = 10;
if i = 2 then A [i, 0]: = 5;}
{Inc (cc)}
end
end;
if EC <> 0 then begin
for i: = GC +1 to MM do begin
A [i, N1 + i]: = 1; B [i, i]: = 1; A [M2, N1 + i]: = 1;
BS [i]: = N1 + i; B [M2, i]: =- 1; write ('?'); Read (A [i, 0]);
B [i, 0]: = A [i, 0]
{Inc (cc);}
end;
end;
if LC <> 0 then begin
for i: = MM +1 to M do begin {3 4}
A [i, N + i-EC]: = 1; B [i, i]: = 1; BS [i]: = N + i-EC; write ('?'); Read (A [i, 0 ]);
B [i, 0]: = A [i, 0]
{If i = 3 then A [i, 0]: = 20;
if i = 4 then A [i, 0]: = 20;}
{Inc (cc);}
end;
end;
if MM = 0 then writeln ('Otsutstvuet ETAP 1 resheniya zadachi');
{Writeln (cc);}
{Zadat iskustvenuyu function for ETAP 1}
L: = 1; N0: = P; {N0 yavlyaetsya nomerom nuzhnogo stolbza}
for i: = 1 to MM do B [M2, 0]: = B [M2, 0] - B [i, 0];
ML: = M1 + L; {ML = M +2 dlya ETAPA 1; ML = M +1 dlya ETAPA 2}
if zz> = 0 then writeln ('Pervonachalnaya tabliza');
Gosub3000;
{Repeat until keydivssed;}
{Vyhod iz progi}
{Pometit nebazisnye peremennye, NB [j] = 0, esli j-nebazisnaya peremennaya}
for i: = 1 to M do NB [BS [i]]: = 1;
Zero: = 0.00000001; NILL: = 1E-20;
{Exit; {Halt (0)}
{Naiti naimenshiy koef-t v stroke zelevoy functii, te stroku ML}
500: MIN: =-Zero; S: = 0; PV: = 0; ML: = M1 + L;
for j: = 1 to N0 do begin
C [j]: = 0;
if NB [j] <> 1 then begin
{Vychislit C [j]}
for i: = 1 to M do C [j]: = C [j] + B [ML, i] * A [i, j];
C [j]: = C [j] + A [ML, j];
if C [j] <MIN then begin MIN: = C [j]; S: = j end
end
end;
{Esli S = 0, to vse koef-ty polozhitelny i minimum naiden}
if S = 0 then goto 1900;
{Naiti stroku peremennyh, kotoruyu sleduet iskluchit iz bazisa
po usloviyu minimuma BI / A '[iS]}
MIN: = 1E20; R: = 0;
{Vychislit A '[iS] i pomestit v stolbez V}
for i: = 1 to M1 do begin
V [i]: = 0;
for k: = 1 to M1 do V [i]: = V [i] + B [i, k] * A [k, s]
end;
V [ML]: = C [S];
for i: = 1 to M do begin
if V [i] <= Zero then Continue;
k: = 0;
Zikl:
RT: = B [i, k] / V [i];
DF: = RT-MIN;
if DF <0 then begin
R: = i;
MIN: = B [i, 0] / V [i];
Continue
end;
if DF <> 0 then Continue;
k: = k +1;
MIN: = B [R, k] / V [R];
goto Zikl
end; {NEXT i}
{Esli R = 0, to imeet mesto reshenie bez ogranicheniy}
if R = 0 then goto 1800;
if zz> = 0 then Gosub3500;
Repeat Until keydivssed; {pervoe reshenie}
{Obnovit obratnyi i simplex-mnozhiteli}
PV: = V [R];
for j: = 0 to M1 do B [R, j]: = Round (B [R, j] / PV);
{Perenaznachit B povtorno pometit bazisnye i nebazisnye peremennye}
NB [BS [R]]: = 0; NB [S]: = 1; BS [R]: = S; NI: = NI +1;
Goto 500;
1800: writeln ('Peremennaya "S" ne imeet ogranicheniy');
Gosub3500; readkey;
Goto 2500;
1900: if L = 0 then Goto 2000;
{Dlya ETAPA 2 eta tochka yavl-sya minimumom. Esli my nahodimsya na ETAPE 1,
to pereiti k ETAPU 2, proverit, chto W stalo ravno 0}
if abs (A [ML, 0])> = 1E-08 then Goto 1960;
writeln ('ETAP 1 uspeshno zavershon');
L: = 0; N0: = N1; {Zadat L i nomer stolbza dlya ETAPA 2}
Goto 500;
1960: writeln ('Ogranicheniya ne imeyut dopustimogo resheniya');
writeln ('summa iskustvennyh peremennyh ravna',-B [ML, 0]);
Gosub3500;
2000: writeln ('Okonchatelnoe reshenie');
writeln ('Ogranichenie Bazis Znachenie');
PB: = 144;
for i: = 1 to M do begin
SL [BS [i]]: = B [i, 0];
write ('', i, '', BS [i], '');
PA: = B [i, 0];
Gosub9000;
writeln ('');
end;
writeln ('Minimum functii Z raven',-B [M1, 0]);
writeln ('Ogranichenie Sostoyanie Dopolnitelnye peremennye');
for i: = 1 to M do begin
Dop: = False;
write ('', i, '');
if (i> GC) and (i <= MM) then begin write ('Uravnenie ne resheno'); Continue end;
if NB [N + i] = 1 then begin write ('dopoln.perem.'); Dop: = True end;
PA: = SL [N + i];
Gosub9000;
write (''); {Continue;}
if not Dop then begin gotoXY (whereX-8, WhereY); writeln ('Ogranichenie 0') end else writeln;
end; writeln;
SS: = 1;
Gosub3500;
2500: writeln ('The End.');
Clearkeybuf;
Repeat until keydivssed
end.
Блок-схема
початок |
GC, EC, LC, N |
Введення коеф-тів матриці |
(Примітка: Якщо ММ = 0,
то отсутствуетЕТАП 1)
Висновок первонач. таблиці |
(Прімецаніе: Початок рішення)
S = 0 R = 0 R = 0 |
ТАК |
НІ |
Виконується дана умова |
Висновок первонач. таблиці |
кінець |
Висновок
Даний курсовий проект був першим, необхідним для закріплення навичок в умінні програмувати. Тут були закладені основи математичних методів розв'язання задач. Майбутньою спеціалізацією курсового проекту було розробка програми на мові TURBO PASCAL. Тому більшу увагу приділялася наступним розділам:
· Основи математичних методів та їх застосування;
· Рішення задач за допомогою покращеного симплекс - методу;
· Основи програмування (мова Turbo Pascal).
Користувачеві пропонується ввести розрахункові дані, щоб отримати конкретні характеристики.
Програма розроблена на мові Turbo Pascal 7.0, що передбачає мінімальні системні вимоги для роботи з нею.
Список літератури
1. Акулич І.Л. Матеіатіческое програмування в прикладах і завданнях: Навч. Посібник для студ. Вузів. - М.: Вищ. Шк., 1986.
2. Банді Б. Основи лінійного програмування / пров. з англ. Під ред. В.А. Волинського. - М.: Радіо і зв'язок, 1989.
3. Кузнєцов А.В., Сакович В.А., Холод Н.І. Вища математика: Математичне програмування. - Мінськ: Вища школа, 1994.