Gomory метод за решаване на задачи на линейното програмиране

Решението на проблема с LP Gomory

Благодаря за четене и за споделяне с други хора

Задачите, които решават по-рано винаги се дава число отговор. Това е така, защото, че първоначалните данни е била избрана по специален начин. Но това не винаги е така.

Той е много по-вероятно да реагира със съответните частични стойности - например, необходимостта да се получи 2.5 единици от продукт А и 3.44 единици продукт Б. дали решението е приемливо? Всичко зависи от условията на проблема. Ако ние произвеждаме, като брашно и захар в килограми - това решение е доста приемливо. 2.5 единици от продукт А - е 2 кг брашно 500 грама и 3.44 единици продукт В е 3 кг 440 грама захар. Въпреки това, представете си, че продукт А - е компютър, и Б на продукта - е MP3-плеъри. Как мога да направя 3,44 единици на MP3-плеър? Очевидно е, че по никакъв начин. В такива случаи ние казваме, че е необходимо да се реши проблема с число линейно програмиране, което означава, че отговорът трябва да се обърнем числа.

За решаване на проблеми число са разработили специален метод, наречен метод Gomory. В действителност, на метода на Gomory е просто "надстройка" по-горе метод на обикновен симплекс, което сме научили в предишните глави. Идеята за метода на Gomory е, че може да реши проблема на по традиционния метод на симплекс, като (вероятно) не е цяло число, решение, а след това за всеки не-число променлива, за да добавите "корекция" ограничение, което на първо място, да направи това целочислена променлива, и второ, минимално отрази на стойността на целевата функция.

Така че, ясно е, че първо трябва просто да се реши проблема по метода на симплекс, а след това за всеки не-число променлива в решението малко "ощипване" си стойност. Това означава, че веригата на метода на Gomory, подобно на следното:

Решаване на проблема първоначалното производство конвенционален метод симплекс;
Уверете се, че отговорът е получен неинтегрален. Ако е цяло число, тогава проблемът е решен;
Увеличаването тази стойност в последния ред (ред F) до 1;
Засега отговорът остана извън цели числа, направете следното:
1. Сред стойности не са цели числа в резултат решението за избор на променлива, за която искате да направите допълнително ограничение (как да направите това ще бъде обяснено в примера по-долу);
2. За първоначалния проблем да се добави, специално съставена лимит за избраната променлива (отново в примера ще бъде показано как точно да направите това). Това ще доведе до допълнително помощно променлива;
3. Към този проблем една стъпка за прилагане на симплекс метода, спомагателната променлива, която се появява за да се отстрани и се добавят някои от изходните (който също е обяснено в примера).
Предишния етап (етап 4) трябва да се извърши, докато всички от разтвора не става цяло число. Gomory метод гарантира, че на определен етап ще се случи със сигурност.

Gomory метод ще реши едни и същи производствени проблеми трябва да бъдат решени преди симплекс метода, но това се промени един номер - разтвора с помощта на симплекс метода е превърнал неинтегрален:

Сега на втория ред ние изразяваме основната променлива $ $ X_A, защото наистина, в колоната $ $ X_A една стойност е 1, а останалата част - 0. итерация се прави.

итерация 3

Преди извършването на следващата итерация, трябва да се провери дали нашето решение е оптимално? Последният ред е налице отрицателни елементи, по този начин, нашето решение е оптимално. Ако напишете стойността на променливите на интереси $ x_A, x_B, $ x_C, ние откриваме, че $ x_A = \ Фрак; x_B = 0; x_C = \ Фрак $. се получава извън цяло число. Следователно, трябва да се прилага метод Gomory. По метода на Gomory трябва да добавим още едно ограничение на нашия проблем. Първо трябва да се определи за някои noninteger променлива ще бъде допълнителен натиск. Имаме две не-цели числа - $ x_C $ и $ x_A $. За да се определи до каква точно е необходимо да намерите най-дробни части на номерата, включени в съответния ред, колона В.

Броят на низ $ x_C $ на колона B се равнява на $ \ Фрак $. Ние можем да го напиша като $ 9 \ Фрак $. Нейната дробна част се равнява на $ \ Фрак $
Броят на низ $ $ X_A на колона B се равнява на $ \ Фрак $. Можете да го запишете като $ 6 \ Фрак $ а. Нейната дробна част се равнява на $ \ Фрак $

Сред дробни части на данните, за да намерят най-високите, и това е за тази променлива, ще бъде допълнителен натиск. Въпреки това, ние се равни дробна част, така че просто да вземем първия - $ x_C $. Ние изготвяме за променливата $ x_C $ лимит. Тя ще изглежда така:

За всяка друга променлива ще бъде точно същата формула, само с индекси на коефициенти $ р $ $ няма да е C $, както и някои други

Ние ще се разбере какво е това, което. Очевидно е, че $ x_A, x_B, x_C, x_1, x_2, x_3 $ - променливи на нашия проблем. За да намерите коефициенти $ р $ използваме броят на първия ред, тъй като това е мястото, където моментна снимка на нашата променлива $ x_C $. Значение на $ q_C $ е просто дробна част от номера в низ $ x_C $ и колона В. Стойността на свободните членовете на клетката е равна на $ \ Frac = 9 \ Frac $. Очевидно е, че цялата страна е 9, а частична $ \ Фрак $. Следователно $ q_C = \ Фрак $.

$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_A $. Има редица 0, и е очевидно, че неговата частична част също е равен на 0. $ q_ = 0 $
$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_B $. Има няколко $ \ $ Фрак, и е очевидно, че тя също е равна на дробна част от $ \ Фрак $. $ Q _ = \ Фрак $
$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_C $. Има редица 1, и е очевидно, че неговата относителна част е 0. $ q_ = 0 $
$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_1 $. Има няколко $ \ $ Фрак, и е очевидно, че тя също е равна на дробна част от $ \ Фрак $. $ Q _ = \ Фрак $
$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_2 $. Има няколко $ - \ Фрак $. За отрицателни числа, дробна част се определя не толкова малко, че да положителните и равен на разликата на следващата ни цяло число и отрицателно число по-малък от нашия. За редица $ - \ Frac $ след минимално отрицателно число е $ $ 1, и следователно, $ р _ = - \ Frac - (- 1) = \ Frac $
$ Коефициентът $ q_ е дробна част от броя съхраняват в ред $ x_C $, колона $ x_3 $. Има редица 0, и е очевидно, че неговата частична част също е равен на 0. $ q_ = 0 $

Заместването на коефициентите, получаваме друго ограничение:

Това ограничение обаче е под формата на неравенство, а ние имаме всички ограничения под формата на уравнения. Ето защо, това ограничение ще се превърне в уравнението, добавяйки още един неотрицателна променлива $ x_4 $:

Изброени ограничаване на друга линия в таблицата с симплекс, освен това, не забравяйте, че има нова колона $ X_4 $, както и промяна на знака на последния ред - както винаги се прави в началото на работата по метод за Gomory:

Проверете дали сте получили, ние цяло число решение. Да, ще го имаме. Имаме разтворът $ x_A = 6, x_B = 1, x_C = $ 9, и стойността на обективната функция (долния десен клетка на таблицата с обратен знак) е 83, който, между другото, да съвпада с целевата стойност на функцията в оригиналните (не-число) проблеми. Следователно, можем да кажем, че преходът към целочислена стойност не се променя, приходите на компанията. Така че, все пак, това не винаги се случва, и голяма част от приходите на дружеството по време на прехода към цяло число, малко пада.

Така че ние имаме решение с число, тогава проблемът е решен. Ако някоя от променливите отново ще nonintegral, процесът трябва да се повтори - намерете една от променливите на не-цяло число, се създаде допълнително ограничение за него ставайки друг помощен променлива и след това стъпка на симплекс метода, го премахнете от базата. След няколко стъпки, щяхме да имам решение число (както е в този случай).

Ние научихме за решаване на проблемите на производство. и ние сме в състояние да даде резултат, който максимизира печалбата. Въпреки това, ние не смятаме, че остатъчните количества в складове. Това е, разбира се, ние гарантираме, че не се използват повече ресурси, отколкото е, но е възможно, че излишъкът ще остане в склад. Какво обикновено прави компанията, ако те са се формират излишните ресурси в складовете? Всъщност, можете да направите много неща:

Можете да ги продават, и по този начин да увеличи печалбата (целева функция);
Някои ресурси могат да бъдат разменени за други (ако е възможно), и може да бъде, тогава печалбата ще се увеличи;
Можете да мислите за пускането на нов продукт, който консумира само един ресурс, който имаме излишък. Може би тогава нашите печалби увеличение.

Средните производствени проблеми за решаване не дават отговори на въпроси от този вид. Въпреки това, съществуват методи, за да получите тези отговори. Един от тези методи - решение "двойна" проблем. Това ще бъде обсъдено в следващия раздел.

Полезна Свързани

MatByuro е на пазара за решаване на математически задачи в продължение на 11 години. През всичките тези години, ние поддържаме отлична репутация и най-добрите условия, "цена-качество".

Ние предлагаме:
Правилното и подробно решение за разумна цена.

Можете също така да направите следното:

С течение на номер 30000
завършен
заповеди
Цените са разумни и
обоснован
цени
Опитът помага на учениците
в решаване на проблеми
11 години
Credo Quality
отговорност
и уважение
И ние се радваме
изпълнява
вашата поръчка