Gomory метод, програмиране число

Икономически и геометрична интерпретация на проблема с число програмиране. Екстремни задачи променливи, които целочислени числа, наречени на проблема с число програмиране.

Математическият модел на проблема с число програмен обективната функция, и системата за функция за ограничаване могат да бъдат линейни, нелинейни и се смесва. Само случаят, когато целевата функция и ограничение системата на проблема са линейни.

В магазина на компанията реши да инсталирате допълнително оборудване, за които разпределят областта на настаняване. Закупуването на оборудване, компанията може да похарчи 10 хиляди. Разтрийте. докато той може да си купи два вида оборудване. Наборът от оборудване I вид струва 1000 рубли. и II тип - 3000 рубли. Придобиване на един набор от тип оборудване мога да увеличи продукцията на всяка работна смяна от 2 единици. и един набор от тип II оборудване - 4 броя. Знаейки, че един комплект оборудване трябва да въведа 2 м 2 площ и оборудване тип II - 1 м 2 площ да се определи набор от допълнително оборудване, което дава възможност да се увеличи максимално изход

Решение. Ние изграждане на математически модел на проблема. Да приемем, че компанията ще придобие x1 комплекта оборудване тип I и II комплекта оборудване тип. Тогава x1 на променливи и трябва да отговарят на следните неравенства:

Ако компанията ще придобие определен брой оборудване, общото увеличение на продукцията ще бъде

В своята икономическа съдържание променливи x1 и могат да вземат само неотрицателни цели числа, т.е.. Д.

Така стигаме до следния математически проблем: намиране на максимална стойност на линейната функция (71), когато изпълнението на условието (70), (72) и (73). От неизвестното могат да вземат само целочислени стойности, тогава проблемът (70) - (73) е проблем на число програмиране. Тъй като броят на неизвестни на проблема е двустранен, проблемът може да се намери с помощта на неговата геометрична интерпретация. За тази предимно изграждане на многоъгълник на разтвори, състоящи се в определяне на максималната стойност на линейната функция (71), при условията, (70) и (72) (фиг. 11). Координатите на всички точки на разтвори многоъгълник OAEVS отговарят на система от линейни неравенства (70) и състоянието на не-негативизъм на променливите (72). Въпреки това, състояние (73), т. Е. пълнотата състояние променливи координати отговарят само 12 точки, маркирани на фиг. 11. За да се намери точката, чиито координати са определени от решаването на първоначалния проблем, сменете полигон полигон OABC OKEMNF. съдържащ всички валидни точки с целочислени координати и такива, че координатите на всеки връх са цели числа. Така че, ако се намери точката на максимална функция (71) на полигон OKEMNF. координатите на тази точка и да се определи оптималната програма на проблема.

За да направите това, ние се конструира вектор и линия, преминаваща през решенията на полигон OKEMNF (номер 12 е произволна). Изграждане на Direct се движи в посока на вектора, стига да не минава през последната точка общо с неговите полигон данни. Координатите на тази точка и да определи най-добрият план, и обективна стойност на функция е в максимална степен.

В този случай, желаната точка Д (1, 3), в която целевата функция приема максималната стойност В. е последователно, координатите на точка Е се определя оптимална проблем (70) - (73). В съответствие с този план, компанията трябва да закупите един комплект оборудване тип 1 и II три комплекта оборудване тип. Това ще осигури на компанията с нейните съществуващи ограничения по отношение на производствените мощности и финансира максималното увеличение на продукцията от 14 единици. на смяна.

За работа може да се използва, за да твърдят, механизми. Изпълнение-тото механизъм, когато j- тата работа е. Ако приемем, че всеки механизъм може да се използва само за едно работно място, както и всяка работа може да се извършва само от един механизъм, механизмите за осигуряване установят, че може да осигури най-доброто представяне. Построява се математически модел на проблема.

Решение. Представяме на променливата Xij. чиято стойност е 1, ако се използва J- та механизъм когато i- та операция, и е 0 в противен случай. Тогава условията за използване на всеки механизъм е само една работа може да се изрази чрез уравнения

и условията на работа е само един механизъм - на равенства

Следователно, проблемът е да се определят стойностите на неизвестни, които отговарят на системата от уравнения (74) и (75) и състоянието (76), при което максималната стойност на функцията

Формулираното проблем е проблем на число програмиране.

Определяне на оптималния план число проблема с програмиране. Помислете за проблема с число програмиране, в която и двете целевата функция и функция в системата на ограничения са линейни. В тази връзка, ние формулираме основния проблем на линейното програмиране, в която променливи могат да целочислени числа. Най-общо казано, този проблем може да се запише по следния начин: намерите максимума на функцията

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

