abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
včera 22:00 | Komunita

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 1
včera 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 26
včera 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 7
3.12. 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 14
3.12. 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 25
2.12. 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 15
2.12. 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 5
2.12. 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
2.12. 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 1
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 774 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Algoritmus optimálního výběru

13.7.2015 15:00 camel1cz | skóre: 23
Algoritmus optimálního výběru
Přečteno: 635×

Zdravím a prosím o pomoc s algoritmickým řešením následující úlohy:

Je dáno:

  • máme 9 druhů kamenů,
  • každá uspořádaná trojice kamenů má určité ohodnocení (řekněme body),
  • na začátku dostanu pytlík s mixem kamenů (je dán počet každého z nich).

Pravidla:

  • znám ohodnocení těch kombinací,
  • mohu si vybrat libovolnou kombínaci z pytlíku,
  • mohu tu kombinaci směnit za body podle ohodnocení (tedy příjdu o 3 kameny a dostanu X bodů)

Cílem je získat pro daný mix v pytlíku nejvíce bodů.

Díky za postrčení.

P.S. Hladový algoritmus? Generický algoritmus? Něco jiného? Jak na to? Nějaké knihovny atd.? Řešit to potřebuju v PHP.


Řešení dotazu:


Odpovědi

Jendа avatar 13.7.2015 15:06 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Pustil bych na to glpsol.

Problémy:
  • není to v PHP
  • možná to bude mít exponenciální časovou složitost
13.7.2015 16:11 Radek Isa | skóre: 11
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
jedná se o algoritmy umělé inteligence. Jak velký může být problém??
Doporučuji si něco nastudovat o prohledavání do hloubky(DFS), prohledávání do šírky(BHF), iterativní prohledávání a backtraking. Jedná se o algoritmy s umělou inteligencí.
13.7.2015 16:18 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Něčeho takového jsem se obával... zrovna moc zběhlý v tom nejsem a nevyplatí se mi to studovat kvůli této úloze :(

Jinak rozsah problému je: 9 druhů kamenů, 729 kombinací výběru a množství kamenů v úvodní množině řekněme v řádu stovek... umím si představit < 600
13.7.2015 16:40 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Od pohledu se mi zdá, že to polynomiální nebude. Potřebuješ garantované maximum nebo ti stačí co nejlepší výsledek? Je to jednorázová úloha, která se může chvíli počítat nebo potřebuješ, aby to generovalo odpovědi na počkání? Té umělé inteligence se moc bát nemusíš, za složitými názvy se schovávají jednoduché algoritmy.

729 můžeš zredukovat na 165 (jestli dobře počítám) - zahoď trojice, které mají nižší ohodnocení než jiná trojice ze stejných kamenů.
13.7.2015 16:54 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Jde o interaktivní úlohu - uživatel bude zadávat 9 čísel (počty jednotlivých kamenů) a očekává posloupnost kroků, jak se dopracovat k optimálnímu zisku bodů.

Maximum nemusí být garantované - stačí "dobré maximum" :-)

Jediné na co jsem přišel je: 1) genetický algoritmus, ale snažím se najít přímočařejší řešení... v tomhle oboru nemám moc zkušeností. 2) hladový algoritmus, teda snažit se volit nejziskovější kombinaci co jde.

To zahození je dobrý nápad! Určitě zjednoduší problém... můžu zahodit horší nebo stejné kombinace složené ze stejných kamenů.

Jendа avatar 13.7.2015 16:43 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Tady je na to manuál se kterým jsem podobný problém zvládl.

Ten program bude něco jako
*_kamenů >= 0 integer

kombinace1 = 19 bodů
kombinace2 = 11 bodů
...

červených_kamenů = 2*kombinace1 + kombinace2 + ...
...

červených_kamenů <= kolik_máš_červených_kamenů
...

ct = sum kombinace*; max ct; solve
Jendа avatar 13.7.2015 16:38 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
DFS, BFS, iterativní prohledávání a backtracking mi nepřijde moc jako „algoritmy s umělou inteligencí“. Asi nemám tendenci je vidět všude… A nějak nevím jak to řeší tazatelův problém…
18.7.2015 11:51 David
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Prohledávání stavového prostoru je skupinou metod řešení úloh, spadající do oblasti umělé inteligence. Doporučuji si nastudovat základní věci.
13.7.2015 20:06 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Pokud těch kamenů není příliš mnoho, tak to můžete vyřešit dynamickým programováním – pro každou devítici si spočítat maximální skóre. Když pak přecházíte k devítici s větším počtem kamenů, tak zkusíte až 729 způsobů (ve skutečnosti méně), jak tato větší devítice mohla vzniknout z menší devítice (jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu větší).

