Дефиниција. Линеарно програмирање (LP) -наука за истражувачки методи и наоѓање екстремни (максимални и минимални) вредности на линеарна функција, на непознатите од кои се наметнуваат линеарни ограничувања.

Оваа линеарна функција се нарекува цел,а се нарекуваат ограничувања кои математички се пишуваат како равенки или неравенки систем на ограничувања.

Дефиниција.Се вика математичкото изразување на целната функција и нејзините ограничувања математички модел на економскиот проблем.

Генерално, математичкиот модел на проблем со линеарно програмирање (LP) е запишан како

со ограничувања:

каде xj- непознато; aij, b i, cjсе дадени константи.

Сите или некои равенки на системот на ограничувања може да се напишат како неравенки.

Математичкиот модел во пократка нотација ја има формата

со ограничувања:

Дефиниција.Изводливо решение (план) на проблем со линеарно програмирање е вектор = ( x 1 , x 2 ,..., x p),задоволување на системот на ограничувања.

Множеството прифатливи решенија го формира регионот на прифатливи раствори (ODD).

Дефиниција.Изводливото решение за кое целната функција ја достигнува својата екстремна вредност се нарекува оптимално решение на линеарното програмирање и се означува опт.

Основно дозволено решение (Х 1 , X 2 ,...,хр , 0, …, 0) е референтно решение, каде r-рангот на системот за ограничување.

Математичкиот модел на проблемот LP може да биде канонски и неканонски.

7. Решавање на задачи за линеарно програмирање со графички метод. Графикони на функции на ограничувања. Линии за нивоа.

Графички метод за решавање на проблеми со линеарно програмирање

Наједноставниот и највизуелниот метод на линеарно програмирање е графичкиот метод. Се користи за решавање на проблеми со LP со две променливи дадени во неканонска форма и многу променливи во канонска форма, под услов да содржат не повеќе од две слободни променливи.

Од геометриска гледна точка, во проблем со линеарно програмирање, се бара таква аголна точка или збир на точки од дозволен сет на решенија, на кои се достигнува линијата на највисокото (пониско) ниво, лоцирана подалеку (поблиску) од другите во насока на најбрз раст.

За да се најде екстремната вредност на функцијата на целта во графичкото решение на проблемите LP, се користи векторот Л() на површината X 1 О 2 , кои ги означуваме . Овој вектор ја покажува насоката на најбрзата промена во функцијата на целта. Со други зборови, векторот е нормалата на линијата на ниво Л()

каде д 1 и д 2 - единечни вектори долж оските Вол 1 и Вол 2 соодветно; на тој начин = (∂L/∂x 1 , ∂L/∂х 2 ). Векторските координати се коефициенти на целната функција L().Изградбата на линијата за ниво ќе биде разгледана детално при решавање на практични проблеми.

Алгоритам за решавање проблеми

1. Ја наоѓаме областа на изводливи решенија за системот на ограничувања на проблемот.

2. Градење вектор .

3. Нацртајте линија на ниво Л 0 , која е нормална .

4. Линијата на ниво ја поместуваме во насока на векторот за задачи до максимум и во спротивна насока , за минимални задачи.

Линијата на ниво се поместува додека не има само една заедничка точка со областа на остварливи решенија. Оваа точка, која го одредува единственото решение на проблемот LP, ќе биде екстремната точка.

Ако се испостави дека линијата на ниво е паралелна со една од страните на ODT, тогаш во овој случај екстремот се достигнува во сите точки на соодветната страна, а проблемот LP ќе има бесконечен број решенија. Демек таков ЛП проблем има алтернативен оптимума неговото решение е дадено со формулата:

Каде 0 ≤ т≤ 1, 1 и 2 - оптимални решенија на аголните точки на ODS.

Проблемот со LP може да биде нерешлив кога ограничувањата што го дефинираат ќе се покажат како контрадикторни.

5. Ги наоѓаме координатите на екстремната точка и вредноста на целната функција во неа.

Пример 3Избор на најдобра опција за ослободување на производот

Компанијата произведува 2 вида сладолед: крем и чоколадо. За производство на сладолед се користат два почетни производи: млеко и филери, чии трошоци за 1 кг сладолед и дневните резерви се дадени во табелата.

Истражувањето на пазарот покажа дека дневната побарувачка за сладолед од путер ја надминува побарувачката на чоколаден сладолед, но не повеќе од 100 килограми.

Покрај тоа, беше откриено дека побарувачката за чоколаден сладолед не надминува 350 килограми дневно. Малопродажната цена на 1 кг кремаст сладолед е 16 рубли, чоколадо - 14 рубли.

Колку од секој вид сладолед треба да произведе фирмата за да ги максимизира приходите од продажба?

Одлука.Означи: x 1 - дневен обем на производство на кремаст сладолед, кг; x 2 - дневно производство на чоколаден сладолед, кг.

Ајде да направиме математички модел на проблемот.

Цените за сладолед се познати: 16 рубли и 14 рубли, соодветно, така што функцијата за цел ќе изгледа вака:

Поставете ограничувања за млеко за сладолед. Неговата потрошувачка за кремаст сладолед е 0,8 кг, за чоколаден сладолед - 0,5 кг. Залиха на млеко 400 кг. Според тоа, првата нееднаквост ќе изгледа вака:

0,8x 1 + 0,5x 2 ≤400 - првата неравенка е ограничување. Останатите неравенки се конструирани на сличен начин.

Резултатот е систем на нееднаквости. која е плоштината на решението на секоја неравенка. Ова може да се направи со замена на координатите на точката O(0:0) во секоја од неравенките. Како резултат, добиваме:

Слика ОАБДЕФ-домен на прифатливи решенија. Го градиме векторот (16; 14). линија на ниво Л 0 е дадена со равенката 16x 1 +14x 2 =Const. Избираме кој било број, на пример бројот 0, потоа 16x 1 +14x 2 =0. На сликата, за правата L 0 е избран позитивен број, кој не е еднаков на нула. Сите линии на нивоа се паралелни една со друга. Нормалниот вектор на линијата на ниво.

Поместете ја линијата на ниво во насока на векторот. излезна точка Л 0 од регионот на изводливи решенија е точката Д, неговите координати се дефинирани како пресек на правите дадени со равенките:

Решавајќи го системот, ги добиваме координатите на точката Д(312,5; 300), во кој ќе има оптимално решение, т.е.

Така, компанијата мора да произведува 312,5 килограми сладолед од путер и 300 килограми чоколаден сладолед дневно, додека приходот од продажба ќе биде 9.200 рубли.

8. Редукција на произволен линеарен проблем за програмирање на главниот проблем.Конвертирање на ограничувањата дадени со неравенки во соодветни равенки.

9.Симплекс метод. Карактеристики и алгоритам на методот, неговата применливост.

За да се реши проблемот со методот симплекс, неопходно е:

1. Наведете метод за наоѓање на оптимално референтно решение

2. Наведете го методот на премин од едно референтно решение во друго, на кое вредноста на целната функција ќе биде поблиску до оптималната, т.е. укажуваат на начин за подобрување на референтното решение

3. Поставете критериуми кои ви дозволуваат навремено да го прекинете набројувањето на референтните решенија за оптималното решение или да донесете заклучок за отсуство на оптимално решение.

Алгоритам на методот симплекс за решавање на проблеми со линеарно програмирање

1. Доведете го проблемот во канонска форма

2. Најдете го иницијалното решение за поддршка со „единична основа“ (ако нема решение за поддршка, тогаш проблемот нема решение, поради некомпатибилноста на системот на ограничувања)

3. Пресметајте ги проценките на векторските проширувања во однос на основата на референтното решение и пополнете ја табелата на методот симплекс

4. Доколку критериумот за единственоста на оптималното решение е задоволен, тогаш решението на проблемот завршува

5. Доколку е исполнет условот за постоење на множество оптимални решенија, тогаш со просто набројување се наоѓаат сите оптимални решенија.

10. Транспортна задача.Дефиниција, видови, методи за изнаоѓање на првичното решение на транспортниот проблем.

Проблемот со транспортот е еден од најчестите проблеми со линеарното програмирање. Неговата цел е да ги развие најрационалните начини и средства за транспорт на стоки, елиминирајќи го прекумерно долгиот, идниот, повторен транспорт.

1. Наоѓање на почетното референтно решение;

2. Проверка на ова решение за оптималност;

3. Премин од едно основно решение во друго.

Наједноставни се таканаречените линеарни детерминистички модели. Тие се дадени во форма на линеарна форма на контролни променливи ( X):

W = a 0 + а 1 x 1 + … + a k x k

под линеарни ограничувања на формата

б 1 j x 1 + б 2 j x 2 + … + b kj x k ³ бј , j = 1,…, q 1 ;

в 1 j x 1 + в 2 j x 2 + … + c kj x k = cj , j = 1,…, q 2 ;

г 1 j x 1 + г 2 j x 2 + … + d kj x k £ г ј , j = 1,…, q 3 .

Вкупен број на ограничувања m = q 1 + q 2 + q 3 може да го надмине бројот на променливи (м> к). Дополнително, условот за позитивност на променливите ( x i ³ 0).

Површината на одговор за линеарниот модел е хиперавион. На пример, разгледајте линеарен модел со две променливи од следнава форма:

W=–2x 1 –3x 2 (2.2)

под следните ограничувања

(2.3)

2x 1 + 3x 2 18 фунти;

x 1 – 4x 2 4 фунти;

–2x 1 + x 2 £ 2;

X 1 ³ 0; x 2 ³ 0.

Валиден опсег (обем на дефиниција) OABCDза моделот (2.2) се формира со ограничувања (2.3) (сл. 2.2). Површината на одговор е рамен многуаголник ОА"Б"Ц"Д"(Сл. 2.2, б).

За одредена релација на ограничување, множеството остварливи решенија може да биде отсутно (празно). Пример за таков сет е прикажан на сл. 2.3. Директно ACи сонцеограничете го опсегот на дозволените вредности од горе. Третото ограничување го отсекува регионот на дозволените вредности подолу од права линија АБ.Така, не постои заедничка област што ги задоволува сите три ограничувања.

Линеарните модели се прилично едноставни и затоа, од една страна, подразбираат значително поедноставување на проблемот, а од друга страна, овозможуваат развој на едноставни и ефективни методи за решавање.

Во проучувањето на DLA, линеарните модели се користат ретко и речиси исклучиво во приближниот опис на проблемите.

