Общ изглед на модела на линейно програмиране. Форми на линейни математически модели и тяхното преобразуване. Формулиране на основните видове задачи на LP, изграждане на техните математически модели

АГЕНЦИЯ ЗА ФЕДЕРАЛНО ОБРАЗОВАНИЕ

ФГОУ ПО „ПСКОВСКИ КОЛЕДЖ НА СТРОИТЕЛСТВОТО И ИКОНОМИКАТА“

Тема "Математически методи"

Задача линейно програмиране

Курсова работа

Студентска група 315-ПО

Андреев Дмитрий Александрович

Надзорник на курсовата работа

Василиева Наталия Анатолиевна

Псков 2009

Въведение

Глава Ι Линейно програмиране

§ 1 Обща формулировка на задачата за линейно програмиране

§ 2 Математически модел на задачата за линейно програмиране

§ 3 Канонична форма на задачата за линейно програмиране

Глава ΙΙ Решаване на проблем с помощта на симплексния метод

§ 1 Изложение на проблема

§ 2 Съставяне на математически модел на задачата

§ 3 Алгоритми за решаване на задачата по симплексния метод

§ 4 Конструиране на първоначалното опорно решение по метода на Гаус

§ 5 Решение на проблема

Заключение

Литература

Въведение

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

В задачите за линейно програмиране критерият за ефективност и функциите в системата от ограничения са линейни.

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

В много икономически модели връзката между постоянни и променливи фактори може да се счита за линейна.

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

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

Глава Ι Линейно програмиране

§ 1 Обща формулировка на задачата за линейно програмиране

Линейното програмиране е клон на математическото програмиране, който изучава методи за решаване на екстремни проблеми, които се характеризират с линейна връзка между променливи и линейна целева функция. За решаване на задачи за линейно програмиране се съставя математически модел на задачата и се избира метод на решение.

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

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

§ 2 Математически модел на задачата за линейно програмиране

Преди да решим задачата, съставяме нейния математически модел.

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

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

1. Изберете променливи на задачата.

Променливите на задачата са количествата

Които напълно характеризират икономическия процес, описан в задачата. Обикновено се записва като вектор X = () Освен това )

2. Създайте система за ограничаване на проблема.

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

V общ изгледсистемата е написана като

3. Определете целевата функция.

Целевата функция е функция Z (X), която характеризира качеството на задачата, чийто екстремум трябва да бъде намерен. По принцип целевата функция се записва Z (X) =

тогава. математическият модел е да се намерят променливите на проблема

отговарящи на системата от ограничения:

и условието за неотрицателност

0 (j =), което осигурява екстремума на целевата функция Z (Y) =

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

Наборът от възможни решения формира областта на възможните решения на проблема (ODS).

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

§ 3 Канонична форма на задачата за линейно програмиране

Математическият модел на задачата трябва да има канонична форма.

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

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