Gomory метод. Намиране на решения на число програмиране проблем с Gomory започват с определение на симплекс метод оптималната програма на проблема (78) - (80), без да цели числа. След като се установи, този план, браузвате нейните компоненти. Ако има, наред с компонентите на дробни числа, намерена на плана е най-добрият план за число програмиране проблем (78) - (81). Ако в оптималния план на проблем (78) - (80) вариабилен е фракционна стойност, тогава системата от уравнения (79) се добавя към неравенството

и да се намери решение на проблема (78) - (80) (82).

В (82), и - трансформираните референтни стойности и стойностите, които са взети от последния симплекс маса, и - фракции от цели числа (дробна част от редица добре разбрани малката неотрицателно цяло число б такова, че разликата между а и б е цяло число). Ако в оптималния план на проблем (78) - (80) фракционни стойности отнеме няколко променливи, допълнително неравенство (82), се определя от най-голямата фракция.

Ако по отношение на резултатите от (78) - (80), (82) променливите са частични стойности, след това отново се добавя един допълнителен ограничение и процеса на изчисляване се повтаря. Чрез краен брой повторения, или да получите най-добрия план за число програмиране проблем (78) - (81), или да го настроите нерешим.

Ако потреблението е цяло число (81) се прилага само за определени променливи, такива задачи се наричат ​​смесени число. Те са също така в съответствие решение за тези проблеми, всеки от които се добива от предишния чрез въвеждане на допълнителни ограничения. В този случай, такова ограничение е на формата

които се определят от следните отношения:

1), който може да приеме не-цели числа,

2), който може да се предположи, целочислени числа,

От гореизложеното следва, че в процеса на определяне на оптималното план число програмиране проблем метода на Gomori включва следните стъпки.

1. Използване на метода на симплекс, намери решение на проблема (78) - (80) без да се вземат предвид изискванията на променлива цяло число.

2. Долива допълнително ограничение за променливата в оптималния план на проблема (78) - (80) има максимална относителна стойност, и оптималното план на проблем (78) - (81) трябва да е цяло число.

3. Използване на двойна симплекс метод. намери решение на проблема, който се получава от проблем (78) - (80) в резултат на допълнителни ограничения присъединяване.

4. Ако е необходимо, да представлява друго допълнително ограничение и да продължи процеса на повторение, докато оптималната проблем (78) - (81) или да се установи тяхната неразтворимост.

Gomory метод, за да се намери максималната стойност на функцията

Дайте геометрична интерпретация на решението.

Решение. За да се определи оптималната програма на проблема (86) - (89) за първи път се намери оптималната програма на проблема (86) - (88) (Таблица 22.).

Сега ние откриваме, максималната стойност на (86) при условията (87), (88) и (90) (Таблица. 23).

се вижда от Таблица 23, че първоначалната проблема с число програмиране е оптималния план w Ith това отношение и обективна стойност на функцията е равна. Нека ни даде геометрична интерпретация на решението. Обхватът на допустимите решения на проблема (86) - (88) е OABCD многоъгълник (Фигура 12).. Фиг. 12 показва, че максималната стойност на целевата функция поема точка С (19/2; 7/2), т д .. X = (19/2, 7/2, 0, 0, 34) е оптималният план. Това е веднага ясно от таблица 22. От X = (19/2, 7/2, 0, 0, 34) не е оптимално програма на (86) - (89) (и номера - частични), се въвежда допълнително ограничение , С изключение от това и заместване на съответните стойности на тези уравнения система ограничения (87), ние получаваме от спирателен триъгълник многоъгълника на OABCD EFC.

Както се вижда от фиг. 12, областта на възможни решения резултат проблем е OABEFD многоъгълник. В точка Е (9; 4) на многоъгълника на обективната функция на проблема се максималната стойност. Тъй като координати на точки Е - числа и неизвестното и получават целочислена стойност, когато заместен в уравнение (87) стойности и оптималното план е проблемът (86) - (89). От това следва, от масата 23.

Gomory метод, за да се намери решение на проблема е да се определи максималната стойност на функцията

Дайте геометрична интерпретация на решението.

Решение. Формулиране на проблема пренаписана, както следва: намери максималната стойност на функцията

Проблемът (95) - (98) е неразделна част, тъй като променливите и може да приеме не-целочислени стойности.

Виж zadayai разтвор метод симплекс (95) - (97) (Таблица 24).