Линеарни модели може да се користат за чекор-по-чекор приближување на нелинеарни модели (линеаризација на проблемот). Оваа техника е особено ефикасна кога се проучуваат мали области од проучуваниот простор. Претставувањето на поединечни делови од површината на нелинеарниот одговор со линеарен модел лежи во основата на голема група на методи за оптимизација, таканаречените методи со линеарни тактики.

Проучувањето на линеарни модели не е тешко. Конкретно, влијанието на секоја од променливите врз карактеристиките на моделот на формата

W = a 0 + а 1 x 1 + а 2 x 2 + …+ a k x k

се дава со неговите коефициенти:

, јас = 1,…, к.

Да се ​​најде оптимумот на линеарниот модел Водлучи да разви ефикасен симплекс метод.

Наједноставните модели на трошоци, кои се сметаат како збир на направени трошоци, понекогаш се сведуваат на линеарни.

Пример за таков модел е класиката модел на транспортни трошоци (проблем со транспорт)(Слика 2.4).

Достапно кпроизводни точки
(јас = 1,…, к) и мточки на потрошувачка
(ј = 1,…, м) на некој производ. Количината на производ произведен во секоја кточки на производство, а јас; количината на производот потребна во секоја од нив мточки на потрошувачка, бј.

Еднаквоста на вкупното производство и потрошувачка се претпоставува:

Количина на производ транспортиран од јас-та производна точка во ј-та точка на потрошувачка, еднаква на xij; трошоците за транспорт на единица од овој производ - со ij.

Вкупни трошоци за превоз Со S е дадена линеарен модел:

под следните ограничувања

Линеарните модели вклучуваат и модели во форма на линеарни диференцијални равенки (обични или парцијални деривати).

Линеарна обична диференцијална равенка nри редослед има форма

Почетните услови се напишани како

Линеарна парцијална диференцијална равенка има форма

Моделот, даден како парцијална диференцијална равенка, вклучува почетни и гранични услови (услови на границата на доменот на дефинирање на функцијата F( т)).

2.3. Проучување на наједноставниот математички модел
работа на мотор со гасна турбина

Моторот со гасна турбина (GTE) е главната електрана на модерните авиони.

Шемата GTE ја има формата прикажана на сл. 2.5.

Еве 1 – влезен дифузер; 2 - компресор; 3 - комората за согорување; 4 – турбина;
5 - излезна млазница.

Работниот циклус на GTE ги вклучува следните фази:

1) Наоѓање со брзина Впротокот на воздух низ дифузорот влегува во компресорот.

2) Компресорот, ротирајќи на истото вратило со турбината, го компресира воздухот што влегува во комората за согорување.

3) Горивото (керозин) постојано се вбризгува во комората за согорување, која се меша со компримиран воздух.

4) Гасот создаден од согорувањето влегува во турбината, што ја забрзува до брзина В.

5) Со оваа брзина, гасот се исфрла низ млазницата во атмосферата.

Покрај фактот дека В > В, се создава влечна сила Р, што му овозможува на авионот да лета во атмосферата.

Промената на влечната сила се врши со менување на брзината на вбризгување на горивото во комората за согорување со движење на контролното копче на моторот (THROT). Движењето на гасот до одреден агол d од гасот се врши или рачно од пилотот, или со помош на актуатор според сигналите од ACS во лет. Зголемувањето на вредноста на d потисок предизвикува зголемување на силата Р, а намалувањето е намалување на оваа сила.

GTE е сложен технички систем во кој се одвиваат значителен број физички и хемиски процеси. Моторот е опремен со секакви уреди за автоматизација, системи за вртење и ладење на лопатките на турбината итн. Секако, математичкиот опис на функционирањето на моторот со гасна турбина исто така ќе биде доста тежок, вклучувајќи системи на диференцијални равенки во парцијални деривати, обични диференцијални равенки, трансцендентални функции, алгоритми дигитален системконтрола на моторот. Таквите модели се користат во процесот на дизајнирање на мотори со гасна турбина.

За да се решат проблемите со контролата на летот, се користи поедноставен модел GTE, што е зависност од потисната сила Род аголот d на отстапувањето на гасот на гасот. Процесот на менување на потисната сила е опишан со обична диференцијална равенка од формата:

, (2.11)

каде t > 0 е временската константа на моторот, која, покрај дизајнерските карактеристики, зависи и од температурата на околината, неговата влажност и други надворешни фактори; к[kg/deg] – коефициент на пропорционалност.

Почетниот услов за равенката (2.11) е запишан како

Р(0) = Р 0 . (2.12)

Така, равенката (2.11) заедно со почетната состојба (2.12) е наједноставниот математички модел на моторот со гасна турбина, напишан во форма на обична диференцијална равенка 1-ти ред.

Да се ​​одреди факторот на пропорционалност кСе користат калибрациони криви на зависноста на потисок од аголот на ротација на гасовите, изградени врз основа на експериментални податоци. Тангентата на наклонот на графикот е еднаква на саканиот коефициент.

Интеграцијата на равенката (2.11) со почетната состојба (2.12) овозможува да се открие како силата на потисок се менува со текот на времето (сл. 2.6).

Кога гасот е отклонет, потисокот Рсе зголемува и потоа се стабилизира на одредена гранична вредност, т.е. GTE е инертен објект.

Ограничување на потисокдобиваме од (2.11) кога стапката на нејзината промена е еднаква на нула:

. (2.13)

