[ Pobierz całość w formacie PDF ]
//-->Badania Operacyjnekierunek Informatyka, studia II stopnia11.11.1.1Programowanie linioweFunkcje wielu zmiennychSformułowanie zadaniaOgólnym zadaniem programowania liniowegonazywamy zadanie postaci:J(u)=c1u1+...+cnun→min.uk≥0,k∈Ia1,1u1+...+a1,nun≤b1...am,1u1+...+am,nun≤bm,(3)(1)(2)gdzieu= (u1, ..., un)∈Rn, natomiastcj,ai,j,bi,i= 1,..., s, j= 1,..., n,sa danymi˛liczbami rzeczywistymi, przy czym nie wszystkie liczbycji nie wszystkie liczbyaijsa˛równe zero,I⊂ {1,..., n}jest ustalonym zbiorem indeksów; mozliwe sa tutaj przypadki:˛˙I=∅,I={1,..., n}, m=s, m= 0.Symbolemx, yoznacza´ bedziemy iloczyn skalarny wektorówx= (x1, ..., xn),y=c ˛(y1, ..., yn),t.zn.x, y=ni=1am+1,1u1+...+am+1,nun=bm+1...a u1+...+a un=bss,1s,nxiyi, natomiast zapisx≥y,1gdziex= (x1, ..., xn),y= (y1, ..., yn),bedzie oznaczał, ze˛˙xi≥yi, i= 1,..., n.Powyzsze zadanie mozemy zapisa´ nastepujaco:c˛˛˙˙J(u)=c, u→min.u∈U={u= (u1, ..., un)∈Rn;ui≥dlai∈I, Au≤b, Au=b}A=a1,1...am,1... a1,n... am+1,nam+1,1...., A=.....as,1... as,n... am,n1m+1bb..b=., b=....msbb,(4)gdzieKazdy punktu∈Unazywamypunktem dopuszczalnymzadania (4). Punktu∗∈U˙nazywamyrozwiazaniemzadania (4), gdy˛J(u∗)≤J(u)dla dowolnegou∈U.Kanonicznym zadaniem programowania liniowegonazywamy zadanie postaciJ(u) =c, u→min.,u∈U={u= (u1, ..., un)∈Rn;u≥,Au=b}Podstawowym zadaniem programowania liniowegonazywamy zadanie postaciJ(u) =c, u→min.,u∈U={u= (u1, ..., un)∈Rn;u≥,Au≤b}(5)gdzieA∈Rm×n,b∈Rm.(6)gdzieAibsa takie, jak wyzej.˛˙Zadanie 1.Zapisa´ nastepujace zadanie w postaci zadania programowania liniowego.c˛˛2Producent odziezy powinien okre´li´, ile kurtek i płaszczy nalezy wyprodukowa´ tak, abys cc˙˙zysk osiagniety z ich sprzedazy był maksymalny. Do produkcji wykorzystywany jest jeden˛ ˛˙rodzaj tkaniny. Producent posiada150m2tej tkaniny. Zgodnie z zamówieniami nalezy˙wyprodukowa´ co najmniej20kurtek i co najwyzej10płaszczy. Do produkcji jednejc˙kurtki i jednego płaszcza potrzeba odpowiednio2, 5m2i4m2tkaniny. Przy sprzedazy˙jednej kurtki producent osiaga zysk50zł, płaszcza -60zł.˛Zadanie 2.Zapisa´ nastepujace zadanie w postaci zadania programowania liniowego.c˛˛Wytwórca mebli powinien okre´li´, ile stołów, krzeseł, biurek i szaf nalezy wypro-s c˙dukowa´, by zysk z ich sprzedazy był maksymalny. Do produkcji wykorzystywane sa˛ dwac˙typy desek. Wytwórca posiada1500m desek I typu i1000m - desek II typu oraz dysponujekapitałem860godzin roboczych na wykonanie zaplanowanej produkcji. Ze złozonych za-˙mówien i mozliwo´ci magazynowych wynika, ze nalezy wyprodukowa´ co najmniej40sc´˙˙˙stołów, co najmniej130krzeseł, co najmniej30biurek i nie wiecej niz10szaf. Do˛˙produkcji kazdego stołu, krzesła, biurka i szafy potrzeba odpowiednio5, 1, 9, 12m desek I˙typu i2, 3, 4, 1m desek II typu. Na wykonanie stołu potrzeba3godzin pracy, krzesła -2godzin, biurka -5godzin, szafy -10godzin. Ze sprzedazy jednego stołu, krzesła, biurka i˙szafy wytwórca osiaga zysk odpowiednio50, 20, 60i40zł.˛Zadanie 3.Zapisa´ nastepujace zadanie w postaci zadania programowania liniowego.c˛˛Zadaniem dietetyka jest opracowanie składu porannej owsianki tak, aby zawierała onaniezbedne dzienne zapotrzebowanie organizmu na okre´lone składniki odzywcze i jednocze´niess˛˙´była mozliwie najtansza. Dietetyk ma dyspozycji płatki dwóch rodzajów: I i II. Sniadanie´ ˛˙powinno zawiera´ co najmniej 1 mg witaminy B1,12mg zelaza i mie´ warto´´ energety-ccsc˙czna˛ równa˛360kcal.100g płatków I rodzaju zawiera1, 2mg witaminy B1,12mg zelaza i˙ma warto´´ energetyczna˛ równa˛358kcal, natomiast100g płatków II rodzaju zawiera1, 5scscmg witaminy B1,10mg zelaza i ma warto´´ energetyczna˛ równa˛390kcal. Ponadto100˙g płatków I rodzaju kosztuje32gr, a100g płatków II rodzaju -36gr.Zadanie 4.Zapisa´ nastepujace zadanie w postaci zadania programowania liniowego.c˛˛Producent farb musi okre´li´, ile litrów farby białej, zielonej, niebieskiej i czerwonej powiniens c3wyprodukowa´, aby zysk osiagniety ze sprzedazy był maksymalny. Do produkcji wykorzysty-c˛ ˛˙wane sa˛ trzy surowce: A, B i C. Producent posiada230litrów surowca A,200litrów -surowca B i170litrów - surowca C oraz dysponuje kapitałem160godzin roboczych. Zprzyjetych zamówie´ wynika, ze nalezy wyprodukowa´ co najmniej125litrów farby białej,nc˛˙˙co najmniej135litrów - farby zielonej, co najwyzej205litrów - farby niebieskiej i nie˙mniej niz175litrów - farby czerwonej. Ilo´ci poszczególnych surowców potrzebnych dos˙wyprodukowania1litra kazdej farby przedstawione sa˛ w nastepujacej tabeli (w litrach)˛˛˙białaABC0,300,250,45zielona0,600,200,20niebieska0,350,450,20czerwona0,150,550,30.Ponadto, wyprodukowanie1litra kazdej farby wymaga15minut pracy. Zysk ze sprzedazy˙˙1litra farby białej wynosi7zł, zielonej -6zł, niebieskiej -7zł, czerwonej -5zł.1.1.2Równowazno´c zada´n˙ s´Zajmiemy sie teraz zagadnieniem „równowazno´n ˙˛˙ sci” zada´ róznego typu. Dokładniej,pokazemy, ze rozwiazywanie zadania podstawowego i zadania ogólnego mozna zastapi´˛˛ c˙˙˙rozwiazywaniem zadania kanonicznego.˛Istotnie, niech dane bedzie zadanie podstawowe (6) i rozwazmy w przestrzeniRn+m˛˙zadanie postacid, z→min.,(7)gdzied= (c, 0)∈Rn+m,z∈Z={z= (u,v)∈Rn+m;z≥,Cz=b}C= [A|Im×m] =a1,1...am,1... a1,n1............... am,n...14(Im×mjest macierza jednostkowa wymiarum×m).Łatwozauwazy´, ze je´u∗∈Ujestsli˛˛˙ c ˙rozwiazaniem zadania (6), toz∗= (u∗, v∗),gdzie˛v∗=b−Au∗,jest rozwiazaniem zadania (7), t.zn.z∗∈Zoraz˛d, z∗≤d, zdla dowolnegoz∈Z.Je´ natomiastz∗= (u∗, v∗)∈Zjest rozwiazaniem zadania (7), tou∗jest rozwiazaniemsli˛˛zadania (6), t.zn.u∗∈Uorazc, u∗≤c, udla dowolnegou∈U.Podobnie, rozwiazywanie zadania ogólnego (4) mozna zastapi´ rozwiazywaniem zadania˛˛ c˛˙kanonicznego. Rzeczywi´cie, rozwazmy w przestrzeniRp(p=m+I+J+J,gdzies˙J={1,..., n} I)zadanie postaciciui+ciwi+−ciwi→min.e, z=i∈Ii∈Ji∈Jz∈Z={z= (v,ui;i∈I, wi;i∈J, wi;i∈J)∈Rp;z≥0,Aiui+Aiwi+−Aiwi=b,v+i∈Ii∈Ji∈JAiui+Aiwi+−Aiwi=b}i∈Ii∈Ji∈J={z ∈Rp;z≥0,  [Im×m|Ai;i∈I|Ai;i∈J| −Ai;i∈J]b z= }b|Ai;i∈I|Ai;i∈J| −Ai;i∈J,(8)gdziee= (0,ci;i∈I, ci;i∈J,−ci;i∈J)∈Rp,Ai-i-takolumna macierzyA, Ai-i-takolumna macierzyA.Je´u∗∈Ujest rozwiazaniem zadania ogólnego (4), tosli˛iz∗= (v∗, ui;i∈I, w∗;i∈J, wi;i∈J),∗∗5 [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

losegirl.htw.pl