Когато ZLP е под формата
Помислете за тримерна координатна пространство с подредени агрегати (точки).
Определение 3.1. Наборът от точки в пространството. координати удовлетворяват уравнението. където поне един от номерата () е различно от нула, то се нарича пространството hyperplane.
Определение 3.2. Наборът от точки в пространството. координати удовлетворяват неравенството. нарича половин пространства. разположени от едната страна на
В пространството на уравнението определя права линия, неравенството определя половината равнина.
Определение 3.3. Наборът от точки в пространството. координира което отговаря едновременно hyperplanes система () се нарича от пресичането на hyperplanes.
Определяне 3.4.Vypukloy линейна комбинация на пиксела. , ... пространство се нарича точка (.).
изпъкнала линейна комбинация на две точки в пространството е отсечка, свързваща тези точки.
Определение 3.5. Множеството от точки в пространството е изпъкнала, ако заедно с две от точки и включва произволна линейна комбинация (т.е., съдържа, заедно с две точки и всички точки на сегмента).
Определение 3.6. Boundary точка се нарича заданието, ако в даден произволно малък квартал на точките, които се съдържат в този набор, и точки, които не принадлежат към нея.
Определение 3.7. Набор се нарича затворена. ако той съдържа всички гранични точки, в противен случай - отворен въпрос.
Определение 3.8. Една точка се нарича точка на ъгъл на затворено изпъкнало множество, ако не може да бъде представен като линейна комбинация от каквито и да било други две различни точки на този набор.
Определение 3.9. Набор се нарича ограничен. ако има топка радиус от краен дължина с център във всяка точка на снимачната площадка, която напълно съдържа тесте. В противен случай, много нарича неограничен.
Определяне 3.10. Комплектът се нарича свързване yaznym. ако всеки две точки могат да бъдат съединени с прекъснатата линия (или непрекъсната крива) лежи изцяло в този набор.
Определяне 3.11. Open свързан набор се нарича домейн.
Дефиниция 3.12. Ако зоната съдържа всичките си гранични пунктове, той се нарича затворена зона.
Дефиниция 3.13. Затворен изпъкнал област, която има определен брой точки, се наричат ъглови измерения изпъкнал многостен.
Дефиниция 3.14. Затворен изпъкнало множество като краен брой ъглови точки се нарича двумерен изпъкнал многостенна
Определяне 3.15.Peresecheniem задава е набор от точки, които е обща част от тези комплекти.
Дефиниция 3.16. Непразна набор от изпълними решения ZLP nazyvayutmnogogrannikom планове (решения).
Дефиниция 3.17. Corner решения полихедронов точка се нарича връх.
Дефиниция 3.18. Върховете на планове с неотрицателни координати, наречени справка. Планът съответстващ се нарича план подкрепа.
От определенията следва, че всеки връх на многостен съответства на плана за справка решения ZLP.
Дефиниция 3.19. Основен план се нарича не-дегенерат. ако съдържа точно положителни координати и дегенерат. ако по-малко положителни координати.
Теорема 3.1 (основното теоремата на линейното програмиране). Ако ZLP има оптимално решение, целевата функция се екстремната стойност на един от върховете на плановете. Ако целевата функция е на крайната стойност на повече от един връх, а след това тя отнема по всяко време, тъй като е изпъкнал комбинацията.
Дефиниция 3.20. Ако целевата функция е на крайната стойност на повече от един топ планове на многостен, тогава ние казваме, че ZLP има оптимална алтернатива.
Дефиниция 3.21. Наборът от точки, които съставляват областта на изпълними решения, в случай на две контролни променливи се нарича полигон решения (планове).
Многоъгълника разтвори могат да бъдат плоски многоъгълник, неограничен различни многоъгълна, сегмент. Геометрично ZLP представлява търсене точка многоъгълни разтвори, чиито координати достави линейна функция цел максимална или минимална стойност, допустимите разтвори са разтвори на всички точки на многоъгълника.
Помислете за графичен метод за решаване на ZLP.
1) Да предположим, че системата на неравенството (3.1) е в съответствие (има поне една точка, която отговаря на всички ограничения наведнъж). На координатната равнина ние изгради набор от възможни решения, които се съобразяват с ограниченията (3.1). Всяка неравенството на системата (3.1) определя полуравнина () с гранична линия ().
Да предположим, че, например, времето на равнината, определена от неравенството. За конструиране на половината равнина () е достатъчно, за да замести съответния неравенството координати на всяка точка (например, (0, 0)), за да се провери валидността на това неравенство. Ако неравенството е вярно, то е необходимо да се сянка на половината равнина, съдържаща тази точка. Ако неравенството е лъжа, а след това на полу-сянка, не съдържащ дадена точка.
Условия за не-негативност на променливите контрол. определи полуравнина с граничните линии. (Първото тримесечие на координатната). Тъй като системата на ограничения заедно, полуравнината имат обща площ. Пресечната точка на половин равнини е изпъкнала комплект и е набор от точки, координатите на които са валидни решения.
2) Изграждане на градиента на обективната функция (в този случай, геометричната вектор):
с начална точка и крайна точка. показващи посоката на най-голямото увеличение на целевата функция.
3) изграждане на нивото на линията на обективната функция. Тази линия е права линия (ако стигнем нула линия. Cm. Фиг. 3.1) и е перпендикулярна на наклона. Като правило, е препоръчително да изберете стойност, при която съответното ниво на линията имаше различни изпълними решения за най-малко две общи точки.
4) За да се реши проблемът на максимума на функцията трябва да се движи линията на ниво в посока на наклон, докато то не само една обща точка с набор от възможни решения. Тази точка се определя от един единствен ZLP решение ще бъде екстремум (максимум). В решаването на проблема с минимизиране на функцията, се движи линията на ниво в обратна посока на градиента до толкова дълго, колкото тя не само ще една обща точка с набор от възможни решения. Тази точка се определя от един единствен ZLP решение ще бъде екстремум (минимум).
5) Да се намерят координатите на върховете на многоъгълника, което е екстремум. За да направите това, трябва да се реши на система от уравнения на линиите, което е в началото на тази пресечка.
6) Изчислява се стойността на обективната функция в резултат върха.
Забележка 3.1. Ако се движите по линията на ниво градиент никога не напуска снимачната площадка на изпълними решения, тогава този комплект е неограничен по посока на оптимизация. В този случай обикновено се смята, че двете.
Забележка 3.2. ZLP няма да има решение, ако наборът от изпълними решения е празен. Това означава, че системата на ограничения е противоречива неравенство, а на координатната равнина няма смисъл, че отговаря на всички ограничения наведнъж.
Забележка 3.3. В ZLP на решение графичен метод може да отговаря на случая, когато линията за ниво е успоредна на една от страните на изпъкнал многоъгълник на възможни решения, и тази страна е в посока на оптимизация. След оптималната стойност на обективната функция се постига при двете ъглови точки (върховете) на областта на възможни решения, и следователно, във всички точки на сегмента свързването на тези върхове, т.е. ZLP има безкраен брой решения (алтернативно оптимално).
Пример 3.1. Фирмата произвежда два вида сладолед: масло и шоколад. две изходни материали, използвани за производството на сладолед: мляко и пълнители, разходите за които на 1 кг сладолед и DSA запаси са дадени в таблицата по-долу:
Консумацията на изходен материал на 1 кг сладолед
Проучване на пазара показа, че всеки ден търсенето на сладолед надвишава търсенето на шоколад е не повече от 100 кг. Освен това беше установено, че търсенето на шоколадов сладолед за да не надвишава 350 кг на ден. Продажната цена на 1 кг сладолед 16 рубли. шоколад - 14 рубли. Какъв е броят на сладолед всеки вид трябва да представят
компания, за да спечели от продажбата на продукти, е най-високата? [1; 2].
Решение. Означаваме контролни променливи: - дневния обем на сладолед, кг; - дневния обем на шоколадов сладолед, кг. Ние изграждане на математически модел на проблема. Целевата функция ще изглежда така.
Да се изготви неравенството на ресурсните ограничения. Ограничаване на мляко е както следва :; пълнители :. Изготвяме неравенството на пазарните ограничения при поискване. Разликата в рамките на дневното потребление за два вида сладолед е. Ограничението на дневно търсене на шоколадов сладолед.
Тогава математически модел на проблема е от вида
Освен това, графичен метод ще реши проблема.
1) Ние конструира набор от възможни решения. Неравенство определя половината равнина, разположена отляво и под линията. това е, права линия. Неравенство определя половината равнина, разположена отляво и под линията. Ограничение определя половината равнина, разположена отляво и под линията. Ограничаване определя полуравнина, разположен от лявата страна на линията. ограничения. определяне на първи координира тримесечие. ZLP набор от изпълними решения, не е празна. Ние означават разтвори върховете на многоъгълника (Фигура 3.2.).
2) Изграждане на градиента на обективната функция:
3) изграждане на нивото на линията на обективната функция. , ниво линия, перпендикулярна на вектора.
4) Придвижване на линията в посока, успоредна на себе си, ние откриваме, крайната точка, в която обективната функция ще напусне областта на възможни решения (прекъснатата линия на фиг. 3.2). Limit точка на полигона - точка.
5) Намерете координатите на точката, като пресечните точки на линиите и:
6) Намерете стойността на целевата функция в точка:
Свързани статии