Време на покачувањезависи од вредноста на временската константа на моторот т. Процесот се смета дека е стабилен кога t = tуста, кога потисокот влегува во таканаречениот петпроцентен коридор на граничната вредност на потисната сила (сл. 2.6). Колку е поголемо t, толку е поинерцијален моторот и, следствено, толку повеќе тустата

На сл. 2.7 го прикажува однесувањето на потисната сила во зависност од аголот на отклонување на гасот при t = 0.5.

Силата на потисок при полетување, кога гасот е отклонет за 10°, достигнува стабилна состојба во третата секунда и достигнува вредност од 3390 kg. Десет секунди по полетувањето, кога гасот е отклонет за 20°, силата на потисок е поставена на 6780 kg, а уште десет секунди подоцна, кога гасот е отклонет за 30°, силата на потиснување е поставена на 10170 kg. Граничната вредност на влечната сила е
14270 кг.

Слични информации.

држава образовна институцијаповисоко

стручно образование

„Московски државен технички универзитет именуван по Н.Е. Бауман“

Филијала Калуга

„Решение на проблемот на линеарно програмирање со методот симплекс“

Целта на работата: да проучи и научи како да го применува симплексот - метод за решавање на директните и двојните проблеми на линеарното програмирање

Теоретски дел.

Математичка формулација на проблемот на линеарно програмирање.

Од практиката на разгледување на проблемите на математичкото програмирање произлегува дека е речиси невозможно да се решат во општа смисла. Препорачливо е да се разгледаат посебни класи (видови) проблеми. За секоја таква класа, можно е да се формулира алгоритам за решение што е прифатлив само за оваа класазадачи. Најразвиени во математичкото програмирање се задачите за линеарно програмирање (LP).

Кај проблемите со линеарно програмирање, функцијата на целта е линеарна, а условите за ограничување содржат линеарни еднаквости и линеарни неравенки. Променливите може или не може да подлежат на барање за ненегативност. Истиот линеарен програмски проблем може да се напише во различни форми. Ако сите ограничувања се во форма на неравенки, тогаш проблемот е запишан во стандардна форма. Ако сите негови ограничувања освен

се еднаквости, тогаш проблемот со линеарното програмирање е запишан во канонска форма.

Општ приказ на проблем со линеарно програмирање

,

Ограничувања:

1. Десните делови од сите ограничувања мора да бидат ненегативни . Доколку некој од коефициентите< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

2. Сите ограничувања мора да се претстават како еднаквости, затоа, при преминување од нееднаквост кон еднаквост, се користи апаратот на дополнителни променливи.

Ако почетните ограничувања ја одредуваат потрошувачката на некој ресурс (знакот ""), тогаш променливите треба да се толкува како остаток или неискористен дел од ресурсот. Во овој случај, тоа е преостаната променлива и се внесува во равенката со знакот „+“.

Ако почетните ограничувања дефинираат вишок на некој ресурс (знак ""), тогаш се воведува вишок променлива знак "-".

Променливи:

Сите променливи мора да бидат не-негативни, т.е. .

Ако променливата нема ограничување на знакот, тогаш таа мора да биде претставена како разлика од две ненегативни променливи: , каде . Таквата замена треба да се користи во сите ограничувања што ја содржат оваа променлива, како и во изразот за целната функција.

Ако таквата променлива падне во оптималното решение, тогаш

Целна функција:

Да се ​​максимизира или минимизира.

Системот на ограничувања во форма на еднаквости и нееднаквости формира конвексно множество - конвексен полиедар. Овој сет може да биде ограничен или неограничен. Целната функција на проблем со линеарно програмирање е исто така конвексна функција. Така, проблемот со линеарното програмирање е посебен случај на конвексниот програмски проблем.

Размислете за системот на ограничувања за линеарно програмирање проблем во форма на еднаквости

(1)

Системот (1) од линеарни равенки е конзистентен ако има барем едно решение. Системот (1) се нарекува редундантен ако една од равенките може да се изрази како линеарна комбинација на другите.

Во системот (1), бројот на променливи (n непознати) е поголем од бројот на ограничувања m. Ќе претпоставиме дека рангот на овој систем е еднаков на m (системот не е излишен) и тој систем (1) е конзистентна.Тогаш m променливите од нивниот вкупен број формираат основни променливи, а другите променливи се нарекуваат неосновни.Ако системот на равенки има решение, тогаш тој има и основно решение. се нарекува допуштена ако сите негови компоненти се ненегативни.Ако системот од линеарни равенки има допуштено решение, тогаш тој има и основно допуштено решение. од сите изводливи решенија на системот (1) е конвексно множество, т.е. решенијата на проблемот со линеарното програмирање се конвексни. Бидејќи ова множество е формирано од рамнини (хиперрамнини), има форма на конвексен полиедар. Основното изводливо решение одговара на екстремната точка на конвексниот полиедар (неговите лица или теме) постои оптимално решение за проблем со линеарно програмирање, тогаш постои основа е оптимално решение.

Целната функција на проблем со линеарно програмирање е равенката на рамнина (или хиперрамнина за повеќе од три променливи). Макс или минимална вредностцелната функција на линеарно програмски проблем достигнува или теме на конвексен полиедар или едно од неговите лица. Така, решението (решенија) на проблемот со линеарното програмирање лежи на темињата на конвексниот полиедар, а за да се најде, потребно е да се пресметаат вредностите на целната функција на темињата на конвексниот полиедар, утврдени со услови-ограничувања на проблемот.

