Розв'язання екстремальних задач цілочисленого програмування геометричним методом

ЗМІСТ Вступ 2 Короткі теоретичні відомості 5 Опис роботи програми 6 Текст програми на мові програмування с++ 7 Приклад роботи програми 12 Висновки 13 Список використаної літератури 14 ВСТУП Екстремальними задачами людина цікавиться з античних часів. У Древній Греції вже давно (у всякому разі до VI століття до н.е.) знали про екстремальні властивості

кола і кулі: серед плоских фігур з однаковим периметром найбільшу площу має коло (рішення изопериметрической екстремальної задачі); куля має максимальний обсяг серед просторових фігур з однаковою площею поверхні (рішення изопіфанної екстремальної задачі). Історія зберегла легенду про наступну саму древню екстремальну задачу, відому як задача Дідони. Фінікійська царівна Дідона (IX століття до н.е.) вирішила організувати поселення на березі затоки, що сподобалося

їй, у Північній Африці. Вона умовила вождя місцевого племені віддати їй клаптик землі, який можна охопити волячою шкірою. Воїни Дідони розрізали шкіру на тонкі смужки, і Дідона охопила ременем, складеним з цих смужок, ділянку землі на березі затоки. Так виникло місто Карфаген. Задача Дідони складається у вказівці форми границі ділянки, що має задану довжину, при якій площа ділянки

максимальна. Якщо знати екстремальну властивість кола, то рішення виходить негайно: границя ділянки представляє частину окружності, що має задану довжину. Екстремальними задачами займалися багато античних учених (Евклід, Архімед, Аристотель і ін.). Відома наступна задача Евкліда (IV століття до н.е.): у заданий трикутник

ABC вписати паралелограм ADEF найбільшої площі. Неважко довести, що рішенням цієї задачі є паралелограм, вершини D, E, F якого поділяють відповідні сторони трикутника навпіл. До середини XX століття створилося враження, що теорія екстремальних задач досягла такого рівня, що дозволяє вирішити будь-яку екстремальну задачу, що виникає в науці і практиці. Останнє твердження більше відноситься до науки, ніж до практичних додатків, тому що до середини

XX століття математика мало використовувалася для рішення прикладних задач, а в основному знаходила різноманітні застосування в інших розділах природознавства. Ситуація стала помітно мінятися напередодні другої світової війни. В економіці і техніці стали виникати задачі, для рішення яких практичний досвід і здоровий глузд виявлялися вже недостатніми. Це було зв'язано зі збільшенням можливих варіантів вибору,

жорсткістю вимог до точності рішення, з обмеженнями на доступні ресурси. Людство стало усе енергійніше переходити від використання тільки природних процесів до створення штучних матеріалів, систем, процесів. Різко підвищився вплив його діяльності на навколишнє середовище. Усі ці та інші обставини поступово змушували більш науково підходити до рішення практичних задач. Науковий підхід припускає складання математичної моделі досліджуваного практичного явища чи процесу,

дослідження моделі відповідними математичними методами, складання алгоритмів рішення і реалізацію цих алгоритмів у виді програм для ЕОМ. У теорії екстремальних задач нові явища XX століття вперше були помічені радянським математиком Л.В. Канторовичем. У 30-і роки він консультував економістів деяких ленінградських заводів і зіштовхнувся з задачею про розкрій матеріалів. Економістів цікавило, як щонайкраще розрізати аркуші

фанери, щоб відходи були мінімальними. Л.В. Канторович показав, що ця задача і багато інших практичних задач можуть бути сформульовані у виді наступної екстремальної задачі: c1x1 + c2x2 + + cnxn ® max, a11x1 + a12x2 + + a1nxn £ b1 , a21x1 + a22x2 + + a2nxn £ b2 , . am1x1 + am2x2 + + amnxn £ bm , x1 ³ 0, x2 ³ 0, … , xn ³ 0. Головна особливість цієї задачі полягає в тому, що в