преминаваме от неравенства към уравнение, както следва: от лявата страна на неравенствата въвеждаме допълнителна променлива с коефициента (+1) за неравенството (

) и (-1) за неравенство () допълнителни променливи не са наложени целеви неотрицателности, след което се заменя с разликата на две неотрицателни променливи, тоест: = - (

Общ изглед на каноничната форма:

Глава ΙΙ Решаване на проблем с помощта на симплексния метод

Симплексният метод е метод за последователно подобряване на плана (решението), най -ефективният и се използва за решаване на всеки проблем с линейното програмиране.

Името на метода е от латинското simplecx - просто защото от първоначалната област на възможните решения на проблема най -простият изглед... Идеите на метода са предложени от руския математик Л. В. Контарович. през 1939 г. и след това тази идея е разработена и развита от Й. Данциг през 1949 г.

Симплексният метод позволява в краен брой стъпки или да се намери оптималното решение, или да се докаже, че то не съществува.

§ 1 Изложение на проблема

Компанията използва 3 вида машини в производствения процес: Ι, ІΙ, ІVІ. В този случай се консумират суровини, трудови ресурси и се вземат предвид режийните разходи.

Всеки проблем с линейно програмиране може да бъде редуциран до проблем с линейно програмиране в канонична форма. За да направите това, в общия случай трябва да можете да редуцирате проблема за максимизиране до проблема за минимизиране; преминете от ограниченията на неравенството към ограниченията на равенството и заменете променливите, които не се подчиняват на условието за отрицателност. Увеличаването на някаква функция е еквивалентно на минимизиране на същата функция, взета с противоположния знак и обратно.

Правилото за свеждане на проблема с линейно програмиране до каноничната форма е следното:

• ако в първоначалния проблем е необходимо да се определи максимума линейна функция, тогава трябва да смените знака и да потърсите минимума на тази функция;
• ако дясната страна на ограниченията е отрицателна, тогава това ограничение трябва да се умножи по -1;
• ако има неравенства сред ограниченията, то чрез въвеждане на допълнителни неотрицателни променливи те се трансформират в равенства;
• ако някаква променлива x jняма ограничения за знаци, след това се заменя (в целевата функция и във всички ограничения) с разликата между две нови неотрицателни променливи:
  x 3 = x 3 + - x 3 - , където x 3 +, x 3 - ≥ 0 .

Пример 1... Редуциране на проблема с линейното програмиране до канонична форма:

min L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Въвеждаме във всяко уравнение на системата от ограничения променливите за изравняване x 4, x 5, x 6... Системата ще бъде написана под формата на равенства, а в първото и третото уравнение на системата от ограничения променливите x 4, x 6се въвеждат в лявата страна със знака "+", а във второто уравнение променливата x 5се въвежда със знак "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободните термини в канонична форма трябва да бъдат положителни, за това умножаваме последните две уравнения с -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

В каноничната форма на писане на задачи за линейно програмиране всички променливи, включени в системата от ограничения, трябва да бъдат отрицателни. Нека приемем, че x 1 = x 1 '- x 7 , където x 1 '≥ 0, x 7 ≥ 0 .

Замествайки този израз в системата от ограничения и целевата функция и записвайки променливите във възходящ ред на индекса, получаваме задача за линейно програмиране, представена в канонична форма:

L min = 2x 1 '+ x 2 - x 3 - 2x 7;
2x 2 - x 3 + x 4 = 5;
-x 1 '- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 ' + x 2 - x 6 + 2x 7 = 3;
x 1 '≥ 0; x i ≥ 0, i = 2, 3, 4, 5, 6, 7.

Условие за оптималност за основния план на каноничния LP проблем. Симплекс метод и неговата конвергенция.

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

Идеята за симплексния метод последователно подобряване на плана,се крие във факта, че като се започне от някакво първоначално решение за поддръжка, последователно насочено движениечрез поддържащите решения на проблема до оптималното.

Стойността на целевата функция не намалява с това движение за задачи до максимум.

Тъй като броят на опорните решения е краен, след краен брой стъпки получаваме оптималното решение за поддръжка.

Основно неотрицателно решение се нарича референтно решение.

Алгоритъм на симплексния метод

1. Математическият модел на задачата трябва да бъде каноничен. Ако е неканоничен, то трябва да се доведе до каноничната форма.

2. Намерете оригиналното решение за поддръжка и го проверете за оптималност.
За да направите това, попълнете симплексната таблица 1.
Попълваме всички редове на таблицата от 1 -ва стъпка според данните от системата на ограниченията и функцията за цел.

Следните случаи са възможни при решаване на проблеми на максимум:

1. Ако всички коефициенти на последния ред на симплексната таблица Dj ³ 0, след това намерен

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

2 Ако има поне един коефициент Dj £ 0, но за съответната променлива няма нито едно положително оценъчно съотношение, тогава решението спираме задачите, тъй като F (X) ® ¥,т.е. целевата функция не е ограничена в областта на възможните решения.

Ако поне един коефициент от последния ред е отрицателен и за съответната променлива има поне една положителна оценка, тогава трябва да отидете към друго референтно решение.

E акотогава в последния ред има няколко отрицателни коефициента до колоната на основната променлива(Bp) въведете това променливакоето съответства на най -големият отрицателен коефициент в абсолютна стойност.

5. Ако поне един коефициент Dk< 0 ,тогава k - thколона приемаме за домакина.

6. За водеща линияприемаме този, който отговаря на минималенотношение на свободния член бикъм положителни коефициенти водещ, к - товаколона.

7. Извиква се елемент, разположен в пресечната точка на водещи редове и колона водещ елемент.

Попълване на симплекс таблица 2 :

· попълнете основната колона с нули и единици

· пренапишете водещия ред, като го разделите на водещия елемент

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

· останалите коефициенти се намират по правилото "правоъгълник"

Получаваме ново решение за поддръжка, което проверяваме за оптималност:

Ако всички коефициенти на последния ред Dj ³ 0, тогава намереното решение максимум.

Ако не, тогава попълнете таблицата за симплекс от 8 -ма стъпка и така нататък.

Ако целта функция F (X)изисква намиране минимална стойност, тогава критерият оптималност на проблемае неположителни коефициентид j за всички j = 1,2,… n.

Сближаване на симплексния метод. Дегенерация в проблемите на LP. Най -важното свойство на всеки изчислителен алгоритъм е конвергенцията, тоест възможността за получаване на желаните резултати (с определена точност) в краен брой стъпки (итерации) по време на неговото прилагане.

Лесно е да се види, че проблемите с конвергенцията на симплексния метод потенциално могат да възникнат на етапа на избор на стойността на r (т. 2 ") в случай, че същите минимални стойности на съотношението

ще бъдат достигнати за няколко реда от таблицата T (q) едновременно. След това при следващата итерация колона b (β (q + 1)) ще съдържа нулеви елементи.

⇐ Предишен12345Следващ ⇒

Дата на публикуване: 2015-11-01; Прочетено: 4190 | Нарушаване на авторски права на страницата

Studopedia.org - Studopedia.Org - 2014-2018 г. (0.002 s) ...

Оптимално решение - проблем - линейно програмиране

Страница 1

Оптималното решение на задачата за линейно програмиране се постига в една от референтните точки, където поне k p, - m променливи са равни на нула.

Използвайки оптималното решение на задачата за линейно програмиране, е възможно да се намерят допустимите промени в DS, за които L също остава постоянна.

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

Доказано е, че оптималното решение на задачата за линейно програмиране се намира на границата на областта на допустимите стойности на контролирани променливи, която е полиедър в n-мерно пространство и се определя от система от линейни ограничения.

Тъй като z е оптимално решение на задача за линейно програмиране с m ограничения, това решение съдържа най -много m строго положителни променливи.

Доказано е, че оптималното решение на задачата за линейно програмиране е на границата на областта на допустимите стойности на контролираните променливи, която е полиедър в n-мерното пространство, дефинирано от система от линейни ограничения. Координатите на всеки връх се определят чрез решаване на система от уравнения (ограничения), а при наличието на n контролирани променливи и m ограничения е необходимо да се реши системата от m уравнения. Комбинацията Cm n (m - n нараства много бързо с увеличаване на типа, затова търсенето на решение изисква много голям брой изчисления, които са недостъпни дори за компютър.

Така че, в случай D 1, оптималното решение на задачата за линейно програмиране се оказва автоматично цяло число.

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

Очевидно не всяко основно решение е оптимално решение на задача за линейно програмиране. Оптималното решение на неизродена задача обаче винаги трябва да бъде основно за системата от уравнения (VIII, 42) и по този начин задачата за намиране на оптималното решение се състои в изброяване само на основните решения на системата от уравнения ( VIII, 42), сред които се намира оптималното.

Очевидно не всяко основно решение е оптимално решение на задача за линейно програмиране. Оптималното решение на неизродена задача обаче винаги трябва да бъде основно за системата от уравнения (VIII42) и по този начин проблемът за намиране на оптималното решение се състои в изброяване само на основните решения на системата от уравнения (VIII42), сред които се намира оптималното.

След извършване на няколко итерации в стъпка 3 могат да се появят множество алтернативни оптимални решения на проблема с линейното програмиране.

ПРОБЛЕМ НА ЛИНЕЙНО ПРОГРАМИРАНЕ

Този цикъл понякога се нарича непрекъснато израждане. За съжаление, това явление често се среща при средни PI проблеми с високо измерение. Има и много примери за нискоразмерни проблеми (не повече от 10 променливи и уравнения), които изискват хиляди повторения, за да се постигне конвергенция.

В тези случаи се използва симплексният метод, който представлява итеративна (стъпка по стъпка) процедура за определяне на оптималното решение на задача за линейно програмиране. Изчисленията, използващи симплексния метод, започват с определяне на възможно решение, след което се намират други възможни решения и се проверяват възможностите за тяхното подобряване. Преходът от едно решение към друго продължава, докато не са възможни нови подобрения. Стандартен компютърни програмикоито използват симплексния метод за решаване на управленски проблеми, които могат да бъдат представени като задачи на линейно програмиране.

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

Идеята за пропорционално разпределение е реализирана под формата на двустепенен алгоритъм за изчисление, предложен от И.И. Дикин, в който свойството на метода на вътрешната точка се използва по същество за генериране на набор от оптимални решения на задача за линейно програмиране по отношение до вътрешна точка. Това свойство означава, че граничните стойности според условията на неравенство (2.3.2) - (2.3.4) се постигат само за тези променливи, които имат тези гранични стойности за всяко друго оптимално решение.

Страници: 1 2

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

Помислете за LPP в стандартна форма за случая на две променливи:

(10)

Нека системата от неравенства (10) е последователна (има поне едно решение). Всяко неравенство на тази система геометрично определя полуплоскост с гранична линия Условията на отрицателност определят полуплоскости със съответни гранични линии и.

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

Решението на LPP е геометрично търсене на такава точка от полигона на решението, чиито координати доставят най -голямата (най -малката) стойност на целевата функция. Освен това всички точки на многогранника са валидно решение.

Помислете за т.нар линия линияобективна функция z, тоест линията, по която тази функция приема същата фиксирана стойност: или

Алгоритъм за решаване на задача за линейно програмиране по графичен метод (брой променливи).

1. Полигонална област от възможни решения на равнината се конструира, отговаряща на ограниченията. След това се конструира векторният градиент

обективна функция zвъв всеки момент областта на възможните решения.

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

3. За да се намерят координатите на оптималната точка, е необходимо да се реши системата от уравнения, която съответства на правите линии, чието пресичане образува тази точка.

Формулиране на основните видове задачи на LP, изграждане на техните математически модели

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

Пример.Решете проблема геометрично:

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

откъдето т.е. точка Сима координати (6, 4).

Максимумът (максималната стойност на целевата функция) е: Отговор:с оптимално решение т.е. максималната печалба може да бъде постигната чрез производство на 6 единици от първия и 4 единици от втория продукт.

ВЪВЕДЕНИЕ

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

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

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

Всички основни раздели на математическото програмиране (планиране) се използват като методи за оптимизация в икономиката.

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

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

където и са дадени функции и са някои реални числа.

В зависимост от вида на целевата функция и ограниченията математическото програмиране се разделя на линейно и нелинейно. Повечето

изучаваният раздел на математическото програмиране е линейно програмиране.

Определение.

Проблем с линейното програмиране (страница 1 от 3)

Линейно програмиране - науката за методите за използване и намиране на крайните (най -големите и най -малките) стойности на линейна функция, неизвестните от които са обект на линейни ограничения.

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

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

Нека разгледаме някои проблеми с линейното програмиране (LPP).

1. Проблемът с използването на ресурсите (проблемът с планирането на производството).

За производство на различни продукти компанията използва три различни вида суровини. Норми на потребление на суровини за производството на един продукт , както и общият брой

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

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

Нека изградим математически модел на този проблем.

Ние обозначаваме чрез желаната продукция на продукти, чрез - продукти,

чрез - продукти.

Тъй като има разходни норми за всеки вид суровина, тогава можем да намерим общите разходи за всеки вид суровина за производството на всички продукти. От таблицата следва, че общият обем на суровините от тип I ще бъде, II -
,

III -
... И тъй като има ограничения за запаса от суровини, следователно общият обем на суровините от всеки вид не трябва да бъде повече от общото количество суровини, т.е.

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

(1)

Икономически променливите може да приема само неотрицателни стойности:

(2)

Цената на всички продукти от този тип ще бъде – – Съответно общата стойност на продуктите, произведени от предприятието, ще бъде (3)

Трябва да намерим тази функция. По този начин сред всички неотрицателни решения на система (1) е необходимо да се намери такова, за което функция (3) да приема максималната си стойност.

Тази задача може лесно да се обобщи в случай на освобождаване на видове продукти, използващи видове суровини (ресурси).

Нека обозначим с - броя единици продукти, планирани за производство, - запас от ресурси - вид, - специфично потребление на ресурси за производство - ти продукти. - печалба от продажбата на единица продукт - първият вид.

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

допълнителна система от ограничения

при която е целевата функция

приема максималната стойност.

Коментирайте.За да съставите математически модел на LPP, трябва:

- въвеждане на обозначение на променливи;

- въз основа на целта на икономическите изследвания да се изготви целева функция;

- като се вземат предвид ограниченията при използването на икономическите показатели на проблема и техните количествени закони, запишете системата от ограничения.

Решаването на задачи за линейно програмиране се основава на концепциите за аналитична геометрия в измервателното векторно пространство.

Привеждане на общия LPP към каноничната форма.

Общият изглед на ЗЗП е следният:

(1)

(2)

(3)

където съотношение (1) е обективна функция, (2) е система от основни ограничения, (3) е система от допълнителни ограничения.

Форми за връзки (2) и (3) цялостна системаограничения.

Намаляването на системата от основни ограничения до каноничната форма се извършва чрез въвеждане на допълнителни неотрицателни променливи с коефициенти "+1", ако неравенствата са от формата, и "-1", ако неравенствата са от вида , в лявата част на неравенствата. Допълнителни променливи влизат в целевата функция с нулеви коефициенти.

Определение ... LPP се нарича канонично дефиниран, ако неговата система от основни ограничения е представена с уравнения.

Определение. LPP се нарича зададен в стандартната форма на каноничната форма, ако са изпълнени следните условия:

1) системата от основни ограничения е представена от уравнения и всички те са линейно независими;

2) броят на уравненията е по -малък от броя на променливите;

3) се решава проблемът за минимизиране на целевата функция;