Решавање на проблем со линеарно програмирање со графички метод.

Тешкотијата за изградба на математички модел лежи во идентификацијата на променливите и последователното претставување на целта и ограничувањата во форма на математички функции на овие променливи. Ако моделот содржи само две променливи, тогаш проблемот со линеарното програмирање може да се реши графички. Во случај на три променливи, графичкото решение станува помалку визуелно, а со поголема вредност на променливите тоа е дури и невозможно. Сепак, графичкото решение овозможува да се извлечат заклучоци кои служат како основа за развој на општ метод за решавање на проблем со линеарно програмирање.

Првиот чекор во користењето на графичкиот метод е геометриски да се прикажат изводливите решенија, т.е. конструкција на доменот на прифатливи решенија (ODD.), во кој сите ограничувања на моделот се истовремено задоволени. Кога ќе се добие графичко решение, променливата се исцртува по хоризонталната оска, а - по вертикалната. При формирањето на SDE потребно е да се спречи прием на неприфатливи решенија кои се поврзани со потребата да се исполни условот за ненегативност на променливите. Пред изградбата потребно е да се одредат квадрантите во кои ќе се наоѓа ОДР. Квадрантите се дефинирани со знаците на променливите и . Условите за ненегативност на променливите и ограничување на опсегот на нивните дозволени вредности до првиот квадрант. Ако променливата не е ограничена во знакот, тогаш областа е ограничена со првиот и вториот квадрант, ако , тогаш - со првиот и четвртиот квадрант. Другите граници на просторот за решение на рамнината , се прикажани со прави линии конструирани според равенките за ограничување, под услов знакот да се замени со знакот "=". Во овој случај, мора да се земе предвид следново: десните страни на сите ограничувања мора да бидат ненегативни . Доколку има некакво ограничување< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

Како резултат на конструкциите се добива многуаголник кој го одредува просторот на решенијата. Ако едно од ограничувањата има знак „=", тогаш ODD дегенерира во сегмент.

Во секоја точка што припаѓа на плоштината или границите на полигонот на решението, сите ограничувања се исполнети, така што сите решенија што одговараат на овие точки се валидни. Просторот за решение содржи бесконечен број такви точки, и покрај тоа, можно е да се најде оптималното решение. За да го направите ова, неопходно е да се изгради во рамнината на променливи, градиентот на целната функција. Одредувањето на оптималната точка зависи од проблемот што треба да се реши.

Ако во функцијата на целта е дефиниран проблем за максимизирање, тогаш оптималната точка ќе биде лоцирана во насока на зголемување на градиентот, ако е дефиниран проблемот за минимизирање, тогаш во насока на намалување на градиентот на целната функција. За да ја одредиме оптималната точка, целната функција ќе ја поместиме во насока на зголемување (намалување) на градиентот додека не се префрли во регионот на неприфатливи решенија.

По наоѓањето на оптималната точка во просторот на решението, се одредуваат нејзините координати и вредноста на целната функција во неа. Исправноста на изборот на оптималната точка може да се провери со пресметување на функцијата на целта на темињата на растворниот полиедар. Во LLP, доменот на изводливи решенија е секогаш конвексно множество, т.е. такво множество што, заедно со кои било две точки кои припаѓаат на ова множество, сегментот што ги поврзува овие две точки исто така припаѓа на истото множество. Секоја функција се зголемува на најбрз начин во насока на нејзиниот градиент.

Решавање на проблем со линеарно програмирање со методот симплекс.

директна задача.

Размислете за линеарен проблем за програмирање во канонска форма:

Најдете го максимумот (минимумот) на функцијата под услови

Се претпоставува дека постои решение за овој проблем. За да се најде оптималното решение, потребно е да се најдат прифатливи основни решенија и од нив да се избере оптималното основно решение.

Симплекс методот е алгебарски метод за решавање на проблеми со линеарно програмирање. Во текот на пресметките, темињата на полиедарот на растворот (ODP) последователно се заобиколуваат со проверка на условите за оптималност на секое теме. Покрај тоа, секоја транзиција кон соседното теме е придружена со подобрување на целната функција.

Пресметковни постапки на методот симплекс.

Со графичкиот метод на решавање на LLP, оптималното решение секогаш одговара на една од аголните (екстремните) точки на просторот за решение. Овој резултат лежи во основата на конструкцијата на методот симплекс. Симплекс методот нема видливост на геометриски приказ на просторот за решение.

Симплекс методот имплементира подреден процес во кој, почнувајќи од некоја почетна дозволена аголна точка, се прават последователни премини од една допуштена крајна точка до друга додека не се најде оптимална точка на решение.

Да означиме: - вкупниот број на променливи во LLP, претставени во канонска форма; - број на почетни променливи; - бројот на ограничувања, - бројот на дополнителни променливи, потоа .

Секое теме на полиедарот на растворот има - не-нула променливи и () - нула променливи.

Променливите кои не се нула се нарекуваат основни, нула променливите се нарекуваат неосновни.

Системот на еднаквости го дополнуваме со еднаквоста на функцијата на целта, додека претпоставуваме дека тоа е основна променлива која е секогаш присутна во основата за кое било теме.