її умовах присутні нестрогі нерівності. Звичайно, з нерівностями вчені зустрічалися і раніше, і знаходили для кожного випадку спеціальні прийоми їхнього обліку. Л.В. Канторович першим чітко заявив, що нестрогі нерівності типові для більшості практичних задач і для їхнього обліку в математиці немає загальних ефективних методів. Він же запропонував кілька прийомів рішення нового класу екстремальних задач, але завершенню роботи

перешкодила друга світова війна. Заслуги Л.В. Канторовича по дослідженню нового класу екстремальних задач були відзначені Нобелівською премією по економіці, у якій задачі такого типу відіграють величезну роль. Після другої світової війни незалежно від Л.В. Канторовича до таких задач дійшов (1947 рік) американський математик Д. Данциг і запропонував ефективний метод їхнього рішення, відомий тепер як симплекс-метод.

З початку 50-х років новий розділ таких екстремальних задач став називатися лінійним програмуванням і став першим розділом сучасної теорії екстремальних задач, що відрізняється від класичної теорії екстремальних задач наявністю в ній методів рішення задач з нестрогими нерівностями і породжуваними останніми замкнутими множинами. Становленню лінійного програмування, його узагальненням і додаткам величезну допомогу зробило створення в середині 40-х років

XX століття електронних обчислювальних машин (ЕОМ). Справа в тім, що екстремальні задачі, що включають у свої умови нестрогі нерівності, рідко допускають рішення у формі, що до XX століття була широко поширена в математиці і широко використовується тепер в шкільній математиці. Мова йде про запис рішень у виді формул, що виражають шукані змінні через параметри задачі.

Найпростіші приклади - формули для площ трикутника, кола, для коренів квадратного рівняння, для точок мінімуму і максимуму квадратного тричлена і т.п. Такий "формульний тип рішення" математичних задач часто зручний для використання, а в найпростіших ситуаціях його знання для математика обов'язкове як таблиця множення. Його достоїнство заключається в глобальності: одержавши формулу один раз, її можна використовувати для одержання чисельної відповіді в будь-якій конкретній ситуації.

Формульне рішення володіє й істотним недоліком: надзвичайно вузький клас математичних задач, для рішення яких удається побудувати зручні формули. В останні роки за допомогою ЕОМ вчені істотно продвинулися в цій області і стали непотрібними численні таблиці формул. Тепер ЕОМ сама одержує формулу для рішення математичної задачі, якщо задача допускає формульне рішення. Однак уже давно відомо, що проблема побудови формул для рішення більшості математичних задач принципово

нерозв'язна. У зв'язку з цим з появою ЕОМ на перший план став виходити інший тип рішення математичних задач. Цей тип рішення був відомий ще И. Ньютонові, але використовувався в математиці не дуже часто. На відміну від формульного новий тип рішення призначався для одержання чисельної відповіді з кожною наперед заданою точністю для конкретних задач із заданими чисельними значеннями параметрів.

У дискретному програмуванні змінні (усі чи частина) задачі можуть приймати лише скінчене число значень, можуть бути, наприклад, лише цілими числами (задача цілочисельного програмування). Одним з прикладів задач цілочисельного програмування може служити так звана “задача про заплічник”: є m різноманітних предметів, відома вага кожного предмета та його вартість. Потрібно визначити, які предмети потрібно покласти в заплічник, щоб загальна маса не перевищувала заданої

границі, а загальна вартість була максимальною. Виділення з теорії екстремальних задач спеціальних частин дозволяє створювати для них ефективні методи, що враховують специфіку цих задач. У даному випадку автором розроблена програма для знаходження розв’язку задачі цілочисельного програмування за допомогою геометричного (графічного) методу, реалізована для ЕОМ типу IBM PC на мові програмування С++. Короткі теоретичні відомості

За допомогою геометричного методу практично можна рішити досить вузький клас задач, оскільки зазвичай даний метод доцільно використовувати лише для площини розв’язків, що передбачає наявність не більше ніж двох змінних (графічний метод). Однак із застосуванням сучасних комп’ютерних технологій не є неможливим і випадок наявності більше, ніж двох змінних, правда, лише при знаходженні оптимального та досить швидкого алгоритму. В цілому задача цілочисленого програмування, призначена для розв’язання

