Разтворът на линейния проблема
метод за програмиране симплекс
Ladover Татяна
Новоросийск Колеж по строителство и икономика
Отличителна черта ZLP формиране подгрупата на математически задачи за програмиране, е, че целта на този проблем е писано като линейна функция е (X), а също и неговите линейни ограничения.
Основната задача на линейното програмиране yavlyaetsyanahozhdenie
такива променливи х = (х1. х2. x3. ..., хп), които водят цел
функция е (X) на стойността на екстремални.
Общ изглед на модела на запис ZLP:
XI ≥ 0, I = 1 ÷ п - желаната стойност,
Aij. BJ. CI - предварително определена постоянни стойности,
BJ - запаси от суровини, енергия и т.н. J = 1 ÷ m.
Наборът от номера X = (х1. X2. X3. Xn) отговаря на ограниченията
проблемът се нарича осъществимо решение или план или валиден домейн
разтвори (SDT).
А е възможно решение, което увеличава или намалява обективната функция се нарича оптимално решение и оптималното план.
ZLP реши в конкретния случай, когато има две променливи могат да бъдат графичен метод.
Ако ZLP повече от две променливи, най-често срещаният метод за решение е симплекс метода.
Simplex е израз на формата
в1 x1 + c2 x2 + ... + Xn КН
или сумата от двойки продукти от вектори
Метод за решаване на проблеми с е (х) → мин различава от методите за решаване на проблеми в е (х) → макс. За удобство на решаване на проблемите на двата вида на един алгоритъм на модела трябва да бъдат доведени до т.нар канонична форма (CF).
Смята се, че ZLP написани на каноничната форма, ако:
а) за цел функция е увеличен;
б) проблемните ограничения приемат формата на равенство с неотрицателна част от правото (BJ ≥ 0);
в) всички променливи в модела на проблема не-отрицателни (≥ 0).
По този начин, каноничната форма на ZLP модел има следния вид:
Помислете два вида математически модели ZLP.
I.
Ние даваме на ЕО ZLP определен модел, в който всички видове ограничения ≤:
Всички неравенства ограничения на системата отляво е по-малка или равна на правото (≤). За да ги изравнят (както се изисква от каноничната форма), е необходимо да се ограничи отляво на всяка добавка. съответно неотрицателно цяло число променливи Xn + 1, Xn + 2, ..., хп + m. За да не се промени стойността на целевата функция, тези променливи са въведени в него с нулеви коефициенти.
по този начин След привеждане нашата канонична форма
задача ще бъде:
Ако ограничението в оригиналната математическия модел на проблема се дава строго знак за равенство (=), тогава не се въведе допълнителен променлива в него, но само изкуствено (виж по-долу).
Нека икономическата проблемът е описан от следния модел
Ние даваме математическия модел за CF:
II.
Разглеждане на втория специален случай: е (х) → минути и най-малко едно от ограниченията на форма ≥ (или дори всички). Модел на този проблем има следния вид:
Определяне на минималната стойност на F функция (X) може да се редуцира до намирането на максималната стойност от -F функция (х).
по този начин в такива случаи, коефициентите на неизвестните в е (х) → мин трябва да бъде умножена по (-1).
За да донесе със строги ограничения за равенство на форма ≥ на, е необходимо от лявата страна на всеки ограничаване на тази форма на приспадане. Съответно, не-отрицателни целочислени променливи Xn + 1, Xn + 2, .... Xn + m.
След това, след намаляване на задачата CF (**) ще бъде:
Всички променливи в математическият модел са разделени на два типа:
- основа (зависима), който може да бъде изразена по отношение на всички останали
променливи. Променливата е основата, ако става въпрос
само едно от уравненията в системата с коефициент, равен на 1 (както в (*) са основни променливи x3. x4. X5).
- всички други променливи са nonbasic (независими).
Особено разтвор, т.е. намиране на основните променливи nonbasic променливи от равнява на нула (XI = 0), наречена база. Основен разтвор се нарича изроден, ако поне един от основните променливи = 0, такъв проблем се нарича изроден. В противен случай - проблем, наречен не-дегенерат.
Над ние разгледахме две отделни случаи I и II.
В случай, че се основава разтвор е възможно разтвор:
и не е валидно, защото противоречи на не-негативност на променливите (XI ≥ 0).
В такива случаи, разпределението на основните променливи и намиране на приемливо решение по метода на изкуственото база, са както следва:
1) в всеки вид ограничение = ≥ прилага или изкуствен неотрицателна променлива y1. v2, ... цт;
2) изкуствени променливи включва фактор (-M) към целевата функция, където М - много голям положително число (оттук и името - метод М).
След въвеждане на CF задача изкуствени променливи (**) ще бъде:
Набор от изкуствен променливи y1. y2, ..., хм в Метод М-изкуствен форми основа. Изкуствени променливи са въведени само за да се получи първоначален основен план за решаване на симплекс метода на проблеми LP. ZLP на решение обикновено се осъществява в т.нар симплекс таблица на следния вид:
Стойността на обективната функция F (х) се изчислява като сума от продукти на сдвоени елементи и елементите на колона С Колона Б. Относителната оценката - като сума от продукти от елементи на чифт С и колонни елементи съответстващи I-тата колона.
Алгоритъм за решаване метод ZLP симплекс
1. Поставете математически
модел на каноничната форма. Попълнете таблицата за симплекс и да се изчислят стойностите
обективната функция и относителните оценки.
2. - Ако всичко относителен
оценка на не-отрицателни и без изкуствени сред основните променливи, планът
оптимално, т.е. проблемът е решен. Разтворът е в колона Б:
- Ако всички не-отрицателни относителните оценки и сред тях е равен на нула, и няма човека, тогава проблемът е решен, и има безкраен брой решения, едно от които беше в основата (намира се в колона Б) сред основните променливи;
- Ако всички не-отрицателни относителните оценки, но сред основните променливи, има изкуствен, проблемът няма решение;
- ако околната среда е относително
проучвания има отрицателен, а след това решението не е оптимално задача да се премине към
след изходното план (стъпка 3).
3. От всички отрицателни относителните оценки на избран най-висок модул. Съответният колоната се нарича лице. е необходимо да се разделят на елемент от елемент в колона на основна колона за определяне на glavnoystroki
(Нула и отрицателни числа не се разделят на основната колона). Най-малката частното
Тя отговаря на основната линия. В точката на пресичане на основната линия и основната колона
Simplex е основен елемент от таблицата. Този номер може да бъде само
положителна.
На следващо място, трябва да се направи преизчисляване на масата.
4. В новата таблица с показатели и основните линии на основната колона (заедно с техните коефициенти) са разменени. Други променливи и техните коефициенти са пренаписани без промяна.
Вместо това, основният елемент се записва обратен номер 1 / основен елемент.
Елементи на основната колона на таблицата е разделен на стария (- основният елемент).
Елементи на старата основната линия на таблицата е разделена на (основен елемент).
Всички други позиции се преизчисляват в правилото на правоъгълника:
на продуктите от елементи на основната диагонала, който преминава през основния елемент, изваждане на продукта от вторичните диагоналните елементи и резултатът се разделя на основния елемент; полученото число се записва в съответната клетка на новата симплекс таблица. Ако основната линия или основната колона има нули, а след това
елементи, съответстващи на тези нули колона и ред презаписани без
промени в новата таблица.
5. новата маса, изчислена обективни стойности функция и роднината
оценки. Преместване в т.2.
Пример 2.
Нека да решим по метода на проблем симплекс.
Учител прави cupronickel лъжици два вида: без щамповане (L1) на цената на 2 евро и щамповане (А2) на цената на 3 евро. Съветникът за ден прави поне една лъжица. Ден доставка на суровини е не повече от 12 дм 3. По този начин се образува върху лъжица L1 отива 3 дм 3 и в лъжица тип А2 - 2 дм 3 никел сребро.
Коя е максималният доход на ден може да се очаква да овладеят предмет на тези стандарти?
означаваме:
X1 - броят на лъжици тип А1,
х2 - броят на лъжици тип А2.
Изготвяме му математически модел за отчета за проблем:
приходи от продажбата на лъжици тип А1 е 2 * x1 (евро);
приходи от продажбата на лъжици тип A2 е 3 * x1 (евро). Сумата на тези числа е равно на доходите на капитана - целевата функция.
Производството на лъжици тип А1 прекарва 3 * x1 m дм 3 никел сребро и производството на лъжици тип А2 прекарва 2 * x1 дм 3 m и инструкциите, не може да се използва в деня за повече от 12 дм 3. М - това е първото ограничение. От условието, че капитанът на деня на вземане на най-малко една лъжица, пише втората ограничавам и да получите модел на проблема:
За решаване на проблема чрез симплекс метода представяме математически модел на каноничната форма:
Въз основа на каноничната форма на първоначалната изгради основните цели на плана:
Проблемът не е решен, тъй като в основата има изкуствени променливи, включително относителните оценки - отрицателни. Сред отрицателна относителна otsenokmso-Далекоизточна-шрифт семейство: Calibri; MSO-ANSI език: RU; MSO-Далекоизточна език: EN-US;
избере най-високата модул (-М 3) - съответства на основната колона; намери дома ред (втори, t.k.1 / 1 отрицателен относителна резултат самостоятелно (-3), това съответства на основната колона; основната линия - първо, съответно, основният елемент е равна на два (клетъчна подчертани в синьо) завършване преизчисляване маси се движат по. нов основен план.
Всички не-отрицателни относителните оценки, в основата на без изкуствени променливи, така че проблемът е решен.
решение:
X1 = 0 (от тази променлива не остава в основа) в основата на Х2 = 6, максималната печалба за такива артикули на производство отношение е
F (X) = 2 * 3 * 0 + 6 = 18 (евро).
2 ябълчена GS Основи на икономиката и математически методи в планирането / - Москва гимназия, 1988.-
279.
Свързани статии