За да се добие решение, се составува почетна прифатлива основа, во која основните променливи мора да бидат претставени како единечни вектори. Ова значи дека равенките што претставуваат дадено теме мора да ја вклучат секоја основна променлива само во еден ред со фактор 1.

При изборот на почетна прифатлива основа за составување на симплекс табела, на првиот чекор CT(0), почетните променливи се изедначуваат на нула и се неосновни, меѓу дополнителните воведени променливи се избираат променливи со коефициенти еднакви на еден. Променливите во равенствата (2) - (4) се основни и влегуваат во линијата - со коефициенти еднакви на 0. За пополнување на симплекс табелата потребно е да се претвори функцијата на цел во формата . Така, конечно добиваме:

При составување на симплекс табела, се следат следниве правила:

најлевата колона ги содржи основните променливи и ;

најдесната колона ги содржи десните делови од ограничувањата;

Првата линија ги содржи променливите по одреден редослед:

прво, потоа не-основните променливи, основните променливи се наоѓаат во последните колони пред десната страна (IF). Коефициентите ги запишуваме во CT(0):

							АКО
	1			0	0	0	0
	0			1	0	0
	0			0	1	0
	0			0	0	1

Оптималноста на кое било од темињата се одредува со коефициентите за не-основните променливи во редот на тековната симплекс табела:

За проблемот со максимизирање, ова теме е оптимално ако сите коефициенти за не-основните променливи во редот – се ненегативни (>0);

За проблемот со минимизирање, ова теме е оптимално ако сите коефициенти за неосновните променливи во редот - се непозитивни (< 0).

Ако во проблемот на максимизирање (минимизирање) една неосновна променлива во редот – има коефициент<0(>0), тогаш моменталната точка не е оптимална и неопходно е да се смени основата. За да го направите ова, изберете не-основна променлива која има најнегативен (позитивен) коефициент во линијата -. Избраната не-основна променлива ќе биде вклучена во новата основа, затоа се нарекува вклучена променлива. Основната променлива што ќе се извади од основата се нарекува променлива на исклучување.

Исклучената променлива ќе биде основната променлива која прво ќе се претвори во „0“ кога ќе се пресели во соседно теме откако ќе ја внесе вклучената променлива.

Колоната на вклучената променлива ќе се нарекува колона за решавање.

Низата од исклучената променлива ќе се нарекува низа за решавање.

Пресекот на дозволена колона и ред дефинира дозволен елемент (RE).

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

поделете ги десните делови од сите основни променливи (освен редот) со соодветните позитивни коефициенти на колоната за решавање;

изберете го најмалиот од добиените соодноси.

Не е дозволено делење со „0“ и негативна вредност, бидејќи тоа доведува до отсуство на пресечно теме или до теме надвор од ODT.

За да се преселите во соседното теме, потребно е да се формира преодна матрица B(0), која ќе ја одреди врската помеѓу ST(0) и ST(1): ST(1) = B(0) ST(0).

За произволна квадратна матрица со димензија n, која има единечни орти како (n - 1) колони, распоредени во согласност со единечните орти на идентитетската матрица и една произволна колона со ненулти елемент на главната дијагонала, инверзна матрицае според следново правило:

Секој елемент од j-колоната е поделен со RE и го менува знакот во спротивен, освен елементот што решава.

Вештачка почетна основа. М - метод.

Ако почетното ограничување е напишано во форма на еднаквост „=" или има знак „“, тогаш невозможно е веднаш да се добие прифатливо почетно основно решение, бидејќи при пишувањето на проблемот во стандардна форма, по воведувањето дополнителни променливи, варијантата може да испадне кога добиените равенки не дозволуваат да се формира почетна прифатлива основа во форма на единечни вектори.

Во овој случај, за да се најде почетната дозволена основа, се воведуваат дополнителни вештачки променливи. Вештачките променливи не се поврзани со содржината на задачата, нивното воведување е дозволено само ако соодветната шема за пресметка ќе обезбеди оптимално решение во кое сите вештачки променливи ќе бидат еднакви на нула.

Променливите R ја одредуваат почетната прифатлива основа од гледна точка на можна понатамошна транзиција кон едно од темињата на ODT. За употреба на вештачки променливи во функцијата на целта се воведува казна М. Во проблемот на максимизирање на М негативна (М<<0), в задаче минимизации М положительное (М>>0).

Својство M: При собирање (одземање) со која било конечна вредност што одредува која било вредност што може да ја земе секоја од променливите на оригиналниот LLP, нејзината вредност (променлива М) не се менува, имено,

Формула (1.2), ограничувања на ненегативноста на променливите (да, не) - формула (1.3) (1.1) i = 1, ... m (1.2) (1.3) Алгоритмот за решавање на линеарни програмски проблеми бара нивно доведување во канонска форма кога целната функција ...

Во пракса, ограничувањата во проблем со линеарно програмирање честопати не се дадени со равенки, туку со неравенки.

Дозволете ни да покажеме како може да се помине од проблем со ограничувања на нееднаквост на главниот проблем на линеарното програмирање.

Нека постои линеарен проблем за програмирање со променливи, во кој ограничувањата наметнати на променливите имаат форма на линеарни неравенки. Во некои од нив, знакот за нееднаквост може да биде и други (вториот тип се сведува на првиот со едноставна промена на знакот на двата дела). Затоа, ги поставивме сите ограничувања за нееднаквост во стандардна форма:

Потребно е да се најде таков сет на ненегативни вредности што би ги задоволиле нееднаквостите (4.1) и, дополнително, би ја минимизирале линеарната функција:

Од вака поставениот проблем, лесно може да се премине на главниот проблем на линеарното програмирање. Навистина, ја воведуваме ознаката:

каде се некои нови променливи, кои ќе ги наречеме „дополнителни“. Според условите (4.1), овие дополнителни променливи, како што треба да бидат, мора да бидат ненегативни.

Така, се соочуваме со проблемот на линеарно програмирање во следната формулација: да се најдат такви ненегативни вредности на променливите што го задоволуваат системот на равенки (4.3) и во исто време да се минимизира линеарната функција на овие променливи:

Како што можете да видите, пред нас во чиста форма го имаме главниот проблем на линеарното програмирање (LPP). Равенките (4.3) се дадени во веќе решена форма во однос на основните променливи, кои се изразени во смисла на слободни променливи. Функцијата L се изразува само во однос на „почетните“ променливи (коефициентите на „дополнителните“ променливи во неа се еднакви на нула).

Така, проблемот на линеарно програмирање со ограничувања на нееднаквост го намаливме на главниот проблем на линеарното програмирање, но со поголем број на променливи отколку што беше првично во проблемот.

Пример 1 Постои линеарен проблем со програмирање со ограничувања за нееднаквост: најдете ненегативни вредности на променливите што ги задоволуваат условите

и минимизирање на линеарната функција

Потребно е овој проблем да се намали во форма на OLP.

Одлука. Неравенките (4.4) ги внесуваме во стандардната форма;

Воведуваме дополнителни променливи:

Задачата е да се најдат не-негативни вредности на променливите

задоволување на равенките (4.6) и минимизирање на линеарната функција (4.5).

Покажавме како може да се премине од проблем со линеарно програмирање со ограничувања на нееднаквост на проблем со ограничувања за еднаквост (ELP). Обратна транзиција е секогаш можна - од LLP до проблемот со ограничувањата на нееднаквоста. Ако во првиот случај го зголемивме бројот на променливи, тогаш во вториот случај ќе го намалиме, елиминирајќи ги основните променливи и оставајќи ги само слободните.

Пример 2. Постои линеарен проблем со програмирање со ограничувања за еднаквост (OLP):

и функцијата да се минимизира

Потребно е да се напише како линеарен проблем за програмирање со ограничувања на нееднаквост.

Одлука. Бидејќи , избираме две од променливите како слободни. Забележете дека променливите не можат да се изберат како слободни, бидејќи тие се поврзани со првата од равенките (4 7): вредноста на едната од нив е целосно одредена од вредноста на другата, а слободните променливи мора да бидат независни

Од истата причина, невозможно е да се изберат променливи како слободни (тие се поврзани со втората равенка). Избираме како слободни променливи и ги изразуваме сите останати во однос на нив:

Бидејќи условите (4 9) може да се заменат со неравенки:

Да го пренесеме изразот на линеарната функција L на слободните променливи Замена во L наместо и нивните изрази (4.9). добие.

МОДЕЛ ЗА ЛИНЕАРНО ПРОГРАМИРАЊЕ

1 Математички опис на моделот на линеарно програмирање

2 Методи за имплементација на модели на линеарно програмирање

3 Проблем со двојно линеарно програмирање

Модел на линеарно програмирање(LP) се одвива ако во проучуваниот систем (објект) ограничувањата на променливите и целната функција линеарна.

LP моделите се користат за решавање на два главни типа на применети проблеми:

1) оптимално планирање во која било сфера на човековата активност - социјална, економска, научна, техничка и воена. На пример, со оптимално планирање на производството: дистрибуција на финансиски, работни и други ресурси, снабдување со суровини, управување со залихи итн.

2) транспортниот проблем (пронаоѓање на оптимален план за различни видови превоз, оптимален план за распределба на различни средства по предмети за различни намени итн.)

МАТЕМАТИЧКИ ОПИС НА МОДЕЛОТ ЗА ЛИНЕАРНО ПРОГРАМИРАЊЕ

Потребно е да се најдат ненегативни вредности на променливите

задоволувачки линеарни ограничувања во форма на еднаквости и неравенки

,

каде - дадени броеви,

и обезбедување на екстрем на линеарната целна функција

,

каде се дадени броеви, што се пишува како

Прифатливо решениесекое множество се нарекува , задоволувајќи ги условите.

Домен на прифатливи решенијае збир на сите допуштени решенија.

Оптимално решение
, за што .

Забелешки

1. Намалениот ЛП модел е генерален. Исто така има стандардени канонскиформи на LP модели.

2. Услови за постоењеимплементација на LP моделот:

– збирката на допуштени решенија не е празна;

– целна функција ограничен со (барем од горе кога се бара максимум и од долу кога се бара минимум).

3.LP се заснова на две теореми

Теорема 1. Еден куп Г, дефиниран со системот на ограничувања на формата, е конвексно затворено множество ( конвексен полиедарво со аголни точки - врвови.)

Теорема 2. Линеарна форма , дефиниран на конвексен полиедар

ј=1,2,…,с

i=s+1,s+2,…, м,

достигнува екстрем на едно од темињата на овој полиедар.

Оваа теорема се нарекува теорема на линеарна форма екстремна.