4) дясните страни на системата от основни ограничения са неотрицателни;

5) всички променливи също са неотрицателни.

В повечето методи за решаване на задачи за линейно програмиране се приема, че системата от ограничения се състои от уравнения и естествени условия за неотрицателността на променливите.

При конструирането на модели на много проблеми обаче ограниченията се формират главно под формата на система от неравенства, така че е необходимо да може да се премине от система от неравенства към система от уравнения.

Това може да стане по следния начин:

Вземете линейното неравенство

и добавете към лявата му част някакво количество, така че неравенството да се превърне в равенство

Освен това тази стойност е неотрицателна.

Пример

Доведете проблема с линейното програмиране до каноничната форма:

Решение:

Нека се обърнем към проблема за намиране на максимума на целевата функция.

За да направите това, ние променяме знаците на коефициентите на целевата функция.

За да превърнем второто и третото неравенство на системата от ограничения в уравнения, въвеждаме неотрицателни допълнителни променливи x 4 x 5 (на математическия модел тази операция е маркирана с буквата D).

Променливата x 4 се въвежда в лявата част на второто неравенство със знака "+", тъй като неравенството има формата "≤".

Променливата x 5 се въвежда в лявата част на третото неравенство със знака "-", тъй като неравенството има формата "≥".

Променливите x 4 x 5 се въвеждат в целевата функция с коефициент. равна на нула.