Pokud můžete k řešení použít nějaký externí program, tak bych zkusil nějaký CSP řešič – například minion.
13.7.2015 21:29 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Nepochopil jsem - mám problém s menší a větší deviticí (čekal bych, že devítice jsou všechny stejné). Taky mi není jasné, proč uvažovat devítice, když jsou ohodnocené trojice. Ve své úvaze dospěl k závěru, že dynamické programování na to aplikovat nepůjde, tak mě zajímá, jestli jsem něco přehlédl.
jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu větší
Pokud znám nejlepší řešení pro 1 trojici a 2 trojice, nevidím jak snadno najít nejlepší řešení pro tří trojice. Jde najít kombimace, kdy v nejlepším řešení pro tři trojice nebude žádná trojice, která je v nejlepších řešeních pro 1 resp. 2 trojice.
13.7.2015 21:47 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Myslel jsem něco jako (s tím, že se výsledky maxSkore budou cachovat):
// poctyKamenu je pole. poctyKamenu[i] oznacuje, kolik kusu i-teho kamene mame.
function maxSkore(poctyKamenu)
  m = 0
  for i = 1 .. 9 do
    for j = 1 .. 9 do
      for k = 1 .. 9 do
        if poctyKamenu umoznuji vybrat trojici (i, j, k) then
          od poctyKamenu odecti kameny pouzite v (i, j, k)
          m = max(maxSkore(poctyKamenu) + skore trojice (i, j, k), m)          
          k poctyKamenu pricti kameny pouzite v (i, j, k)
        end if
      end for
    end for
  end for
end function
13.7.2015 21:48 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Na konci funkce musíte vrátit m, to jsem zapomněl.
13.7.2015 22:04 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
BTW, jak psal TTTTTTTT, počet možností by šlo snížit uvažováním neuspořádaných trojic (vyberete si uspořádanou trojici s největším skóre):
  for i = 1 .. 9 do
    for j = i .. 9 do
      for k = j .. 9 do
Dále lze v rekurzivních voláních maxSkore uvažovat pouze lexikálně stejně velké nebo vyšší trojice.
13.7.2015 23:58 TTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Dík, už chápu. Nevím proč jsem uvažoval jen budovat to "odspodu". Každopádně při uvedených číslech se tímto způsobem zřejmě nedopočítá (buď dojde cache nebo to bude počítat roky). Dá se to zřejmě ještě dost prořezat - např. zkusit nejdřív najít nějaké dobré řešení (třeba hladově) a pak zaříznout výpočet už ve chvíli, kdy vidím, že už nedostanu tak dobré řešení. Nebo podobně jako jsem zahodil některé drojice, můžu si předpočítat i které dvojice (trojice, čtveřice) trojic nikdy nebudou spolu v řešení. Ale i tak bych vsadil spíš na to lineární programování.
13.7.2015 22:20 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Pokud máte hodně kamenů a nehledáte optimální řešení, můžete použít lineární programování.
Jendа avatar 13.7.2015 22:39 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
To byl ten glpsol nahoře (když zruší integer podmínku, tak to asi nenajde optimum, ale řešení by mohlo být „docela dobré“ a spočítá se rychle).
13.7.2015 22:47 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Lze zkusit php-simplex, ten je v PHP.
14.7.2015 10:41 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.

Nemohu volit jako proměnné sadu 9 proměnných (pro každý kámen jedna) - protože kámen má různou hodnotu v různých kombinacích (v tom je složitost té úlohy).

Musím tedy volit jako proměnné trojice kamenů - nejdříve eliminuji závislost kombinací na pořadí výběrem vždy té nejcennější z nich - tak docílím komutativnosti výpočtu dále. Pak to bude vypadat tak, že budu mít několik set funkcí (to budou zadané ceny kombinací a budou pro mou úlohu konstatní).
x(1) = 3
x(2) = 9
...
x(n) = k(n)
Dále mám nějaké kameny, to vyjádřím:
y(1) = 100 // tím zavedu počet kamenů, možná by mělo být y(m) <= k(m) ale to je detail
y(2) = 23
...
y(9) = 11
Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?

Podle mého nikdy nedostanu do jedné (ne)rovnice x(n) a y(m), protože hodnota kamenu není konstanta...

Uniká mi něco?
14.7.2015 11:12 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Musím tedy volit jako proměnné trojice kamenů
Ano. Trojice kamenů očísluji 1-729 a x(i) bude vyjadřovat, kolikrát vyberu trojici s číslem i.

Je-li c(i) konstanta s cenou trojice číslo i, pak chceme maximalizovat c(1)*x(1) + … + c(729)*x(729) s tím, že počty použitých kamenů nesmí přesáhnout počty kamenů na vstupu.

