симплекс метод? Помагайте!
11 отговора
513 прегледа
Re: симплекс метод? Помагайте!
Did you mean: simplex method ?
Разбира се, че мога да го извадя от гугъл-а, ако си имах по принцип някаква идея за какво става въпрос. Аз съм скаран с математиката и физиката откакто завърших средното си образование, а това беше преди повече от 10 години, а и тогава не ме биваше кой знае колко в тази област.
Разбира се, че мога да го извадя от гугъл-а, ако си имах по принцип някаква идея за какво става въпрос. Аз съм скаран с математиката и физиката откакто завърших средното си образование, а това беше преди повече от 10 години, а и тогава не ме биваше кой знае колко в тази област.
Re: симплекс метод? Помагайте!
Май бед, дис уоз а тайпо :-)
Тук става въпрос за "линейно програмиране" (ЛП).
В общия случай ЛП е функция (т.нар. "обективна функция"), която трябва да се "максимизира"/"минимизира" (т.е. трябва да намериш най-голямата/малката й стойност, в зависимост от задачата (в твоя случай - мин.) ), която е зависима от поредица от ограничаващи неравенства (constraints).
Има няколко основни алгоритми, които решават проблема на "линейното програмиране". Симплексът е един от най-известните (другия е Елипсоидния, ако не ме лъже паметта).
Та, ако знаеш GAMS, тук можеш да решиш задачата си (просто дефинирай в синтаксиса на GAMS условието на задачата и сървера ще ти я реши):
[линк]
Тук става въпрос за "линейно програмиране" (ЛП).
В общия случай ЛП е функция (т.нар. "обективна функция"), която трябва да се "максимизира"/"минимизира" (т.е. трябва да намериш най-голямата/малката й стойност, в зависимост от задачата (в твоя случай - мин.) ), която е зависима от поредица от ограничаващи неравенства (constraints).
Има няколко основни алгоритми, които решават проблема на "линейното програмиране". Симплексът е един от най-известните (другия е Елипсоидния, ако не ме лъже паметта).
Та, ако знаеш GAMS, тук можеш да решиш задачата си (просто дефинирай в синтаксиса на GAMS условието на задачата и сървера ще ти я реши):
[линк]
Re: симплекс метод? Помагайте!
Илияне,
аз си имам собствено написана програмка за симплекса, и ми беше лесно да въведа коефициентите за да пробвам. Обаче получих глупости:
; BUG:
;
; Maximum = 2.19999e+007
; x[1] = -1.11308e-308
; x[2] = +9.33333
; x[3] = -6
; x[4] = -6
Идиотската стойност за x[1] = -1.11308e-308 трябва да е на практика минус безкрайност, понеже е най-малкото възможно число с плаваща точка за компютъра (по абсолйютна стойност най-голямо за компютъра, но с отрицателен знак).
Като погледнах по-внимателно трите неравенства видях че във всяко едно има по един нулев коефициент, т.е. това са три хипер-4мерни-равнини успоредни на някоя от трите координатни оси X1, X2, и X4. Заедно с условието
x1, x2, x3, x4 >= 0
образуват един отворен от към оста X3 хипер-паралелепипед. Значи като нямаме затворено тяло, може резултата да е логичен (но защо получхих минус безкрайност в X1 а не в X3?- трябва да грешкав разсужденията ми, предполагам)
Т.е.,
струва ми се ... може би да има печатна грешка в условието, или професора умишлено е поставил така задачата, за да постави на изпитание студентите си.
/Линейното програмиране ми е стар спомен, .. не твърдя, че текста ми по-горе е верен, а по-скоро пиша, че някой по-компетентен да обясни къде е проблема, за да си припомня нешата
ОК?/
аз си имам собствено написана програмка за симплекса, и ми беше лесно да въведа коефициентите за да пробвам. Обаче получих глупости:
; BUG:
;
; Maximum = 2.19999e+007
; x[1] = -1.11308e-308
; x[2] = +9.33333
; x[3] = -6
; x[4] = -6
Идиотската стойност за x[1] = -1.11308e-308 трябва да е на практика минус безкрайност, понеже е най-малкото възможно число с плаваща точка за компютъра (по абсолйютна стойност най-голямо за компютъра, но с отрицателен знак).
Като погледнах по-внимателно трите неравенства видях че във всяко едно има по един нулев коефициент, т.е. това са три хипер-4мерни-равнини успоредни на някоя от трите координатни оси X1, X2, и X4. Заедно с условието
x1, x2, x3, x4 >= 0
образуват един отворен от към оста X3 хипер-паралелепипед. Значи като нямаме затворено тяло, може резултата да е логичен (но защо получхих минус безкрайност в X1 а не в X3?- трябва да грешкав разсужденията ми, предполагам)
Т.е.,
струва ми се ... може би да има печатна грешка в условието, или професора умишлено е поставил така задачата, за да постави на изпитание студентите си.
/Линейното програмиране ми е стар спомен, .. не твърдя, че текста ми по-горе е верен, а по-скоро пиша, че някой по-компетентен да обясни къде е проблема, за да си припомня нешата
ОК?/
Oops!
Това x[1] = -1.11308e-308 което съм получил не е минус безкрайност, ами НУЛА, понеже експонентата е с отрицателен знак: ......e-308
Сигурно програмата ми не е коректна и да се сбърквясва при грешно зададени данни.
Понеже, чрез чисто логически разсъждения, откривам ограничителните условия (трите неравенства) не ни позволяват да намерим смислен отговотр. Защото областта зададена от ограничителние условия не е затворено (компактно) тяло .. и тогава задачата не е коректна, та не е чудно че моята дилетантска програма се сгъбясва.
Сигурно програмата ми не е коректна и да се сбърквясва при грешно зададени данни.
Понеже, чрез чисто логически разсъждения, откривам ограничителните условия (трите неравенства) не ни позволяват да намерим смислен отговотр. Защото областта зададена от ограничителние условия не е затворено (компактно) тяло .. и тогава задачата не е коректна, та не е чудно че моята дилетантска програма се сгъбясва.
в отговор на eднo мoмичe
#8
Re: симплекс метод? Помагайте!
Моля ти се невинно девойче, не ме упреквай за такива работи!
Моята леля (имам такава:) може да ме хванве че и пипам парите за ежедневната порция пенсионерско кисело мляко, .. но знай, че съм и взел парите за да си купя хашиш и кока -- нещо жизнено важно за мене!
Майтап де, не употребявам по-силни наркотици от кафе, кола, и бирича :)
Моята леля (имам такава:) може да ме хванве че и пипам парите за ежедневната порция пенсионерско кисело мляко, .. но знай, че съм и взел парите за да си купя хашиш и кока -- нещо жизнено важно за мене!
Майтап де, не употребявам по-силни наркотици от кафе, кола, и бирича :)
Re: Oops!
Е, то си зависи от това на каква машина си пуснал да се мели кодът. На Ц++ ли си я писал програмката? Там има разни форматори за изписване на числата, които понякога се побъркват, ако не ги настроиш подходящо.
Нямам време да напиша условието на ГАМС и да изкарам резултата. Пък и не е хубаво така :-) А ти защо си максимизирал о.ф.? Нали уж трябва да се минимизира? :-) Макар, че... като го гледам така условието, по-точно - ограниченията, това си е задача баш за максимизиране, а защо е написано МИН - не знам... :-) Ти затова май си минимизирал...
Нямам време да напиша условието на ГАМС и да изкарам резултата. Пък и не е хубаво така :-) А ти защо си максимизирал о.ф.? Нали уж трябва да се минимизира? :-) Макар, че... като го гледам така условието, по-точно - ограниченията, това си е задача баш за максимизиране, а защо е написано МИН - не знам... :-) Ти затова май си минимизирал...
Re: Oops!
Максимизирал съм, защото програмата ми е написана да максимизира, обаче съм имножил по -1 вектора на цената, което до колкото си спомням е трик за да намерим минимума.
Обаче не зная дали отговора е верен; може да съм сбъркал някъде. Понеже, както казах, не съм много наясно с линейното програмиране; и съм програмист, а не професионален математик.
Програмката съм си я писал преди време по книга (уж вярно), заради една задача за оптимално разкрояване на правоъгално парче (листова стомана) на по-малки правоъгълни парчета (детайли) за да се пести материала.
Исках просто да си припомня задачата, и ако може да помогна. Решението на дилемата на автора ме интересува, понеже съм ги позабравил нещата, но искам да съм в час.
ОК?
Обаче не зная дали отговора е верен; може да съм сбъркал някъде. Понеже, както казах, не съм много наясно с линейното програмиране; и съм програмист, а не професионален математик.
Програмката съм си я писал преди време по книга (уж вярно), заради една задача за оптимално разкрояване на правоъгално парче (листова стомана) на по-малки правоъгълни парчета (детайли) за да се пести материала.
Исках просто да си припомня задачата, и ако може да помогна. Решението на дилемата на автора ме интересува, понеже съм ги позабравил нещата, но искам да съм в час.
ОК?