за допомогою геометричного методу, має слідуючий вигляд: c1x1 + c2x2 ® extr, a11x1 + a12x2 £ b1 , a21x1 + a22x2 £ b2 , . am1x1 + am2x2 £ bm , x1 ³ 0, x2 ³ 0. х1, х2 – цілі числа. У загальному випадку задача лінійного програмування при застосуванні геометричного методу, поділяється на такі наступні кроки: 1) По заданим рівнянням (нерівностям) будуються прямі. 2) Знаходяться напівплощини для усіх ліній. 3) Будується многокутник розв’язків.

4) Будується напрямляючий вектор С (с1, с2). 5) Будується пряма с1х1+с2х2=h, котра проходить через многокутник розв’язків. 6) Рухаючи пряму у напрямку вектору С, або знаходять точку екстремуму, або встановлюють необмежежність зверху функції. 7) Визначаються координати точки екстремуму і обчислюється значення цільової функції у цій точці. При знаходженні розв’язку задачі цілочисельного програмування усі вищевказані пункти залишаються практично

без змін, за одним виключенням: якщо координати точки екстремуму є цілими числами, то задача розв’язана. Якщо ж серед них хоча б одне число виявиться дробовим, то поступають слідуючим чином: із многокутника розв’язків вибирають многокутник цілочисельних розв’язків, який містить тільки цілі числа у якості вершин. Після цього цільову функцію знову рухають на екстремум. Таким чином знаходиться цілочисельний розв’язок задачі.

Опис роботи програми При запуску програми перше, що потрібно ввести – це кількість обмежень та коефіцієнти цільової функції. Після цього потрібно ввести коефіцієнти при невідомих нерівностей обмежень та вид обмеження (більше-рівно або менше-рівно). Після цього програма переключається в графічний режим. Усі обчислення проводяться у графічному режимі роботи екрану, причому із застосуванням графіки BGI для DOS. Завдяки цьому програма має досить компактний виконуваний код (близько 131

кб. увесь двійковий код разом з модулем графіки BGI). Принцип обчислень слідуючий: по заданим рівнянням (нерівностям) будуються прямі та виводяться на екран; знаходяться напівплощини для усіх ліній та формується многокутник розв’язків. Якщо такий сформувати не вдається, програма виводить повідомлення про помилку та завершає свою роботу. Будується напрямляючий вектор С (с1, с2). Будується пряма с1х1+с2х2=h, котра проходить через многокутник

розв’язків. Вибирається довільним чином одна із точок перетину прямих, котра потрапляє у многокутник роз’язків та знаходиться значення цільової функції у цій точці. Потім цільова функція рухається у напрямку, заданому вектором цільової функції до тих пір, доки не буде досягнений кінець многокутника розв’язків, або доти, доки не виявиться, що пройдені усі точки, а кінець многокутника розв’язків не досягнений. У такому випадку або виводиться значення цільової функції

у даній точці, або видається на екран повідомлення про помилку. Перед тим, як видати результат, програма перевіряє координати вказаної точки на предмет знаходження серед них дробових чисел. якщо координати точки екстремуму є цілими числами, то задача розв’язана. Якщо ж серед них хоча б одне число виявиться дробовим, то програма поступає слідуючим чином: границя області розв’язків оконтурюється зсередини ламаною, яка проходить

тільки через ті точки, координатами яких є цілі числа і процес пошуку продовжується у порядку, вказаному вище, з тією відмінністю, що в такому випадку розв’язок майже завжди буде, за тим єдиним виключенням, коли не вдається побудувати контурну ламану (у такому випадку програма не має розв’язку з цілочисельними координатами). ТЕКСТ ПРОГРАМИ НА МОВІ ПРОГРАМУВАННЯ С++ // Uses headers #include <dos.h> #include<stdio.h>

#include<stdlib.h> #include<conio.h> #include<iostream.h> #include<string.h> #include<graphics.h> // Headers of used procedures void clut(); void coords(); void beep(); void datainput(); void scanmatrix(); void calcpoints(); int min(int a,int b); // List of variables struct point{long double x;long double y;}a[16],b[150]; int gd=VGA,gm=VGAHI,i,j,k,m,n,s_x,s_y,x,y; int numpoint=0,dots,dotcount=0; long double f[16],result; int poly[8],scale=20; char

str[40],temp[10],sign[15]; char mx[200][200]; char p[16][8] = {//matrica nalozhenija {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80 }, {0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x01 }, {0x04,0x08,0x10,0x20,0x40,0x80,0x01,0x02 }, {0x08,0x10,0x20,0x40,0x80,0x01,0x02,0x04 }, {0x10,0x20,0x40,0x80,0x01,0x02,0x04,0x08 }, {0x20,0x40,0x80,0x01,0x02,0x04,0x08,0x10 }, {0x40,0x80,0x01,0x02,0x04,0x08,0x10,0x20 }, {0x80,0x01,0x02,0x04,0x08,0x10,0x20,0x40 }, {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01 }, {0x40,0x20,0x10,0x08,0x04,0x02,0x01,0x80 }, {0x20,0x10,0x08,0x04,0x02,0x01,0x80,0x40 }, {0x10,0x08,0x04,0x02,0x01,0x80,0x40,0x20 }, {0x08,0x04,0x02,0x01,0x80,0x40,0x20,0x10

}, {0x04,0x02,0x01,0x80,0x40,0x20,0x10,0x08 }, {0x02,0x01,0x80,0x40,0x20,0x10,0x08,0x04 }, {0x01,0x80,0x40,0x20,0x10,0x08,0x04,0x02 } }; // Main part void main(){ datainput(); initgraph(&gd,&gm,""); clut();coords(); for(i=0;i<n;i++){setcolor(i+1);// Lines output s_x=f[i]/a[i].x*scale;s_y=f[i]/a[i].y*sc ale; if(s_x<0||s_y<0){if(s_x<0&& amp;s_y<0)continue; int margin;margin=320/min(abs(s_x),abs(s_y)) ; if(s_y<0) line(320+s_x,240,320+s_x+s_x*margin,240+ s_y*margin); if(s_x<0) line(320,240-s_y,320-s_x*margin,240-s_y- s_y*margin); }else{ if(a[i].x)s_x=320+f[i]/a[i].

x*scale;else s_x=320; if(a[i].y)s_y=240-f[i]/a[i].y*scale;else s_y=240; if(a[i].x&&a[i].y)line(s_x,240,3 20,s_y); else if(a[i].x)line(s_x,240,s_x,0);else line(320,s_y,640,s_y); }; };coords();scanmatrix(); getch();closegraph(); calcpoints(); } // // Graphical procedures void clut(){ // Output colors for lines and formules for(i=0;i<n;i++){setcolor(i+1); rectangle(0,i*10,10,(i+1)*10-1); setfillstyle(SOLID_FILL,i+1); floodfill(5,i*10+1,i+1); itoa(i+1,str,10);strcat(str,": ");

itoa(a[i].x,temp,10); strcat(str,temp);strcat(str,"X + "); itoa(a[i].y,temp,10); strcat(str,temp);strcat(str,"Y = "); itoa(f[i],temp,10);strcat(str,temp); outtextxy(15,i*10+1,str); }; setcolor(15);outtextxy(15,n*10,"X > 0, Y > 0"); }; void coords(){ settextstyle(DEFAULT_FONT,HORIZ_DIR,2); setcolor(14);outtextxy(330,5,"Y&quo t;); outtextxy(620,212,"

X");setcolo r(9); line(320,0,320,480);line(0,240,640,240); line(315,10,320,0);line(325,10,320,0); line(634,235,639,240);line(634,245,639,2 40); for(i=1;i<230/scale;i++){ line(319,240-i*scale,321,240-i*scale); line(319,240+i*scale,321,240+i*scale);}; for(i=1;i<320/scale;i++){ line(320+i*scale,239,320+i*scale,241); line(320-i*scale,239,320-i*scale,241);}; settextstyle(DEFAULT_FONT,HORIZ_DIR,1); }; // Other helpfull functions void beep(){sound(440);delay(100);nosound();} ; void datainput(){

directvideo=1;textcolor(14); textbackground(1);clrscr(); for(i=2;i<=24;i++){gotoxy(1,i); putch(0xb3);gotoxy(80,i);putch(0xb3);}; for(i=2;i<=79;i++){gotoxy(i,1); putch(0xc4);gotoxy(i,25);putch(0xc4);}; gotoxy(1,1);putch(0xda);gotoxy(1,25);put ch(0xc0); gotoxy(80,1);putch(0xbf);gotoxy(80,25); asm{mov ah,15;int 16;mov ah,10;mov al,0xd9;int 16;}; gotoxy(2,2);window(2,2,79,24); cout<<"Введiть число обмежень: ";cin>>n; if(n>15)n=15;if(n<0)n=2; gotoxy(1,2);cout<<

"Задайте цiльову функцiю: "; gotoxy(1,3);cout<<"X=";c in>>a[n].x; gotoxy(10,3);cout<<"Y="; cin>>a[n].y; gotoxy(20,3);cout<<"Max або Min - > або <: "; k=wherex();sign[n]=getche(); while(sign[n]!='>'&&sign[n]!= '<'){ beep();gotoxy(k,3);cout<<" ";gotoxy(k,3);sign[i]=getche(); } cout<<

" "; // VVod dannix for(i=0;i<n;i++){ j=wherey();gotoxy(1,j); cout<<"X"<<i+1< <"=";cin>>a[i].x;goto xy(10,j); cout<<"Y"<<i+1< <"=";cin>>a[i].y;goto xy(20,j); cout<<"Введiть < або >: "; k=wherex();sign[i]=getche(); while(sign[i]!='>'&&sign[i]!= '<'){ beep();gotoxy(k,j);cout<<" ";gotoxy(k,j);sign[i]=getche(); } gotoxy(40,j);cout<

<"F="; cin>>f[i]; }gotoxy(1,j+1);cout<<"Натиснi ть ENTER.";while(getch()!=13)beep(); // Konetz vvoda. window(1,1,80,25); }; // Matrix scanning procedure //(Opredelenie oblasti perekrutija) void scanmatrix(){ int res,flag=0;dotcount=0; for(x=0;x<200;x++)for(y=0;y<200;y+ +){mx[x][y]=0; for(k=0;k<n;k++){res=a[k].x*x+a[k].y* y; if(sign[k]=='<'&&res<=f[k] )mx[x][y]=mx[x][y]+1;

if(sign[k]=='>'&&res>=f[k] )mx[x][y]=mx[x][y]+1; };setcolor(7); if(mx[x][y]<n&&flag)continue; flag=0; if(mx[x][y]==n){dotcount++;s_x=x;s_y=y;f lag=1; setcolor(14);circle(320+x*scale,240-y*sc ale,2); }; // itoa(int(mx[x][y]),temp,10); outtextxy(x*8+20,472-y*8,temp); }; // Rasstavlenie krajnix tochek dots=0;result=a[n].x*s_x+a[n].y*s_y; for(x=0;x<30;x++)for(y=0;y<30;y++) { res=0;setcolor(15); if(mx[x][y]==n){dots++; if(sign[n]=='>')if(result<=(a[n].x *x+a[n].y*y)){

result=a[n].x*x+a[n].y*y;s_x=x;s_y=y; }; if(sign[n]=='<')if(result>=(a[n].x *x+a[n].y*y)){ result=a[n].x*x+a[n].y*y;s_x=x;s_y=y; }; for(i=-1;i<2;i++)for(j=-1;j<2;j++) if(i||j)if(mx[x+i][y+j]<n){res++; if(res>1)circle(320+x*scale,240-y*sca le,2); if(dots>dotcount){x=30;y=30;}; }; }; };f[n]=result; // Vuvod na ekran maksimyma/minimyma f-cij i koordinat tochki if(sign[n]=='>')strcpy(str,"F(ma x) = "); if(sign[n]=='<')strcpy(str,"