Tj. označíme-li n(1), …, n(9) počty kamenů na vstupu, pak pro každé n(j) musí platit:
    (suma x(i) takových, že trojice číslo i obsahuje právě jeden kámen j) +
2 * (suma x(i) takových, že trojice číslo i obsahuje právě dva kameny j) +
3 * (suma x(i) takových, že trojice číslo i obsahuje právě tři kameny j) <= n(j)
Jendа avatar 14.7.2015 13:03 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.
Napsal jsem to výše. (btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší)
Pak to bude vypadat tak, že budu mít několik set funkcí
Ano, to není problém, třeba můj úkol pro předmět ze kterého pochází ten manuál měl 10k funkcí a výpočet trval pár sekund.
Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?
Vyrobíš si proměnné z(1) .. z(n), které značí, kolikrát jsi kterou kombinaci použil. Potom vyrobíš proměnné a(1) .. a(9), které v závislosti na vektoru z ukazují, kolik kamenů jsi využil.
a(1) = 1*z(1) + 2*z(2) + 1*z(4)
pokud v kombinaci 1 je 1 kámen barvy 1, v kombinaci 2 jsou 2 kameny barvy 2, v kombinaci 3 žádný atd.

Pak už jenom zadáš podmínky že nesmíš použít víc kamenů než máš
a(1) <= y(1)
Pak zadáš účelovou funkci - součet ohodnocení * kolikrát ta kombinace padla
ct = z(1)*x(1) + z(2)*x(2) + .. + z(n)*x(n)
A řešíš pro
max ct
Ale jak jsem psal, pokud to jde iterativně dynamicky, dá to lepší výsledek a nejspíš to doběhne i rychleji.
14.7.2015 13:34 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší
Obávám se, že pro větší počet kamenů to je nepraktické. Například pro 100 kamenů celkem existuje 108! / 100! / 8! možných devític.
14.7.2015 14:57 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
To je počet možných _zadání_ programu, ne? Velikost potřebná pro řešení je podle mě horší. Uvažujme, že mám od každého kamene 10+ kusů, tedy jsem schopen sestavit 1ibobolných 10 trojic. Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojic, kterých je 738! / 10! / 728!. To je ještě přibližně totéž jako 108! / 100! / 8!, ale pro 20 kusů od každého míčku se z toho stane 738! / 20! / 718! ~ 10^38 (resp. 10^25 při zredukování 729 na 165), ne "přijatelných" 208! / 200! / 8 ~ 10^15 .

Pokud bych necachoval, tak při 99 kamenech má ta rekurze 33 úrovní s větvícím faktorem 729 (resp. ~150) => 10^66. Hádám, že to tedy ani nedokážu paměť vyměnit za čas.
Jendа avatar 14.7.2015 15:34 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
(tohle mi nikdy nešlo)
Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojic
Cache je 9-rozměrné pole o hranách kolik_kamenů_od_té_barvy_máme, ne? Takže pro 20 kusů od každého kamene je to „jenom“ 20^9 * sizeof(uint64) = 4 TB.
14.7.2015 16:33 TTTTTTTT
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Hm, mě to kdysi možná i šlo, ale zdá se, že ty časy jsou už ty tam. Máš pravdu.
Jendа avatar 14.7.2015 15:36 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
A pokud alespoň trochu můžeš, nepoužívej ten php-simplex, ale spouštěj z PHP binárku glpsol. Ten je oproti php-simplexu značně optimalizovaný.
14.7.2015 21:17 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
jj jedu na tom glpsol... mám to napsané, ale někde je chyba... píše to, že "multiplication of linear forms not allowed" na řádku s tou maximalizací účelové funkce.

Kod vypadá takto (zkráceno):

# x(i) ... promenna kolikrat jsem pouzil kombinaci i (vůbec nebo libovolně krát)
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x11 >= 0;
...
var x729 >= 0;

# c(i) ... hodnota kombinace i (dané konstanty)
var c1 = 6;
var c2 = 5;
var c3 = 6;
var c4 = 5;
var c5 = 5;
var c6 = 7;
var c7 = 8;
var c8 = 9;
var c9 = 5;
var c11 = 4;
...
var c729 = 3;

# vstupy a(i) - kolik mám kamenů daných typů (nerovnost, protože nemusím použít všechny)
var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;
var a5 <= 0;
var a6 <= 0;
var a7 <= 0;
var a8 <= 0;
var a9 <= 0;