Пишем задачата в канонична форма:

СИМПЛЕКСЕН МЕТОД ЗА РЕШАВАНЕ НА ЛИНЕЙНИ ПРОГРАМИРАНИ ПРОБЛЕМИ

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

Алгоритъм на симплексния метод за решаване на задачи за линейно програмиране

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

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

Тема 8. Линейно програмиране

Намерете първоначалното решение за поддръжка с "единична основа" (ако няма решение за поддръжка, тогава проблемът няма решение поради несъвместимостта на системата от ограничения)

3. Изчислете прогнозите за векторните разширения в основата на поддържащото решение и попълнете таблицата на симплексния метод

4. Ако критерият за уникалност на оптималното решение е удовлетворен, решението на проблема приключва

5. Ако условието за съществуване на набор от оптимални решения е изпълнено, тогава чрез просто изброяване се намират всички оптимални решения

Пример за решаване на проблем с помощта на симплексния метод

Пример 1

Решете проблема, като използвате симплексния метод:

Минимизирайте стойността на функцията

F = 10 × 1 - 4 × 3 макс

При наличието на ограничения под формата на неравенства

Довеждаме проблема до канонична форма.

За да направите това, от лявата страна на първото ограничение на неравенството въвеждаме допълнителна променлива x 5 с коефициент +1. Променливата x 5 е включена в целевата функция с коефициент нула (т.е. не е включена).

Получаваме:

F = 10 × 1 - 4 × 3 + 0 ∙ x5 макс

При наличието на ограничения под формата на неравенства

Намерете първоначалното решение за поддръжка. За това свободните (неразрешени) променливи се приравняват на нула x1 = x3 = 0.

Получаваме еталонното решение X1 = (0,0,0,5,9 / 15,6) с единична основа B1 = (A4, A5, A6).

Изчисляваме оценките на разширенията на векторите на условията в основата на поддържащото решение по формулата:

Δ k = C b X k - c k

C b = (s 1, s 2, ..., s m) е векторът на коефициентите на целевата функция за основните променливи

X k = (x 1k, x 2k, ..., x mk) е векторът на разширение на съответния вектор A към основата на референтното решение

· С к - коефициент на целевата функция при променливата х к.

Изчисленията на векторите, включени в базата, винаги са нула.

Поддържащото решение, коефициентите на разширение и оценките на разширенията на векторите на условията в основата на поддържащото решение са записани в симплекс таблица:

Над таблицата, за удобство при изчисляване на прогнозите, се изписват коефициентите на целевата функция. Първата колона "B" съдържа векторите, включени в основата на референтното решение. Редът на запис на тези вектори съответства на числата на разрешените неизвестни в уравненията на ограниченията. Втората колона на таблицата "C b" записва коефициентите на целевата функция с основните променливи в същия ред. При правилното подреждане на коефициентите на целевата функция в колоната "C b" оценките на единичните вектори, включени в базата, винаги са равни на нула.

Последният ред на таблицата с оценки Δ k в колоната "A 0" записва стойностите на целевата функция върху референтното решение Z (X 1).

Първоначалното опорно решение не е оптимално, тъй като в максималната задача оценките Δ 1 = -2, Δ 3 = -9 за вектори А 1 и А 3 са отрицателни.

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

Нека определим кой от двата вектора ще доведе до по -голям прираст на целевата функция.

Прирастването на целевата функция се намира по формулата:

Изчисляваме стойностите на параметъра θ 01 за първата и третата колона, използвайки формулата:

Получаваме θ 01 = 6 с l = 1, θ 03 = 3 с l = 1 (таблица 26.1).

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

ΔZ 1 = - 6 * ( - 2) = 12,

и третият вектор ΔZ 3 = - 3 * ( - 9) = 27.

Следователно, за по -бързо сближаване с оптималното решение, е необходимо да се въведе векторът A3 в основата на опорното решение вместо първия вектор на основата A6, тъй като минимумът на параметъра θ 03 е достигнат в първия ред (l = 1).

Извършваме преобразуването на Джордан с елемента X13 = 2, получаваме второто опорно решение

X2 = (0,0,3,21,42,0)

с основа B2 = (A3, A4, A5).

(таблица 26.2)

Това решение не е оптимално, тъй като векторът A2 има отрицателна оценка Δ2 = - 6.

За да се подобри решението, е необходимо да се въведе вектор А2 в основата на носещото решение.

Определете броя на вектора, получен от основата. За да направите това, изчислете параметъра θ 02 за втората колона, той е равен на 7 за l = 2.

Следователно от базата извеждаме втория базисен вектор A4.

Извършваме преобразуването на Джордан с елемента x 22 = 3, получаваме третото опорно решение

X3 = (0.7.10.0.63.0)

B2 = (A3, A2, A5) (таблица 26.3).

Това решение е единственото оптимално, тъй като за всички вектори, които не са включени в основата на оценката, е положително

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Отговор: max Z (X) = 201 при X = (0.7,10,0.63).

⇐ Предишен123456789Следващ ⇒

На практика ограниченията в задачата за линейно програмиране често се определят не от уравнения, а от неравенства.

Нека покажем как можем да преминем от проблема с ограниченията на неравенството към основния проблем на линейното програмиране.

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

Изисква се да се намери набор от неотрицателни стойности, които да удовлетворяват неравенствата (4.1) и освен това да минимизират линейната функция:

Лесно се преминава от така поставената задача към основната задача на линейното програмиране. Наистина, нека въведем нотацията:

къде са някои нови променливи, които ще наречем "допълнителни". Съгласно условията (4.1), тези допълнителни променливи, както и трябва да бъдат неотрицателни.

По този начин сме изправени пред проблем с линейно програмиране в следната формулировка: намерете такива неотрицателни стойности на променливите, така че да отговарят на системата от уравнения (4.3) и едновременно да редуцират линейната функция на тези променливи до минимум:

Както можете да видите, ние имаме в чиста форма основната задача на линейното програмиране (LPP). Уравненията (4.3) са дадени във вече разрешен вид за основни променливи, които се изразяват като свободни променливи.Общият брой на променливите е равен, от които "начални" и "допълнителни". Функцията L се изразява само чрез "началните" променливи (коефициентите на "допълнителните" променливи в нея са равни на нула).

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

Пример 1 Има проблем с линейно програмиране с ограничения на неравенството: намерете неотрицателни стойности на променливи, отговарящи на условията

и минимизиране на линейната функция

Изисква се тази задача да бъде приведена под формата на OZLP.

Решение. Намаляваме неравенствата (4.4) до стандартната форма;

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

Задачата се свежда до намиране на неотрицателните стойности на променливите

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

Показахме как можем да преминем от задача за линейно програмиране с ограничения на неравенството към проблем с ограничения за равенство (LPPP). Обратният преход винаги е възможен - от LPP към проблема с ограниченията на неравенството. Ако в първия случай увеличихме броя на променливите, то във втория ще го намалим, премахвайки основните променливи и оставяйки само свободни.

Пример 2. Има проблем с линейно програмиране с ограничения за равенство (LPPP):

и функцията, която трябва да бъде сведена до минимум

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

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

По същата причина е невъзможно да се изберат променливите като свободни (те са свързани с второто уравнение). Нека да изберем като безплатни променливи и да изразим всички останали чрез тях:

Тъй като условията (4 9) могат да бъдат заменени с неравенства:

Нека преминем в израза на линейната функция L към свободните променливи, заместващи в L вместо техните изрази (4.9). получаваме.

МОДЕЛ ЛИНЕЙНО ПРОГРАМИРАНЕ

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

2 Методи за внедряване на модели на линейно програмиране

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

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

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

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

2) транспортният проблем (намиране на оптимален план за различни видове транспорт, оптимален план за разпределение на различни средства към обекти за различни цели и др.)

МАТЕМАТИЧНО ОПИСАНИЕ НА МОДЕЛА НА ЛИНЕЙНО ПРОГРАМИРАНЕ

Необходимо е да се намерят неотрицателните стойности на променливите

удовлетворяващи линейни ограничения под формата на равенства и неравенства

,

където - дадени числа,

и осигуряване на екстремума на линейната целева функция