F(mi n) = "); itoa(f[n],temp,10); strcat(str,temp);outtextxy(15,(n+1)*10,s tr); if(sign[n]=='>')strcpy(str,"Max = ("); if(sign[n]=='<')strcpy(str,"Min = ("); itoa(int(s_x),temp,10);strcat(str,temp); strcat(str,".");itoa(int(s_y), temp,10);strcat(str,temp); strcat(str,")");outtextxy(15,( n+2)*10,str); // Risovanie linii celevoj f-cii if(a[n].x)s_x=320+f[n]/a[n].x*scale;else s_x=320; if(a[n].y)s_y=240-f[n]/a[n].

y*scale;else s_y=240; if(a[n].x&&a[n].y)line(s_x,240,3 20,s_y); else if(a[n].y)line(s_x,240,s_x,0);else line(320,s_y,640,s_y); //Risovanie napravlyauchogo vektora celevoj f-cij setlinestyle(DOTTED_LINE,127,15); line(320,240,320+f[n]*scale/a[n].y,240-f [n]*scale/a[n].x); setlinestyle(SOLID_LINE,255,15); }; int min(int a,int b){if(a<b)b=a;return b;}; // Najti vse tochki peresechenija linij void calcpoints(){ k=0;gotoxy(1,1); for(i=0;i<n-1;i++)for(j=i+1;j<n;j+ +){ result=a[i].x*a[j].y-a[i].y*a[j].x; if(result){

b[k].x=f[i]*a[j].y-f[j]*a[i].x; b[k].y=a[i].x*f[j]-a[i].y*f[i]; if(b[k].x>=0&&b[k].y>=0)k+ +; }; }; numpoint=k; }; // End of program. Приклад роботи програми Розглянемо роботу програми на прикладі розв’язання простої задачі. Нехай ми маємо слідуючу задачу: f = 2x1 + x2 ® max 2x1 + 3x2 &#163; 12 4x1 + x2 &#179; 10 x1, x2 &#179; 0 x1, x2 – цілі числа Після вводу в програму усіх даних на екрані отримуємо наступний

малюнок: Кожна лінія на малюнку відображена своїм кольором, причому у верхньому лівому кутку показано, лінія якого кольору відображає кожну нерівність умови. Також там вказується значення цільової функції у точці екстремуму та координати цієї точки. Лінія рівняння цільової функції у точці екстремуму та направляючий вектор також показані на цьому ж малюнку, але на відміну від усіх інших ліній вони відображаються кольором,

інверсним до фонового кольору екрану. Таким чином дана програма не лише виводить результати обчислень, але і дає змогу наочно побачити результати у графічній формі, що позбавляє необхідності для перевірки правильності результатів малювати усі лінії нерівностей, (а їх може бути і кілька десятків, і кілька сотень) що називається, “від руки”. Дана програма дозволяє вводити до 16230 нерівностей, але у зв’язку з тим, що кольороподільна здатність

монітора для BGI-модулів обмежена 16 кольорами, то для більшої наглядності кількість нерівностей, які можна вводити, також була обмежена автором до 16, чого вистачає для більшості задач. Висновки Розробляючи дану програму, автор мав на меті створити досить компактний та швидкий алгоритм розв’язку задачі цілочисельного програмування геометричним методом за допомогою виключно програмних засобів, без втручання людини в процес розрахунків, що обов’язково мало б місце, якщо б дану задачу

розв’язувати класичними методами (див. розділ “КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ”). Набагато спростив роботу над програмою той факт, що при дискретному програмуванні змінні (усі чи частина) задачі можуть приймати лише скінчене число значень, тобто можуть бути лише цілими числами. Звичайно, дана задача допускає і простіший шлях розв’язку, якщо просто задати двовимірний масив та просканувати почергово усі його точки на предмет знаходження точки, у якій цільова функція досягяє

свого екстремуму. Але такий алгоритм, на думку автора, є недопустимо ресурсоємним, адже для області розмірності (m,n) потрібно виділити m*n чарунок пам’яті. Крім того, подібний шлях розв’язання задачі вимагає багато часу. Тому автор зупинився на варіанті, описаному вище, як найбільш оптимальному як з точки зору швидкодії та ресурсоємності, так з точки зору порівняно малого об’єму програмного та двійкового коду.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 1. Абрамов С.А Гнездилов Г. Г. Задачи по программированию. М.: Наука, 1988. 2. Акулич. И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. 3. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. 4. Кнут. Д. Искусство программирования.

Том 3. М.: Мир, 1978.