# a(n) ... pocet pouzitych kamenu n... tohle je dáno zadáním - např. kombinace 1 je ze 3 kamenu typu 1, proto je v a1 člen 3*x1
v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4 + ...
v2: a2 = 0 + 1*x2 + 2*x11 + 1*x12 + 1*x13 + ...
v3: a3 = 0 + 1*x3 + 1*x12 + 2*x21 + 1*x22 + ... 
v4: a4 = 0 + 1*x4 + 1*x13 + 1*x22 + 2*x31 + ...
v5: a5 = 0 + 1*x5 + 1*x23 + 1*x32 + 2*x41 + ...
v6: a6 = 0 + 1*x6 + 1*x15 + 1*x24 + 1*x33 + ...
v7: a7 = 0 + 1*x7 + 1*x25 + 1*x34 + 1*x43 + ...
v8: a8 = 0 + 1*x8 + 1*x17 + 1*x26 + 1*x35 + ...
v9: a9 = 0 + 1*x9 + 1*x27 + 1*x36 + 1*x45 + ...

# ucelova fce ct = c(1)*x(1) + c(2)*x(2) + .. + c(n)*x(n) - vždy násobím hodnotu kombinace krát počet jejích užití... celkový součet maximalizuji
maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4 + c5*x5 + c6*x6 + ...

solve;
end;

Ty kombinace jsem zkrátil - teda vybral vždy jen jen tu nejlepší permutaci pro danou trojici kamenů - zbylo 165 kombinací.

Netušíte, v čem je zakopaný pes a co je špatně?
Řešení 1× (camel1cz (tazatel))
14.7.2015 22:02 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
multiplication of linear forms not allowed
Nemůže být problém v tom, že násobíte proměnné jinýmy proměnnými? Místo c1, c2 atd. bych zkusil použít přímo konkrétní čísla.
15.7.2015 01:10 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Díky moc, takhle jsem to nakonec udělal... i když Jenda níže našel asi lepší zápis s ponecháním konstant. Ale to už jsem ladil jednoduchý TCP server, který dotazuji z PHP :)
Řešení 1× (camel1cz (tazatel))
Jendа avatar 14.7.2015 22:16 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
param c1 := 6; etc. Píšou to tady. glpk nepochopil, že je to konstanta, a myslí si, že řešení není hodnědimenzionální mnohostěn, ale že je to omezené nějakým polynomem proměnná*proměnná.
/tmp> cat lin.mod
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;

param c1 := 6;
param c2 := 5;
param c3 := 6;
param c4 := 5;

var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;

v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4;
v2: a2 = 0 + 1*x2;
v3: a3 = 0 + 1*x2;
v4: a4 = 0 + 1*x3;

maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4;

solve;
end;
/tmp> glpsol -m lin.mod 
GLPSOL: GLPK LP/MIP Solver, v4.55
Parameter(s) specified in the command line:
 -m lin.mod
Reading model section from lin.mod...
24 lines were read
Generating v1...
Generating v2...
Generating v3...
Generating v4...
Generating ct...
Model has been successfully generated
GLPK Simplex Optimizer, v4.55
5 rows, 8 columns, 15 non-zeros
Preprocessing...
1 row, 2 columns, 2 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  2.000e+00  ratio =  2.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 1
*     0: obj =   1.200000000e+01  infeas =  0.000e+00 (0)
*     1: obj =   1.500000000e+01  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (102316 bytes)
Model has been successfully processed
No a tohle ti najde řešení, které když zaokrouhlíš, tak asi bude nějak „přiměřeně dobré“ (v tom předmětu ze kterého to pochází se pak třeba dokazuje jestli takto získané řešení není více než 2x horší než skutečné optimum atd.). Když za "x" proměnné napíšeš "integer" (var x1 >= 0, integer;), tak to najde optimum, ale asi to bude počítat dýl (obecně až exponenciálně dlouho).
14.7.2015 22:28 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
obecně až exponenciálně dlouho
Obecně i Simplex počítá exponenciálně dlouho (lineární programy lze však řešit v polynomiálním čase – například elipsoidovou metodou).
Jendа avatar 14.7.2015 22:32 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Jsem se musel podívat jestli jsi mě z tohohle předmětu vlastně letos necvičil, ale ne, to byl Radek Hušek :-).

Vím, a gplk neimplementuje elipsoidovou metodu?
15.7.2015 01:06 camel1cz | skóre: 23
Rozbalit Rozbalit vše Re: Algoritmus optimálního výběru
Tak hlásím úspěch! Sice mi to vrací v některých případech nepřípustné kombinace, ale to bude asi chybou v sestavení rovnic... případné odladění již zvládám!

Moc děkuju všem, kdo mi pomáhali a hlavně Jendovi - jehož považuji za řešitele problému.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.