,

къде са дадените числа, което се записва като

Валидно решениевсеки набор се извиква удовлетворяващи условията.

Област на възможните решения- съвкупността от всички възможни решения.

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

Забележки

1. Даденият LP модел е общ... Разграничете също стандарти канониченформи на LP модели.

2... Условия на съществуванеИзпълнение на модела LP:

- наборът от възможни решения не е празен;

- обективна функция ограничено (поне отгоре при търсене на максимум и отдолу при търсене на минимум).

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

Теорема 1. Много Gдефинирана от система от ограничения на формата е изпъкнало затворено множество ( изпъкнал многогранникв с ъглови точки - върхове.)

Теорема 2. Линейна форма дефинирани върху изпъкналия многоъгълник

й=1,2,…,с

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

достига до екстремум в един от върховете на този многогранник.

Тази теорема се нарича теорема за екстремума на линейна форма.

Според теоремата на Вайерщрас оптималното решение е уникално и е глобален екстремум.

Има общ аналитичен подходкъм внедряването на LP модела - симплексния метод. При решаване на проблеми с линейно програмиране често няма решение. Това се случва по следните причини.

Нека илюстрираме първата причина с пример

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

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

В този случай областта на възможните решения не е ограничена отгоре. Областта на допустимите решения не е ограничена.

Следвайки традициите на линейно програмиране, нека да дадем на LP проблема икономическа интерпретация. Нека бъдат на наше разположение мвидове ресурси. Номер на типа ресурс йравно на . Тези ресурси са необходими за производството нвидове стоки. Нека обозначим количеството на тези стоки със символи съответно. Единица тип артикул iразходи. Вид производство на стоки iтрябва да бъдат ограничени до стойности съответно. За производството на единица от стоков тип iтип ресурс се консумира й... Необходимо е да се определи такъв план за производство на стоки ( ), така че общата им цена да е минимална.

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

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

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

,

,

i=1,..,н;й=1,..,м.

Всеки проблем с линейното програмиране може да бъде сведен до стандартна форма. Сравнението на общия модел с каноничния модел ни позволява да заключим, че за да се намали задачата LP до стандартната форма, е необходимо, първо, да се премине от системата на неравенства към равенства и, второ, да се трансформират всички променливите, така че да са неотрицателни.

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

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

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

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

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

,

.

Необходимо е да го приведете в стандартна форма. Обърнете внимание, че първото неравенство на първоначалния проблем има знак, следователно е необходимо да се въведе остатъчна променлива в него. В резултат на това получаваме.

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

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

.

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

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

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

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

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

в линейни ограничениямил

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

° С 1 j x 1 + ° С 2 j x 2 + … + c kj x k = c j , j = 1,…, q 2 ;

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

Общ брой ограничения m = q 1 + q 2 + q 3 може да надвишава броя на променливите (м> к). Освен това обикновено се въвежда условието за положителност на променливите ( x i ³ 0).

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

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

при следните ограничения

(2.3)

2х 1 + 3х£ 2 18;

х 1 – 4х 2 £ 4;

–2х 1 + х£ 2;

NS 1 ³ 0; х 2 ³ 0.

Обхват на валидни стойности (диапазон на дефиниция) OABCDза модел (2.2) се формира от ограничения (2.3) (фиг. 2.2). Повърхността за реакция е плосък многоъгълник OA "B" C "D"(фиг. 2.2, б).

При определено съотношение на ограничения, наборът от възможни решения може да отсъства (празен). Пример за такъв набор е показан на фиг. 2.3. Директен КАТОи Слънцеограничете обхвата на допустимите стойности отгоре. Третото ограничение отрязва диапазона от допустими стойности от долната част на правата линия AB.По този начин няма обща зона, която да отговаря на трите ограничения.

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

При изследването на DLA рядко се използват линейни модели и почти изключително за приблизително описание на проблемите.

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

Изучаването на линейни модели не е трудно. По -специално, влиянието на всяка от променливите върху характеристиките на модел на формата

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

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

, i = 1,…, к.

За да намерите оптималния линеен модел W opt разработи ефективен симплекс метод.

Най -простите модели на разходите понякога се свеждат до линейни, разглеждани като набор от направени разходи.

Пример за такъв модел е класическият модел на транспортните разходи (проблем с транспорта)(Фиг. 2.4).

Има кпроизводствени точки
(i = 1,…, к) и мточки на потребление
(й = 1,…, м) на някой продукт. Количеството произведен продукт във всеки кпроизводствените точки са равни a i; количеството продукт, необходимо във всеки от мточки на потребление е равно на b j.

Приема се равенство на общото производство и потребление:

Количеството на транспортирания продукт от i-тият производствен пункт в й-та точка на потребление е равна на x ij; разходите за транспортиране на единица от този продукт - с ij.

Общи разходи за транспорт СДадено е S линеен модел:

при следните ограничения

Линейните модели включват и модели под формата на линейни диференциални уравнения (обикновени или частични производни).

Линейно обикновено диференциално уравнение н-та поръчка има формата

Началните условия са записани като

Линейното уравнение с частичен диференциал има формата

Моделът, даден под формата на частично диференциално уравнение, включва начални и гранични условия (условия на границата на областта на дефиниция на функцията F ( T)).

2.3. Изучаване на най -простия математически модел
работа на газотурбинен двигател

Газотурбинният двигател (GTE) е основната електроцентрала на съвременните самолети.

Диаграмата GTE има формата, показана на фиг. 2.5.

Тук 1 - входящ дифузьор; 2 - компресор; 3 - горивната камера; 4 - турбина;
5 - изходяща дюза.

Работният цикъл на GTE включва следните етапи:

1) Пристигане със скорост Vвъздушният поток през дифузора влиза в компресора.

2) Компресорът, въртящ се на същия вал с турбината, компресира въздуха, който влиза в горивната камера.

3) Горивото (керосин) се впръсква постоянно в горивната камера, което се смесва със сгъстен въздух.

4) Газът, генериран от горенето, влиза в турбината, което я ускорява до скорост W.

5) При тази скорост газът се изхвърля в атмосферата през дюзата.

Поради факта че W > V, се генерира тягова сила Rкоето позволява на самолета да лети в атмосферата.

Силата на тягата се променя чрез промяна на скоростта на впръскване на гориво в горивната камера чрез преместване на копчето за управление на двигателя (управление на дросела). Движението на тягата на газ до определен ъгъл d на дросела се извършва или ръчно от пилота, или чрез задвижващ механизъм според сигналите от ACS по време на полет. Увеличаването на стойността на d дросела води до увеличаване на силата R, а намаляването е намаляване на тази сила.

GTE е сложна техническа система, в която протичат значителен брой физични и химични процеси. Двигателят е оборудван с всякакви устройства за автоматизация, системи за завъртане и охлаждане на лопатките на турбините и др. Естествено, математическото описание на функционирането на GTE също ще бъде доста тромаво, включително системи от уравнения с частични диференциали, обикновени диференциални уравнения, трансцендентални функции, алгоритми на цифрова система за управление на двигателя. Такива модели се използват в процеса на проектиране на газотурбинен двигател.

За решаване на проблеми с управлението на полета се използва по -прост модел GTE, който е зависимостта на силата на тягата Rот ъгъла d на дросела, отклонението на дросела. Процесът на промяна на тяговата сила е описан с обикновен диференциално уравнениемил:

, (2.11)

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

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

R(0) = R 0 . (2.12)

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

За да се определи съотношението на страните кизползвани калибриращи графики на зависимостта на тягата от ъгъла на въртене на дросела, изградени въз основа на експериментални данни. Тангенсът на наклона на графиката е равен на желания коефициент.

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

Когато дроселът е отклонен, тягата Rсе увеличава и след това се стабилизира при определена гранична стойност, т.е. GTE е инерционен обект.

Граница на тягова силаполучаваме от (2.11), когато скоростта на промяната му е равна на нула:

. (2.13)

Продължителност на покачванезависи от стойността на времевата константа на двигателя t. Процесът се счита за стабилен, когато t = tустата, когато тягата влезе в т. нар. пет процентов коридор от граничната стойност на силата на тягата (фиг. 2.6). Колкото повече t, толкова по -инерционен е двигателят и следователно, толкова повече Tуста

На фиг. 2.7 показва поведението на тяговата сила като функция от ъгъла на отклонение на дросела при t = 0,5.

Силата на тягата по време на излитане, когато дроселът се отклонява с 10 °, достига стабилно състояние през третата секунда и достига 3390 кг. Десет секунди след излитане, когато дроселната клапа е отклонена с 20 °, силата на тягата е зададена на 6780 кг, а след още десет секунди, когато дроселната клапа е отклонена с 30 °, тягата е зададена на 10170 кг. Ограничителната стойност на тяговата сила е
14270 кг.

Подобна информация.

Основни концепции за моделиране

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

МоделиранеТова е универсален начин за изучаване на процеси и явления в реалния свят. Моделирането е от особено значение при изучаване на обекти, които са недостъпни за директно наблюдение и изследване. Те включват по-специално социално-икономически явления и процеси.

Изучаването на всеки обект, всяка форма на движение е разкриване не само на неговите качествени, но и на количествени закони, изучавани от математиката. Гореизложеното се отнася изцяло за икономиката.

Икономика- Това е система на обществено производство, която действително осъществява производството, разпределението, размяната и потреблението на материални блага, необходими на обществото.

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

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

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

Дадена функция нпроменливи Необходимо е да се намери най -голямата или най -малката стойност на тази функция, при условие че аргументът

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

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

намерете екстремума на функцията

с ограничения

при условия без отрицателност

Нека въведем нотация:

Запаси i-Тип ресурс;

разходи i-Тип ресурс за производство й-Тип продукт;

единична печалба й-Тип продукт.

В компактна нотация задачата за линейно програмиране има формата:

Компактната нотация показва, че общият модел на задача за линейно програмиране включва пет основни елемента:

Променливи, чиято стойност се открива в процеса на решаване на проблема;

Технически и икономически коефициенти за променливи в ограниченията;

Обемът на дясната страна на неравенствата, които се наричат ​​константи на задачата;

Коефициенти на променливи в целевата функция, които се наричат ​​променливи оценки;

Променлив индекс;

Индекс на ограничение.

Целева функция(функция цел) е математически израз, за ​​който искате да намерите крайността, тоест максималната или минималната стойност.

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

Променливите могат да бъдат произволно променяни при условията на разглеждания проблем. Променлива , чиито коефициенти образуват единична колона се наричат основен.Формират се основни променливи единична основасистеми. Извикват се променливи, които не са включени в единичната основа Безплатно.

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

Променливите могат да бъдат изразени в голямо разнообразие от единици: ha, q, kg, бр., Heads и др. По своето естество променливите се подразделят на основни, допълнителни и спомагателни. Основните променливи включват търсените дейности: индустрии, видове фуражи, марки автомобили. Допълнителни променливи се наричат ​​променливи, които се образуват в процеса на трансформиране на неравенствата в уравнения. Те могат да означават недостатъчно използвана част от ресурсите, излишък над правилната странанеравенство (ако става въпрос за неравенство от типа "не повече"). Помощните променливи са включени в задачата, за да се определят прогнозните стойности на придобитите производствени ресурси, прогнозните стойности на показателите за икономическата ефективност на производството.

Допълнителните и спомагателните променливи винаги имат единични коефициенти (+1 или –1).

Технически и икономически коефициенти (a ij)с променливи в системата на ограниченията се изразяват нормите на производствени ресурси или нормата на продукция на единица измерване на променливата.

И в двата случая е необходимо техническите и икономическите коефициенти да съответстват точно на периода на планиране, за който се решава проблемът. Например, ако проблемът е решен за икономическия и математически анализ на производството за изминалия период, тогава коефициентите ще бъдат изчислени според отчетените данни. Ако е решено за в бъдеще, тогава коефициентите трябва да бъдат изчислени за тази перспектива.

Нормите на потребление на ресурси най -често се определят от справочници, те трябва да бъдат съобразени със съответните специфични условия. Коефициентите на добив се изчисляват въз основа на планираните добиви и производителността на животните.

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

Дясната страна на ограниченията (b i)се наричат ​​константи, т.е. постоянни стойности. Те включват обема на производствените ресурси - земя, труд, машини, торове, капиталови инвестиции и др. Производствените ресурси трябва да се определят, като се вземе предвид тяхното реално състояние и е наложително да се вземе предвид периодът на планиране. Освен това тези производствени ресурси, чието използване е неравномерно през цялата година, се изчисляват не само за годината като цяло, но и за отделни интензивни периоди или месеци (трудови ресурси).

Производствените ресурси се определят в различни единици: земя - в хектари, трудови ресурси - в човекодни или в човекочасове, оборудване - в брой смени на машината, смяна или дневна продукция и др.

По този начин определянето на наличността на производствени ресурси не е лесно. Необходимо е внимателно да се анализира производствената дейност на икономиката, използването на труд, земя, технически и други ресурси и едва след това да се включат обемите им в ограниченията.

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

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

ОграничениеТова е математически израз, който свързва променливите под формата на равенства и неравенства. Всички ограничения са под формата система от ограничениязадачи. Системата от ограничения в математическа форма характеризира условията на задачата. Пълнотата на отражението на тези условия зависи от състава на ограниченията. Следователно при определяне на броя на ограниченията трябва да се вземат предвид две обстоятелства:

v отразяват в задачата само тези условия, които наистина ограничават възможностите за производство;

v твърде много ограничения увеличават размера на проблема и затрудняват разрешаването му

Има три типа ограничения: равенство (=), неравенство на типа по -малко или равно на (≤), неравенство на типа по -голямо или равно на (≥). Например,

където i = 1, 2, … , м... Обозначават се променливи коефициенти a ijкъдето индекс i- номер на ограничение, индекс й- променлив номер, се означават свободните членове (дясната страна на ограниченията) b i, индекс i- номер на ограничение.

Ограниченията от първия тип се наричат ​​горни ограничения, тъй като лявата страна на неравенството не може да бъде по -висока от определена стойност (константа). Ограниченията от третия тип се наричат ​​ограничения отдолу, тъй като лявата страна на неравенството не може да бъде по -ниска от определена стойност (константа).

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

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

Допълнителни ограничениясе наслагват върху част от променливите или върху една променлива. Тези ограничения се въвеждат в случаите, когато е необходимо да се ограничи размерът на отделните променливи отгоре или отдолу, например, като се вземат предвид изискванията за сеитбообращение или като се вземат предвид физиологичните граници на насищане на диетата с отделни фуражи или техните групи. По този начин допълнителните ограничения отразяват различни допълнителни условия, които възникват по време на симулацията. Но всяко допълнително ограничение стеснява зоната на свобода на избор. Следователно те трябва да бъдат въведени в задачата внимателно, в разумни граници и когато е необходимо.

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

Оценка на променливите в целевата функция (с й) са коефициенти, които изразяват размера на общия доход или разходи на единица мярка на променливата. Оценката на променлива, като правило, изразява приетия критерий за оптималност. Тя може да бъде представена както в натура, така и в брой, т.е. единични разходи (производствени разходи).

Условието за неотрицателност на променливите се записва във формата

x j≥ 0, j = 1, 2, ..., н.

В реалния живот на производството, въз основа на условията на задачата, списъкът на променливите и ограниченията се съставя от този запис на структурния икономически и математически модел (EMM), изготвя се първоначална информация, изгражда се подробен EMM проблем, който е след това се записва под формата на матрица (таблица), въвежда се в компютър и изчислението и анализът на резултатите се извършва съгласно съответната програма. i = 1, ..., м, (1.5)

й = 1, …, н. (1.6)

Вектор х = (х 1 , х 2 , …, х n), компоненти x jкоито отговарят на ограничения (1.2) и (1.3) [или (1.5) и (1.6) в минималния проблем] се нарича приемливо решениеили приемлив план LP задачи. Извиква се събирането на всички валидни планове много валидни планове.

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

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

Правилото за свеждане на задачата за линейно програмиране до каноничната формае както следва:

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

2) ако в ограниченията дясната страна е отрицателна, тогава това ограничение трябва да се умножи по - 1;

3) ако сред ограниченията има неравенства, то чрез въвеждане на допълнителни променливи на неотрицателни променливи те се трансформират в равенства. Например допълнителни променливи S jв ограничения от типа по -малки или равни на (£) се въвеждат със знак плюс:

Допълнителни променливи S jв типа ограничения по -големи или равни на (≥) се въвеждат със знак минус:

За да премахнете негативността на допълнителни променливи - S jвъведете изкуствени променливи със знак плюс + M jс много големи стойности.