Во согласност со теоремата на Вајерштрас, оптималното решение е единствено и е глобален екстрем.

Постои општ аналитички пристапдо имплементација на LP моделот - методот симплекс. При решавање на проблеми со линеарно програмирање, доста често нема решение. Ова се случува поради следните причини.

Ајде да ја илустрираме првата причина со пример.

За таквата причина велат дека ограничувањата се неконзистентни. Доменот на прифатливи решенија е празното множество.

Втората причина се коментира со следниот пример:

Во овој случај, областа на изводливи решенија не е ограничена одозгора. Областа на прифатливи решенија не е ограничена.

Следејќи ги традициите на линеарното програмирање, на проблемот LP ќе му дадеме економска интерпретација. Дозволете ни да имаме мвидови ресурси. Број на тип ресурс једнакви . Овие ресурси се потребни за производство nвидови на стоки. Дозволете ни да ја означиме количината на овие добра со симболите соодветно. Тип на ставка јастрошоци . Производство на стоки тип јастреба да се ограничи на соодветно. За производство на единица стока од типот јастип на потрошен ресурс ј. Неопходно е да се одреди таков план за производство на стоки ( ) така што нивниот вкупен трошок е минимален.

Проблемите со линеарното програмирање што се користат за оптимизирање на функционирањето на реалните објекти содржат значителен број променливи и ограничувања. Ова го оневозможува нивното решавање со графички методи. Со голем број на променливи и ограничувања се користат алгебарски методи кои се засноваат на итеративни пресметковни процедури. Во линеарното програмирање, развиени се многу алгебарски методи кои се разликуваат по начините на конструирање на почетно изводливо решение и во условите за премин од една итерација во друга. Сепак, сите овие методи се засноваат на општи теоретски одредби.

Општоста на главните теоретски одредби води до фактот дека алгебарските методи за решавање на проблеми со линеарно програмирање во голема мера се слични едни на други. Конкретно, речиси секој од нив бара прелиминарно намалување на проблемот со линеарно програмирање во стандардна (канонска) форма.

Алгебарските методи за решавање на проблемот ЛП започнуваат со негово намалување на стандардна (канонска) форма:

,

,

јас=1,..,n;ј=1,..,м.

Секој проблем со линеарното програмирање може да се сведе на стандардна форма. Споредбата на општиот модел со канонскиот модел ни овозможува да заклучиме дека за да се сведе проблемот на LP на стандардна форма, потребно е, прво, да се премине од системот на нееднаквости на еднаквости и второ, да се трансформираат сите променливи така што дека не се негативни.

Преминот кон еднаквости се врши со додавање на ненегативна преостаната променлива на левата страна на ограничувањата за неравенки од типот, и одземање од левата страна на ненегативна вишок променлива за неравенки од типот. На пример, нееднаквост кога се преминува во стандардна форма се трансформира во еднаквост , и нееднаквоста - до еднаквост . Во овој случај, и резидуалната променлива и вишокот променлива се ненегативни.

Се претпоставува дека десната страна на неравенките е ненегативна. Во спротивно, ова може да се постигне со множење на двете страни на неравенката со „-1“ и менување на неговиот знак во спротивен.

Ако во оригиналниот проблем со линеарно програмирање променливата не е ограничена во знак, таа може да се претстави како разлика на две ненегативни променливи , каде .

Важна карактеристика на променливите е дека за секое допуштено решение само едно од нив може да земе позитивна вредност. Ова значи дека ако , тогаш и обратно. Затоа, може да се смета како резидуална, но - како редундантна променлива.

ПримерНека е даден линеарен проблем за програмирање:

,

.

Треба да го доведете во стандардна форма. Забележете дека првата нееднаквост на оригиналниот проблем го има знакот , затоа, неопходно е да се воведе преостанатата променлива во неа. Како резултат на тоа, добиваме.

Втората неравенка има предзнак и за трансформација во стандардна форма бара воведување на редундантна променлива , откако ќе ја извршиме оваа операција, добиваме .

Исто така, променливата не е ограничена со знак. Затоа, и во целната функција и во двете ограничувања, таа мора да се замени со разликата . Откако ја извршивме замената, добиваме линеарен проблем за програмирање во стандардна форма, еквивалентен на оригиналниот проблем:

.

Проблемот на линеарното програмирање, запишан во стандардна форма, е проблем на наоѓање на екстремот на целната функција на множеството вектори кои се решенија на системот на линеарни равенки, земајќи ги предвид условите на ненегативност. Како што е познато, системот на линеарни равенки може да нема решенија, да има едно решение или да има бесконечен број решенија. Оптимизација на целната функција е можна само ако системот има бесконечнамногу решенија. Системот на линеарни равенки има бесконечен број решенија ако е конзистентен (рангот на главната матрица е еднаков на ранг на продолжената) и ако рангот на главната матрица е помал од бројот на непознати.

Нека рангот на матрицата на системот за ограничување е еднаков на м. Ова значи дека матрицата има најмалку еден минор мредот не е еднаков на нула. Без губење на општоста, можеме да претпоставиме дека малолетникот се наоѓа во горниот лев агол на матрицата. Ова секогаш може да се постигне со промена на нумерирањето на променливите. Ова не-нулта ранг-мала мсе нарекува основа. Ајде да направиме систем од прво мравенки на системот, пишувајќи го на следниов начин:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .