Решение: намерете максималната и минималната стойност на функцията \(f (x, y)\) при следните ограничения $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Графичен начинПрепоръчително е да се използва решението на задачата за задачи с две променливи, които са записани в симетрична форма, както и за задачи с много променливи, при условие че тяхната канонична нотация съдържа не повече от две свободни променливи.

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

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

1. Да построим областта на допустимите решения на равнината xOy.
2. Изберете областта на неотрицателните решения.

4. Нека построим семейство от целеви функции.
5. Намерете максималната (минималната) стойност целева функция.

1. Конструираме областта на допустимите решения на задачата \(D\).

За да изградите областта на осъществимите решения:
1) Изграждаме гранични линии:
преобразуваме неравенствата в равенства и след това в уравнение на права линия в сегменти по осите на формата \(\frac(x)(a)+\frac(y)(b) = 1\), тогава \ (x=a\) е сегмент, отрязан по оста Ox, \(y=b\) - по оста Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ За всяка линия отделете сегменти на осите и ги свържете. Имаме правилните линии.

2) Намираме полуравнини, които удовлетворяват дадените неравенства:
За неравенството \(2x+3y\geq 6\) е полуравнината, която лежи над правата \(2x+3y = 6\). Директен климатик
За неравенството \(3x-2y\leq 18 => -3x+2y \geq -18\) е полуравнина, която лежи над правата \(3x-2y = 18\). Директен CB
За неравенството \(-x+2y\leq 8\) е полуравнината, която лежи под правата \(-x+2y = 8\). Директен АВ

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

Регионът \(D\) е триъгълникът \(ABC\), вижте фиг.

2. Изберете областта на неотрицателните решения.

Областта на неотрицателните решения се намира в първата четвърт и е обща част от всичките пет полуравнини, три от които са областта \(D\), получена от неравенства и допълнително две неравенства \(x \geq 0\ ) - горната полуравнина (I и II четвърти) и \(y \geq 0\) - дясната полуравнина (I и IV четвърти), които изразяват условието за неотрицателност на променливите \(x; y\). Получена е желаната област на неотрицателни решения \(DEBFG\)

3. Намерете координатите на върховете на областта.
Координатите на четирите върха вече са известни (това са точките на пресичане на правите с осите).
Нека запишем тези координати:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Намерете координатите на точката \(B\), като точки на пресичане на правите \(-x+2y = 8\) и \(3x-2y = 18\). Решете системата от уравнения и намерете координатите на тази точка $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Получихме координатите на точката \(B(13;10.5)\)

4. Изграждаме семейство от целеви функции.
Уравнението \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) определя в равнината xOy семейство от концентрични окръжности с център в точка с координати \ (Q(4 ;3)\), всеки от които отговаря на определена стойност на параметъра \(f\). Както знаете, за уравнението на окръжност параметърът \(f=R^2\).

Нека представим в една и съща координатна система семейство от концентрични окръжности \(f\) и семейство от прави. Задачата за определяне на максималната (минималната) точка на точката \(f\) ще се сведе до намиране в допустимата област на точката, през която преминава окръжността на семейството \(f=const\), което отговаря за най-голямата (най-малката) стойност на параметъра \(f\).

5. Намерете максималната (минималната) стойност на целевата функция.

Минимална стойност на целевата функция: Чрез постепенно увеличаване на радиуса на окръжността получихме, че първият връх, през който минава окръжността, е точката \(G(3;0)\). Целевата функция в този момент ще бъде минимална и равна на \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Максималната стойност на целевата функция: Чрез допълнително увеличаване на радиуса на окръжността, ние получихме, че последният връх, през който окръжността ще премине, е точката \(B(13;10.5)\). Целевата функция в тази точка ще бъде максимална и равна на \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Можете да проверите правилността на решението, като замените координатите на останалите върхове в уравнението на целевата функция:
във върха \(D(0;2)\) стойността на целевата функция е равна на \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
във върха \(E(0;4)\) стойността на целевата функция е равна на \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
във върха \(F(6;0)\) стойността на целевата функция е \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Разбрах това

Отговор:
минималната стойност на целевата функция \(f_(min) = 10\)
максималната стойност на целевата функция \(f_(max) = 137,25\)

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

Примери

Гладки функции и системи уравнения

Проблемът за решаване на всяка система от уравнения

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\точно.)

може да се формулира като проблем за минимизиране на целевата функция

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

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

За всяка гладка целева функция можете да приравните към 0 (\displaystyle 0) частните производни по отношение на всички променливи. Оптималната целева функция ще бъде едно от решенията на такава система от уравнения. В случай на функция (1) (\displaystyle (1)) това ще бъде системата от уравнения на метода най-малки квадрати(MNK). Всяко решение на първоначалната система е решение на системата на най-малките квадрати. Ако оригиналната система е непоследователна, тогава системата LSM, която винаги има решение, позволява да се получи приблизително решение на оригиналната система. Броят на уравненията на LSM системата съвпада с броя на неизвестните, което понякога улеснява решаването на съвместни начални системи.

Линейно програмиране

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

Комбинаторна оптимизация

Типичен пример за комбинаторна целева функция е целевата функция на задачата на пътуващия търговец. Тази функция е равна на дължината на Хамилтоновия цикъл на графиката. Дадено е върху множеството за пермутация n − 1 (\displaystyle n-1) от върховете на графа и се определя от матрицата на дължината на ръба на графа. Точното решение на подобни проблеми често се свежда до изброяване на варианти.

Глава 1. Постановка на основния проблем на линейното програмиране

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

Линейното програмиране е клон на математическото програмиране, който изучава методи за решаване на екстремални проблеми, които се характеризират с линейна връзка между променливи и линеен критерий. Такива проблеми намират широки приложения в различни области. човешка дейност. Систематичното изследване на проблеми от този тип започва през 1939–1940 г. в произведенията на L.V. Канторович.

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

Обхватът на проблемите, решавани с помощта на методите на линейното програмиране, е доста широк, като например:

проблемът за оптималното използване на ресурсите при планирането на производството;

проблемът със смесите (планиране състава на продуктите);

проблемът за намиране на оптималната комбинация различни видовепродукти за съхранение в складове (управление на запасите или);

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

Линейното програмиране е най-развитият и широко използван раздел на математическото програмиране (в допълнение, това включва: цяло число, динамично, нелинейно, параметрично програмиране). Това се обяснява по следния начин:

математически модели Голям бройикономическите проблеми са линейни по отношение на необходимите променливи;

този тип проблеми в момента са най-изследвани. За него са разработени специални методи, с помощта на които се решават тези проблеми, и съответните компютърни програми;

много проблеми на линейното програмиране, като са решени, са намерили широко приложение;

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

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

AT общ изгледмоделът е написан по следния начин:

целева функция

(1.1) при ограниченията

(1.2) изисквания за неотрицателност

(1.3) където х й– променливи (неизвестни);

- коефициенти на задачата за линейно програмиране.

Проблемът е да се намери оптималната стойност на функцията (1.1) при ограниченията (1.2) и (1.3).

Системата от ограничения (1.2) се нарича функционални ограничения на задачата, а ограниченията (1.3) се наричат ​​директни ограничения.

Вектор, който удовлетворява ограниченията (1.2) и (1.3), се нарича изпълнимо решение (план) на задача на линейно програмиране. Планът, при който функцията (1.1) достига своята максимална (минимална) стойност, се нарича оптимален.

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

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

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

Допустимо решение (допустим план) на задачата LP, дадена в стандартна форма, е подреден набор от числа (x1, x2, ..., xn), които удовлетворяват ограниченията; е точка в n-мерното пространство.

Множеството от допустими решения образува областта на допустимите решения (SDR) на задачата LP. ODR е изпъкнал многостен (многоъгълник).

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

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

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

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

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

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

Може да се използва за решаване на всеки проблем с линейно програмиране.

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

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

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

Процесът на прилагане на симплексния метод включва изпълнението на неговите три основни елемента:

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

правилото за преход към най-доброто (по-точно, не най-лошото) решение;

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

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

6.1 Въведение

Оптимизация. Част 1

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

6.2.Основи на теорията на оптимизацията

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

Разглеждайки произволна система, описана с m уравнения с n неизвестни, можем да различим три основни типа задачи. Ако m=n, проблемът се нарича алгебричен. Такъв проблем обикновено има едно решение. Ако m>n, тогава проблемът е предефиниран и по правило няма решение. И накрая, за m

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

Проектни параметри

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

X1, x2, x3,...,xn.

целева функция

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

M=M(x 1 , x 2 ,...,x n).

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

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

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

Фиг. 1. Едномерна целева функция.

Фиг.6.2. Двумерна целева функция.

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

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

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

Намиране на минимума и максимума

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

Дизайн пространство

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

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

Фигура 6.3 Промяна на знака на целевата функция към противоположния

Максималната задача става минимална задача.

задоволително решение. Ограниченията се делят на две групи: ограничения – равенства и ограничения – неравенства.

Ограничения – равенство

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

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

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

C j (x 1, x 2,...,x n)=0.

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

Ограничения – неравенства

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

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

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

z k r k (x 1 , x 2 ,...,x n) Z k

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

Локален оптимум

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

Фиг.6.4 Една произволна целева функция може да има няколко

локални оптимуми.

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

Глобален оптимум

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

Пример 6.1

Нека е необходимо да се проектира правоъгълен контейнер с обем 1 m, предназначен за транспортиране на неопаковани влакна. Желателно е възможно най-малко материал да се изразходва за производството на такива контейнери (при постоянна дебелина на стената, това означава, че повърхността трябва да бъде минимална), тъй като ще бъде по-евтино. За да е удобно да вземете контейнера с мотокар, ширината му трябва да бъде най-малко 1,5 m.

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

Проектни параметри: x 1 , x 2 , x 3 .

Целевата функция (която трябва да бъде сведена до минимум) е площта на страничната повърхност на контейнера:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

Ограничение - равенство:

Обем \u003d x 1 x 2 x 3 \u003d 1m3.

Ограничение - неравенство:

Проблеми с линейно програмиране

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

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

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

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

AT общ изгледПроблемът с LP има следната форма:

, (5.1)

, , (5.2)

, , (5.3)

където , , са дадени константи.

Функция (5.1) се нарича целева функция; системи (5.2), (5.3) - чрез система от ограничения; условие (5.4) е условието за неотрицателност на проектните параметри.

Наборът от проектни параметри, удовлетворяващи ограниченията (5.2), (5.3) и (5.4), се нарича приемливо решениеили план.

Оптималното решениеили оптимален планПроблемът на LP се нарича осъществимо решение, при което целевата функция (5.1) приема оптимална (максимална или минимална) стойност.

Стандартна задача LP се нарича задачата за намиране на максималната (минималната) стойност на целевата функция (5.1) при условие (5.2) и (5.4), където , , т.е. тези. ограничения само под формата на неравенства (5.2) и всички параметри на дизайна отговарят на условието за неотрицателност и няма условия под формата на равенства:

,

, , (5.5)

.

Канонична (главна) задачаЛП се нарича задачата за намиране на максималната (минималната) стойност на целевата функция (5.1) при условията (5.3) и (5.4), където , , т.е. тези. ограничения само под формата на равенства (5.3) и всички проектни параметри отговарят на условието за неотрицателност и няма условия под формата на неравенства:

,

.

Каноничният LP проблем може също да бъде написан в матрична и векторна форма.

Матричната форма на каноничния LP проблем има следния вид:

Векторна форма на каноничната задача LP.

ТЕМА: ЛИНЕЙНО ПРОГРАМИРАНЕ

ЗАДАЧА 2.А. Решаване на задача от линейно програмиране графичен метод

внимание!

Това е ВЪВЕДЕНИЕ ВЕРСИЯ на работа № 2073, цената на оригинала е 200 рубли. Проектиран в Microsoft Word.

Плащане. Контакти.

Вариант 7. Намерете максималната и минималната стойностлинейна функция Ф \u003d 2x 1 - 2 x 2с ограничения: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Решение:

Заменяйки условно знаци на неравенства със знаци на равенства, получаваме система от уравнения x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

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

Минималната стойност на функцията

tsii - в точката M (2; 2)

Ф min = 2 2 - 2 2 = 0.

Максималната стойност се достига в точка N (10; 0),

Ф max \u003d 2 10 - 2 0 \u003d 20.

Вариант 8. Намерете максималната и минималната стойност

линейна функция Ф \u003d x 1 + x 2

с ограничения: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Решение:

Заменяйки условно знаци на неравенства със знаци на равенства, получаваме система от уравнения x1 - 4 x2 = 4;

3 x1 - x2 = 0;

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

Минималната стойност на функцията

ции - на права линия NP, например

в точка Р(4; 0)

Ф min = 4 + 0 = 4.

ODE не е ограничен отгоре, следователно Ф max = + ∞.

Вариант 10. Намерете максималната и минималната стойност

линейна функция Ф \u003d 2 x 1 - 3 x 2

с ограничения: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

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

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

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

Построяваме вектора Г(2; -3) и прекарваме през началото линия на ниво- прав.

Преместваме линията на нивото в посока, докато стойността на F се увеличава. В точката S(7; 0) целевата функция достига своя максимум Ф max =2·7–3·0= = 14. Преместваме линията на нивото в посока, докато стойността на Ф намалява. Минималната стойност на функцията е в точка N(0; 5)

Ф min = 2 0 – 3 5 = –15.

ЗАДАЧА 2.Б. Решаване на задача от линейно програмиране

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

Вариант 7. Минимизирайте целевата функция Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

при ограничения: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Решение:

Броят на неизвестните n=6, броят на уравненията m=3. Следователно r = n-m = 3 неизвестни могат да се приемат за свободни. Нека изберем x 1 , x 3 и x 6 .

Изразяваме основните променливи x 2 , x 4 и x 5 по отношение на свободните и привеждаме системата към единица

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Целевата функция ще изглежда така:

Ф \u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

Нека поставим x 1 \u003d x 3 \u003d x 6 \u003d 0, докато основните променливи ще приемат стойностите x 2 \u003d 2; x4 = 9; x 5 \u003d 6, т.е. първото възможно решение (0; 2; 0; 9; 6; 0), целева функция Ф 1 \u003d 13.

Променливите x 3 и x 6 са включени в целевата функция с отрицателни коефициенти, следователно с увеличаване на техните стойности стойността на Ф ще намалее. Вземете например x 6 . От първото уравнение на системата (*) се вижда, че е възможно увеличение на стойността на x 6 до x 6 \u003d 1 (стига x 2 ³ 0). В този случай x 1 и x 3 запазват стойности, равни на нула. Сега като основни променливи приемаме x 4, x 5, x 6, като свободни - x 1, x 2, x 3. Нека изразим новите основни променливи чрез новите свободни. Вземете

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

Ф \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Задайте нулеви стойности на свободни променливи, т.е. x 1 \u003d x 2 \u003d x 3 \u003d 0, докато x 6 \u003d 1, x 4 = 3, x 5 \u003d 4, тоест третата валидно решение (0; 0; 0; 3; 4; 1). В този случай Ф 3 \u003d 6.

Променливата x 3 е включена в целевата функция с отрицателен коефициент, следователно увеличението на x 3 спрямо нула ще доведе до намаляване на F. От второто уравнение се вижда, че x 3 може да се увеличи до 1/ 4, от 3-то уравнение - до 2/3 . Второто уравнение е по-критично. Превеждаме променливата x 3 в броя на основните, x 4 в броя на свободните.

Сега вземаме x 1 , x 2 и x 4 като нови свободни променливи. Нека изразим нови основни променливи x 3 , x 5 , x 6 чрез тях. Да вземем системата

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

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

Ф \u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Променливите x 1 и x 2 са включени в целевата функция с отрицателни коефициенти, следователно с увеличаване на техните стойности стойността на Ф ще намалее. Вземете, например, x 2 . От второто уравнение на системата може да се види, че е възможно увеличение на стойността на x 2 до x 2 \u003d 5 (стига x 5 ³ 0). В този случай x 1 и x 4 запазват нулеви стойности, стойностите на другите променливи са равни на x 3 = 3/2; x 5 \u003d 0, x 6 \u003d 3/2, т.е. четвъртото валидно решение (0; 5; 3/2; 0; 0; 3/2). В този случай Ф 4 \u003d 5/4.

Сега вземаме x 1, x 4 и x 5 като нови свободни променливи. Нека изразим нови основни променливи x 2 , x 3 , x 6 чрез тях. Да вземем системата

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

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

F \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

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

Тоест минималната стойност на Ф min = - 5, последното възможно решение (0; 5; 3/2; 0; 0; 3/2) е оптимално.

Вариант 8. Максимизиране на целевата функция Ф = 4 x 5 + 2 x 6

с ограничения: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

Решение:

Броят на уравненията е 4, броят на неизвестните е 6. Следователно r = n - m = 6 - 4 = 2 променливи могат да бъдат избрани като свободни, 4 променливи като основни. Избираме x 5 и x 6 като безплатни, x 1, x 2, x 3, x 4 като основни. Изразяваме основните променливи чрез свободните и редуцираме системата от уравнения до единица

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Записваме целевата функция във вида Ф = 4 x 5 + 2 x 6 . Задайте на свободни променливи нулеви стойности x 5 = x 6 = 0. В този случай основните променливи ще приемат стойностите x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9, тоест ще получим първото възможно решение (12, 30 , 6, 9, 0,) и Ф 1 = 0.

И двете свободни променливи влизат в целевата функция с положителни коефициенти, тоест е възможно по-нататъшно увеличение на F. Нека преведем, например, x 6 в броя на основните. Уравнение (1) показва, че x 1 = 0 при x 5 = 12, в (2) ÷ (4) x 6 влиза с положителни коефициенти. Нека преминем към нова основа: основни променливи - x 6, x 2, x 3, x 4, свободни - x 1, x 5. Нека изразим новите основни променливи чрез нови свободни

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

Целевата функция ще приеме формата Ф = 24 - 2 x 1 + 2 x 5 ;

Присвояваме нулеви стойности на свободни променливи x 1 = x 5 = 0. В този случай основните променливи ще приемат стойностите x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , тоест ще получим второто допустимо решение (0, 42 , 30, 21, 0, 12) и Ф 2 = 24.

Целевата функция x 5 влиза с положителен коефициент, тоест е възможно по-нататъшно увеличение на F. Да преминем към нова база: основни променливи - x 6, x 5, x 3, x 4, свободни - x 1 , x 2. Нека изразим нови основни променливи чрез new free

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

Целевата функция ще приеме формата Ф = 38 - 7/2 x 1 - 1/3 x 2;

Задайте нулеви стойности на свободни променливи x 1 = x 2 = 0. В този случай основните променливи ще приемат стойностите x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, тоест ще получим третото допустимо решение X 3 = (0, 0, 9, 7/2, 7, 5) и Ф 3 = 38.

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

Следователно последното възможно решение е оптимално, т.е. Х opt = (0, 0, 9, 7/2, 7, 5) и Ф max = 38.

Вариант 10. Максимизирайте целевата функция Ф \u003d x 2 + x 3

при ограничения: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

Решение:

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

Да вземем като свободни променливи x 2 и x 3. Тогава променливите x 1 и x 2 ще бъдат основните, които ще изразим чрез свободни

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

Целевата функция вече е изразена чрез x 2 и x 3 , тоест Ф = x 2 + x 3 .

При x 2 \u003d 0 и x 3 \u003d 0, основните променливи ще бъдат равни на x 1 = 1, x 4 \u003d 2.

Имаме първото допустимо решение X 1 = (1, 0, 0, 2), докато Ф 1 = 0.

Увеличаване на Ф е възможно с увеличаване например на стойността на x 3, която се включва в израза за Ф с положителен коефициент (x 2 остава равен на нула). В първото уравнение на системата (*) се вижда, че x 3 може да се увеличи до 1 (от условието x 1 ³0), тоест това уравнение налага ограничение за увеличаване на стойността на x 3. Първото уравнение на системата (*) е разрешаващо. На базата на това уравнение преминаваме към нова основа, променяйки x 1 и x 3 места. Сега основните променливи ще бъдат x 3 и x 4, свободните - x 1 и x 2. Сега изразяваме x 3 и x 4 чрез x 1 и x 2.

Получаваме: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

Приравнявайки свободните променливи на нула, получаваме второто допустимо базисно решение X 2 = (0; 0; 1; 4), в което Ф 2 =1.

Възможно е увеличение на F с увеличение на x 2. Увеличението на x 2, съдейки по последната система от уравнения (**), не е ограничено. Следователно Ф ще вземе всички големи положителни стойности, тоест Ф max = + ¥.

Така че целевата функция Ф не е ограничена отгоре, така че няма оптимално решение.

ЗАДАЧА 2.Г. Напишете задача, двойна на дадената.

оригинална задача.

Вариант 7. Максимизиране на целевата функция Ф = 2× x 1 - x 4

с ограничения: x 1 + x 2 \u003d 20,

х 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Решение:

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

x 1 + x 2 = 20,

х 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

Имаме асиметрична задача от 2-ри тип. Двойният проблем ще изглежда така:

Минимизиране на целевата функция F = 20 × y 1 + 5 × y 2 + 8 × y 3

за y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Вариант 8. Максимизирайте целевата функция Ф \u003d x 2 - x 4 - 3× х 5

с ограничения: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (аз = 1, 6)

Решение:

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

Първоначален проблем: Двоен проблем:

F = C × X max F = B T × Имин

при А × X \u003d B в A T × Y ≥ C T

В оригиналната задача матрицата-ред от коефициенти за променливи в целевата функция има формата С = (0; 1; 0; -1; -3; 0),

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

B \u003d 2, A \u003d 0 - 4 1 2 -1 0

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

0 1 0 0 V T \u003d (1; 2; 5)

A T = -1 2 0 C T = -1

Двойният проблем може да бъде написан в следната форма:

намерете минималната стойност на целевата функция F = y 1 + 2 × y 2 + 5 × y 3

при ограничения y 1 ≥ 0,

2× y 1-4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Вариант 10. Минимизирайте функцията Ф = x 1 + x 2 + x 3

ограничено: 3× х 1 + 9× х 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Решение:

Имаме първоначалния проблем за минимизиране със система от ограничения под формата на неравенства, тоест двойка двойни проблеми има симетрична форма от 3-ти тип, чийто математически модел в матрична форма има формата:

Първоначален проблем Двойна задача

F = C × X min F \u003d B T × Ymax

при А × х ≥ B в A T × Y ≤ C T

X ≥ 0 Y ≥ 0

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

C \u003d (1; 1; 1), B \u003d 3, A = 6 4 5

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

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Двойният проблем се формулира така:

Максимизиране на целевата функция F = 2y 1 + 3y 2 + 4y 3

под ограничения 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ЗАДАЧА 2.В. Решаване на задача за линейно програмиране с помощта на симплексни таблици.

Вариант 7. Максимизиране на целевата функция Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

при ограничения: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Решение:

Ние свеждаме системата от ограничения до каноничната форма

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Имаме система от 3 уравнения със 7 неизвестни. Избираме x 1 , z 1 , z 3 като основни 3 променливи, x 2 , x 3 , x 4 , z 2 като свободни, изразяваме основните променливи чрез тях.

От (2) имаме x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Заместете в (1) и (3), получаваме

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

Съставете симплексна таблица

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	4	0	18	-17	13	0	4	1	4/13	13/8
Е	2	0	— 3	7	— 8	0	— 2	0		1

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

II итерация Таблица 2

х 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Е	4	0	4	— 4	0	1	0	0		32/7

X 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 \u003d 4.

III итерация Таблица 3

х 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
х 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Е	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 \u003d 52/7.

IV итерация Таблица 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
х 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Е	149/14	45/14	15	0	0	0	3/14	19/14

X 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 \u003d 149/14.

В индексния ред на последната таблица няма отрицателни числа, т.е. в израза за целевата функция всички Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Отговор: Ф max = 149/14,

оптимално решение (0; 0; 25/14; 37/14; 1/2; 0; 0)

Вариант 8. Минимизиране на целевата функция Ф = 5 x 1 - x 3

при ограничения: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

x 2 + 2 x 4 \u003d 1,

Решение:

Броят на променливите е 4, рангът на матрицата е ​​2, следователно броят на свободните променливи е r \u003d 4 - 2 \u003d 2, броят на основните променливи също е 2. Взимаме x 3, x 4 като свободни променливи, ние ще изразим основните променливи x 1, x 2 по отношение на свободните и привеждаме системата към базисната единица:

x 2 \u003d 1 - 2 x 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

Ф \u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Записваме системата от уравнения и целевата функция във форма, удобна за симплексната таблица, т.е. x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ф + 11 х 3 - 15 х 4 \u003d 10

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	2	1	0		— 3		1/2
x2	1	0	1	0	2
Е	10	0	0	11	— 15		— 11/2

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

II итерация Таблица 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
Е	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

III итерация Таблица 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
Е	— 7/4	— 11/2	— 3/4	0	0

X 3 \u003d (0; 0; 7/4; 1/2) F 3 \u003d -7/4.

В индексния ред на последната таблица няма положителни числа, т.е. в израза за целевата функция всички Г i > 0. Имаме случай I, следователно последното основно решение е оптимално.

Отговор: Ф min = -7/4, оптимално решение (0; 0; 7/4; 1/2)

********************

Вариант 10. Минимизирайте целевата функция Ф \u003d x 1 + x 2,

с ограничения: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Решение:

Броят на променливите е 5, рангът на матрицата е ​​3, следователно броят на свободните променливи е r \u003d 6-3 \u003d 2. Взимаме x 3 и x 4 като свободни променливи, x 1, x 2, x 5 като основни. Всички уравнения на системата вече са сведени до една основа (основните променливи са изразени чрез свободни), но са написани във форма, която не е удобна за използване на симплексни таблици. Записваме системата от уравнения във формата

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

x 5 + x 3 - x 4 . = 5

Изразяваме целевата функция чрез свободни променливи и я записваме във формата Ф - 3 x 3 +3 x 4 = 3

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	2	1	0	-2	1	0	2	-1/2
х 2	1	0	1	-1		0	1/2	1/2
х 5	5	0	0	1	-1	1		1/2
Е	3	0	0	-3	3	0		-3/2

X 1 \u003d (2; 3; 0; 0; 5) F 1 \u003d 3.

таблица 2

х 1	3/2	1	-1/2	-3/2	0	0
х 4	1/2	0	1/2	-1/2	1	0
х 5	11/2	0	1/2	1/2	0	1
Е	3/2	0	-3/2	-3/2	0	0

X 2 \u003d (3/2; 0; 0; 1/2; 11/2) F 2 \u003d 3/2.

В индексния ред на последната таблица няма положителни числа, т.е. в израза за целевата функция всички Гi > 0. Имаме случай 1, следователно последното основно решение е оптимално.

Отговор: Ф min = 3/2, оптималното решение е (3/2; 0; 0; 1/2; 11/2).

Разделяме третия ред на ключовия елемент, равен на 5, получаваме третия ред на новата таблица.

Базовите колони съответстват на единични колони.

Изчисляване на останалите стойности на таблицата:

"BP - Основен план":

; ;

"x1": ; ;

"x5": ; .

Стойностите на индексния ред са неотрицателни, следователно получаваме оптималното решение: , ; .

Отговор:максималната печалба от продажбата на произведени продукти, равна на 160/3 единици, се осигурява от освобождаването само на продукти от втори тип в размер на 80/9 единици.

Задача номер 2

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

защото последната цифра на шифъра е 8, тогава A=2; B=5.

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

Решение:

1) Нека начертаем областта, която определя системата от неравенства.

Тази област е триъгълник ABC с координати на върховете: A(0; 2); B(4; 6) и C(16/3; 14/3).

Целевите функционални нива са кръгове с център в точката (2; 5). Квадратите на радиусите ще бъдат стойностите на целевата функция. Тогава фигурата показва, че минималната стойност на целевата функция се достига в точка H, максималната стойност е или в точка A, или в точка C.

Стойността на целевата функция в точка А: ;

Стойността на целевата функция в точка C: ;

Това означава, че максималната стойност на функцията се достига в точката A(0; 2) и е равна на 13.

Нека намерим координатите на точка H.

За да направите това, помислете за системата:

ó

ó

Една права е допирателна към окръжност, ако уравнението има единствено решение. Квадратно уравнениеима уникално решение, ако дискриминантът е 0.

Тогава ; ; - минималната стойност на функцията.

2) Съставете функцията на Лагранж, за да намерите минималното решение:

При х 1 =2.5; х 2 =4.5 получаваме:

ó

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

Съставяме функцията на Лагранж за намиране на максималното решение:

Достатъчни условия за екстремум:

При х 1 =0; х 2 =2 получаваме:

ó ó

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

Отговор:минимумът на целевата функция се достига при ; ; максималната целева функция се достига, когато ; .

Задача номер 3

На две предприятия са отпуснати средства в размер дединици. При разпределение на първото предприятие за една година хпарични единици осигурява доход к 1 хединици, а когато се разпределят към второто предприятие гпарични единици, той осигурява доход к 1 гединици. Салдото на средствата в края на годината за първото предприятие е равно на nx, а за второто моя. Как да разпределим всички средства в рамките на 4 години, така че общият приход да е най-голям? Решете проблема чрез динамично програмиране.

i=8, k=1.

А=2200; k 1 =6; k 2 =1; п=0,2; m=0,5.

Решение:

Целият период от 4 години е разделен на 4 етапа, всеки от които е равен на една година. Нека номерираме етапите, започвайки от първата година. Нека X k и Y k са средствата, разпределени съответно на предприятия A и B на k-тия етап. Тогава сумата X k + Y k =a k е общата сума на средствата, използвани на k - този етап и оставащи от предишния етап k - 1. на първия етап се използват всички разпределени средства и a 1 = 2200 единици. доходът, който ще бъде получен на k - този етап, когато се разпределят X k и Y k единици, ще бъде 6X k + 1Y k . нека максималният доход, получен на последните етапи, започвайки от k - този етап е f k (a k) единици. Нека напишем функционалното уравнение на Белман, изразяващо принципа на оптималност: каквото и да е първоначалното състояние и първоначалното решение, последващото решение трябва да бъде оптимално по отношение на състоянието, получено в резултат на първоначалното състояние:

За всеки етап трябва да изберете стойността X k и стойността Y k=ак- Хк. Имайки това предвид, ще намерим доход на k-тия етап:

Функционалното уравнение на Белман ще изглежда така:

Обмислете всички етапи, като започнете с последния.

(тъй като максимумът на линейната функция се достига в края на сегмента при x 4 = a 4);

федерална агенцияна образованието

Държавно бюджетно учебно заведение

висше професионално образование

"Омски държавен технически университет"

ИЗЧИСЛИТЕЛНО-ГРАФИЧНА РАБОТА

по дисциплина"ТЕОРИЯ ЗА ОПТИМАЛНО УПРАВЛЕНИЕ »

по темата "МЕТОДИ ЗА ОПТИМИЗАЦИЯ И ИЗСЛЕДВАНЕ НА ОПЕРАЦИИ »

вариант 7

Завършено:

задочно студент

4-та година група ЗА-419

Име: Кужелев С. А.

Проверено:

Девятерикова М.В.

Омск - 2012 г
^

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

7) 7х 1 + 6х 2 → макс 20х 1 + 6х 2 ≤ 15 16х 1 − 2х 2 ≤ 18 8х 1 + 4х 2 ≤ 20 13х 1 + 3х 2 ≤ 4 х 1 , х 2 ≥ 0.

Стъпка 1. Изграждане на валидна област

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

Първото ограничение на модела е . Заменяйки знака ≤ в него със знака =, получаваме уравнението . На фиг. 1.1 той дефинира права (1), която разделя равнината на две полуравнини, в този случай над и под правата. Да се ​​избере кой удовлетворява неравенството , ние заместваме в него координатите на всяка точка, която не лежи на дадената права (например началото х 1 = 0, х 2 = 0). Тъй като получаваме правилния израз (20 0 + 6 0 = 0 ≤15), полуравнината, съдържаща началото (отбелязана със стрелка), удовлетворява неравенството. Иначе друга полуравнина.

Продължаваме по подобен начин с останалите ограничения на проблема. Пресечната точка на всички построени полуравнини се образува с първия квадрант ABCD(виж фиг. 1). Това е валидният обхват на задачата.

Стъпка 2. Изграждане на линия на ниво Линия на ниво целевата функция е набор от точки в равнината, където се намира целевата функция постоянна стойност. Такъв набор е даден от уравнението f ( х) = конст. Да сложим например конст = 0 и начертайте линия на нивото f ( х) = 0, т.е. в нашия случай директно 7 х 1 + 6х 2 = 0.

Тази права минава през началото и е перпендикулярна на вектора. Този вектор е градиентът на целевата функция при (0,0). Градиентът на функция е вектор от стойности на частните производни на дадена функция във въпросната точка. В случая на задачата LP частните производни на целевата функция са равни на коефициентите ° Саз, й = 1 , ..., н.

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

Той се намира в пресечната точка на линиите (2) и (3) (виж фиг. 1) и задава оптималното решение.

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

^ Стъпка 3. Определяне на координатите на максималната (минималната) точка и оптималната стойност на целевата функция

За да се намерят координатите на точка C, е необходимо да се реши система, състояща се от съответните директни уравнения (в този случай от уравнения 2 и 3):

16х 1 − 2х 2 ≤ 18

8х 1 + 4х 2 ≤ 20

Получаваме оптималното решение = 1,33.

^ Оптималната стойност на целевата функция f * = f (Х*) = 7 * 0 + 6 * 1,33 = 7,8