намирам графичен методмаксимум целева функция
F= 2х 1 + 3х 2 ® макс
С ограничения
Решениеизползвайки Excel таблици
Първо, нека го изградим върху лист хартия Решение на Excelсистеми от неравенства.
Нека разгледаме първото неравенство.
Нека построим гранична линия, използвайки две точки. Означаваме правата линия (L1) (или Row1). Координати х 2 изчисляваме по формулите:
За да конструирате, изберете точкова диаграма
Избор на данни за директно
Променете името на реда:
Избор на оформление на диаграма. Променете името на координатните оси:
Права линия (L1) на графиката:
Решението на строгото неравенство може да се намери с помощта на една тестова точка, която не принадлежи на правата (L1). Например с помощта на точката (0; 0)П(L1).
0 + 3×0< 18 или 0 < 18 .
Неравенството е вярно, следователно решението на неравенство (1) ще бъде полуравнината, в която се намира пробната точка (на фигурата по-долу, линия L1).
След това решаваме неравенство (2).
Нека построим гранична линия 2, използвайки две точки. Означаваме правата с (L2).
Права линия (L2) на графиката:
Решението на строго неравенство 2 може да бъде намерено с помощта на една тестова точка, която не принадлежи на правата (L2). Например с помощта на точката (0; 0)П(L2).
При заместване на координатите на точката (0; 0) получаваме неравенството
2 × 0 + 0< 16 или 0 < 16 .
Неравенството е вярно, следователно решението на неравенство (2) ще бъде полуравнината, в която се намира пробната точка (на фигурата под линия L2).
След това решаваме неравенство (3).
Нека построим гранична линия, използвайки две точки. Означаваме правата линия (L3).
Права линия (L3) на графиката:
Решението на строго неравенство 2 може да бъде намерено с помощта на една тестова точка, която не принадлежи на правата (L3). Например с помощта на точката (0; 0)П(L3).
При заместване на координатите на точката (0; 0) получаваме неравенството
Неравенството е вярно, следователно решението на неравенство (3) ще бъде полуравнината, в която се намира пробната точка (на фигурата под линия L3).
След това решаваме неравенство (4).
Нека построим гранична линия, използвайки две точки. Означаваме правата линия (L4).
Добавете данни към лист на Excel
Права линия (L4) на графиката:
Решаване на строго неравенство 3 х 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).
При заместване на координатите на точката (0; 0) получаваме неравенството
Неравенството е вярно, следователно решението на неравенство (4) ще бъде полуравнината, в която се намира пробната точка (на фигурата отляво на линия L4).
Чрез решаване на две неравенства (5) и (6)
е 1-ва четвърт, ограничена от координатните линии и .
Системата от неравенства е решена. Чрез решаване на системата от неравенства (1) – (6) в в този примере изпъкнал многоъгълник в долния ляв ъгъл на фигурата, ограничен от линии L1, L2, L3, L4 и координатни линии и . Можете да се уверите, че многоъгълникът е избран правилно, като замените тестова точка, например (1; 1), във всяко неравенство на оригиналната система. Когато заместваме точката (1; 1), откриваме, че всички неравенства, включително естествените ограничения, са верни.
Нека сега разгледаме целевата функция
F= 2х 1 + 3х 2 .
Нека построим линии на ниво за стойностите на функцията F=0И F=12(числовите стойности се избират произволно). Добавете данни към лист на Excel
Линии на ниво на диаграмата:
Нека конструираме насочващ вектор (или градиент) (2; 3). Координатите на вектора съвпадат с коефициентите на целевата функция Е.
Решение: намерете максималната и минималната стойност на функцията \(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\). Прав AB
Областта на допустимите решения се определя като общата част на трите полуравнини, съответстващи на тези неравенства. Тази област е триъгълник \(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\)
Нека построим на равнината множество от допустими решения на системата линейни неравенстваи намерете геометрично минималната стойност на целевата функция.
Изграждаме прави линии в координатната система x 1 x 2
Намираме полуравнините, определени от системата. Тъй като неравенствата на системата са изпълнени за всяка точка от съответната полуравнина, достатъчно е да ги проверим за всяка една точка. Използваме точката (0;0). Нека заместим неговите координати в първото неравенство на системата. защото , тогава неравенството определя полуравнина, която не съдържа точката (0;0). По подобен начин дефинираме останалите полуравнини. Ние намираме множеството от възможни решения като обща частот получените полуравнини е защрихованата област.
Построяваме вектор и линия на нулево ниво, перпендикулярна на него.
Премествайки права линия (5) в посока на вектора, виждаме, че максималната точка на областта ще бъде в точка А на пресечната точка на права линия (3) и права линия (2). Намираме решението на системата от уравнения:
Това означава, че получихме точката (13;11) и.
Премествайки права линия (5) в посока на вектора, виждаме, че минималната точка на областта ще бъде в точка B на пресечната точка на права линия (1) и права линия (4). Намираме решението на системата от уравнения:
Това означава, че получихме точката (6;6) и.
2. Мебелна фирма произвежда комбинирани шкафове и компютърни маси. Производството им е ограничено от наличието на суровини (висококачествени плоскости, обков) и времето на работа на машините, които ги обработват. За всеки шкаф са необходими 5 м2 дъски, за маса - 2 м2. Фитингите струват $10 за един шкаф и $8 за една маса. Компанията може да получи от своите доставчици до 600 m2 плоскости на месец и аксесоари на стойност $2000. Всеки шкаф изисква 7 часа работа на машината, а масата изисква 3 часа. Месечно могат да се използват общо 840 работни часа на машината.
Колко комбинирани шкафове и компютърни маси трябва да произвежда една компания на месец, за да увеличи максимално печалбите, ако един шкаф носи $100 печалба и всяко бюро носи $50?
- 1. Създайте математически модел на задачата и я решете с помощта на симплексния метод.
- 2. Създайте математически модел на двойствения проблем, запишете решението му въз основа на решението на оригиналния.
- 3. Установете степента на недостиг на използваните ресурси и обосновете рентабилността на оптималния план.
- 4. Проучете възможностите за по-нататъшно увеличаване на производствената продукция в зависимост от използването на всеки вид ресурс.
- 5. Оценете осъществимостта на въвеждането на нов вид продукт - рафтове за книги, ако производството на един рафт струва 1 m 2 дъски и аксесоари на стойност $5 и е необходимо да се изразходват 0,25 часа работа на машината и печалбата от продажбата на един рафт е $20.
- 1. Нека изградим математически модел за този проблем:
Нека обозначим с x 1 обема на производството на шкафове и x 2 обема на производството на маси. Нека създадем система от ограничения и целева функция:
Решаваме задачата с помощта на симплексния метод. Нека го напишем в канонична форма:
Нека напишем данните за задачата под формата на таблица:
маса 1
защото Сега всички делти са по-големи от нула, тогава по-нататъшно увеличаване на стойността на целевата функция f е невъзможно и ние сме получили оптимален план.
ТЕМА: ЛИНЕЙНО ПРОГРАМИРАНЕ
ЗАДАЧА 2.А. Решаване на задача от линейно програмиране по графичен метод
внимание!
Това е ПРОБНА ВЕРСИЯ на работа № 2073, цената на оригинала е 200 рубли. Проектиран в Програма на MicrosoftСлово.
Плащане. Контакти.
Вариант 7. Намерете максималната и минималната стойностлинейна функция Ф = 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.
Нека построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата избираме полуравнините и получаваме тяхната обща част - областта на допустимите решения на ODR - четириъгълника MNPQ.
Минимална стойност на функцията
ции - в точка М(2; 2)
Ф min = 2·2 - 2·2 = 0.
Максималната стойност се достига в точка N (10; 0),
Ф max = 2·10 - 2·0 = 20.
Вариант 8. Намерете максималната и минималната стойност
линейна функция Ф = 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;
Нека построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата избираме полуравнините и получаваме тяхната обща част - областта на допустимите решения на ODR - неограничения многоъгълник MNPQ.
Минимална стойност на функцията
ции – на директен НП, например
в точка P(4; 0)
Ф min = 4 + 0 = 4.
ODR не е ограничен отгоре, следователно Ф max = + ∞.
Вариант 10. Намерете максималната и минималната стойност
линейна функция Ф = 2 х 1 - 3 х 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).
Нека да построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата да изберем полуравнините и да получим тяхната обща част - областта на допустимите решения на ODR - многоъгълника MNPQRS.
Да построим вектора Г(2; -3) и да прекараме началото на координатите линия на ниво– прав.
Преместваме линията на нивото в посока, стойността на Ф се увеличава. В точка S(7; 0) целевата функция достига максимум Ф max =2·7–3·0= = 14. Преместваме линията на нивото в посока, стойността на Ф намалява. Минималната стойност на функцията е в точка N(0; 5)
Ф min = 2·0 – 3·5 = –15.
ЗАДАЧА 2.Б. Решаване на задача от линейно програмиране
аналитичен симплекс метод
Вариант 7. Минимизиране на целевата функция Ф = 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 = 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 = 2 – 3 x 1 + 4 x 3 – 2 x 6
x 4 = 9 – x 1 – 6 x 6 (*)
x 5 = 6 – x 1 – 2 x 3 – 2 x 6
Целевата функция ще изглежда така:
Ф = 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 = x 3 = x 6 = 0, а основните променливи ще приемат стойностите x 2 = 2; х 4 = 9; x 5 = 6, т.е. първото допустимо решение (0; 2; 0; 9; 6; 0), целева функция Ф 1 = 13.
Променливите x 3 и x 6 са включени в целевата функция с отрицателни коефициенти, следователно, когато техните стойности се увеличават, стойността на Ф ще намалява. Да вземем х 6 например. От първото уравнение на системата (*) става ясно, че е възможно увеличение на стойността на x 6 до x 6 = 1 (докато x 2 ³ 0). В този случай x 1 и x 3 остават равни на нула. Сега вземаме x 4, x 5, x 6 като основни променливи и x 1, x 2, x 3 като свободни променливи. Нека изразим новите основни променливи чрез новите свободни. Получаваме
x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3
x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3
x 5 = 4 + 2 x 1 + x 2 – 6 x 3
Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3
Нека присвоим нулеви стойности на свободните променливи, тоест x 1 = x 2 = x 3 = 0, докато x 6 = 1, x 4 = 3, x 5 = 4, тоест третото възможно решение (0 0; 4; В този случай Ф 3 = 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 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4
x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4
x 6 = 3/2 – 1/6 x 1 – 1/6 x 4
Целевата функция ще приеме формата
Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4
Променливите x 1 и x 2 са включени в целевата функция с отрицателни коефициенти, следователно, когато техните стойности се увеличават, стойността на Ф ще намалява. Да вземем х 2 например. От второто уравнение на системата става ясно, че е възможно увеличение на стойността на x 2 до x 2 = 5 (докато x 5 ³ 0). В този случай x 1 и x 4 остават нула, стойностите на другите променливи са равни на x 3 = 3/2; x 5 = 0, x 6 = 3/2, т.е. четвъртото възможно решение (0; 5; 3/2; 0; 0; 3/2). В този случай Ф 4 = 5/4.
Сега вземаме x 1, x 4 и x 5 като нови свободни променливи. Нека изразим чрез тях новите базисни променливи x 2, x 3, x 6. Да вземем системата
x 2 = 5 – 4 x 1 + x 4 – 2 x 5
x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5
x 6 = 3/2 – 1/6 x 1 – 1/6 x 4
Целевата функция ще приеме формата
Ф = - 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 = 30;
x 3 + x 5 - 2 x 6 = 6;
2 x 4 + 3 x 5 - 2 x 6 = 18;
Решение:
Броят на уравненията е 4, броят на неизвестните е 6. Следователно r = n – m = 6 – 4 = 2 променливи могат да бъдат избрани като свободни променливи, 4 променливи като основни. Избираме x 5 и x 6 като свободни, а x 1 , x 2 , x 3 , x 4 като основни. Нека изразим основните променливи чрез свободни и редуцираме системата от уравнения до единица
x 1 = 12 - x 5 - x 6;
x 2 = 30 - 5 x 5 + x 6;
x 3 = 6 - x 5 + 2 x 6;
x 4 = 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 = 12 - x 1 - x 5;
x 2 = 42 - x 1 - 6 x 5;
x 3 = 30 - 2 x 1 - 3 x 5;
x 4 = 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 = 5 - 5/6 x 1 + 1/6 x 2;
x 5 = 7 - 1/6 x 1 - 1/6 x 2;
x 3 = 9 - 3/2 x 1 + 1/2 x 2;
x 4 = 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.
И двете променливи влизат в целевата функция с отрицателни коефициенти, т.е. по-нататъшно увеличаване на Ф е невъзможно.
Следователно последното възможно решение е оптимално, т.е. X opt = (0, 0, 9, 7/2, 7, 5) и Ф max = 38.
Вариант 10. Максимизиране на целевата функция Ф = x 2 + x 3
с ограничения: x 1 - x 2 + x 3 = 1,
x 2 - 2 x 3 + x 4 = 2.
Решение:
Системата от уравнения-ограничения е последователна, тъй като ранговете на матрицата на системата от уравнения и разширената матрица са еднакви и равни на 2. Следователно две променливи могат да се приемат за свободни, а другите две променливи - основни - могат се изразяват линейно чрез две свободни.
Нека вземем x 2 и x 3 като свободни променливи. Тогава основните променливи ще бъдат x 1 и x 2, които ще изразим чрез свободни
x 1 = 1 + x 2 - x 3; (*)
x 4 = 2 - x 2 + 2 x 3;
Целевата функция вече е изразена чрез x 2 и x 3, т.е. Ф = x 2 + x 3.
За x 2 =0 и x 3 =0 основните променливи ще бъдат равни на x 1 = 1, x 4 = 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 = 1 - x 1 + x 2 ; (**)
x 4 = 4 - 2 x 1 + x 2 ;
Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2
Приравнявайки свободните променливи на нула, получаваме второто допустимо базисно решение X 2 = (0; 0; 1; 4), за което Ф 2 = 1.
Увеличаване на Ф е възможно с увеличение на х2. Увеличението на x 2, съдейки по последната система от уравнения (**), не е ограничено. Следователно Ф ще става все по-голям положителни стойности, тоест F max = + ¥.
Така че целевата функция Ф не е ограничена отгоре, следователно няма оптимално решение.
ЗАДАЧА 2.Г. Съставете задача, двойна на дадената
оригиналната задача.
Вариант 7. Максимизиране на целевата функция Ф = 2× x 1 - x 4
с ограничения: x 1 + x 2 = 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 = 5,
- x 1 + x 2 + x 3 + x 6 = 8.
Получихме асиметрична задача от тип 2. Двойният проблем ще изглежда така:
Минимизирайте целевата функция F = 20 × y 1 + 5 × у2+8 × y 3
на y 1 - y 3 ≥ 2,
y 1 + y 2 + y 3 ≥ 0,
y 3 ≥ 0,
2× y 2 ≥ 1,
Y2 ≥ 0,
y 3 ≥ 0.
Вариант 8. Максимизиране на целевата функция Ф = x 2 - x 4 - 3× х 5
с ограничения: x 1 + 2× x 2 - x 4 + x 5 = 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 × Y мин
при А × X = B при A T × Y ≥ C T
В оригиналната задача матрицата на редовете на коефициентите за променливи в целевата функция има формата C = (0; 1; 0; -1; -3; 0),
матрицата-колона от свободни членове и матрицата от коефициенти за променливи в системата от ограничения имат формата
B = 2, A = 0 - 4 1 2 -1 0
Нека намерим транспонираната матрица от коефициенти, матрица от редове от коефициенти за променливи в целевата функция и матрица от колони от свободни членове
0 1 0 0 V T = (1; 2; 5)
A T = -1 2 0 C T = -1
Двойният проблем ще бъде написан в следната форма:
намерете минималната стойност на целевата функция F = y 1 + 2 × у2+5 × y 3
при ограничения y 1 ≥ 0,
2× y 1 - 4 × у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 = B T × Y макс
при А × х ≥ B в A T × Y ≤ С Т
X ≥ 0 Y ≥ 0
В оригиналната задача матрицата-ред от коефициенти за променливи в целевата функция, матрицата-колона от свободни членове и матрицата от коефициенти за променливи в системата от ограничения имат формата
C = (1; 1; 1), B = 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 × у2+8 × y 3 ≤ 1,
9× y 1 + 4 × у2+2 × y 3 ≤ 1,
7× y 1 + 5 × у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 неизвестни. Нека да изберем 3 променливи x 1 , z 1 , z 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 = 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 = 2.
Нека създадем симплексна таблица
I итерация Таблица 1
| Основен AC | Свободата. AC | |||||||||
| х 1 | 1 | 1 | — 2 | 5 | — 3 | 0 | — 1 | 0 | 3/8 | |
| z 1 | 2 | 0 | 7 | -11 | 1 | 2 | 0 | 1/ 4 | 1/8 | |
| z 3 | 4 | 0 | 18 | -17 | 13 | 0 | 4 | 1 | 4/13 | 13/8 |
| Е | 2 | 0 | — 3 | 7 | — 8 | 0 | — 2 | 0 | 1 |
X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.
II итерация Таблица 2
| х 1 | 14/8 | 1 | 5/8 | 7/8 | 0 | 3/8 | -2/8 | 0 | 2 | — 1 |
| х 4 | 1/ 4 | 0 | 7/8 | -11/8 | 1 | 1/8 | 2/8 | 0 | 11/7 | |
| z 3 | 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 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.
III итерация Таблица 3
| х 1 | 1 | 1 | — 6 | 0 | 0 | -1 | — 1 | 1/2 | ||
| х 4 | 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 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.
IV итерация Таблица 4
| z 1 | 1/ 2 | 1/2 | — 3 | 0 | 0 | 1 | -1/2 | -1/2 | ||
| х 4 | 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 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.
Няма последна таблица в индексния ред отрицателни числа, тоест в израза за целевата функция всички Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.
Отговор: Ф m ax = 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 = 3,
x 2 + 2 x 4 =1,
Решение:
Броят на променливите е 4, рангът на матрицата е 2, следователно броят на свободните променливи е r = 4 - 2 = 2, броят на основните променливи също е 2. Нека вземем x 3, x 4 като свободни променливи, изразете основните променливи x 1, x 2 по отношение на свободните и Нека редуцираме системата до единица:
x 2 = 1 - 2 x 4,
x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4
Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 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
F + 11 x 3 - 15 x 4 = 10
Да направим маса
I итерация Таблица 1
| Основен AC | Свободата. AC | ||||||
| X 1 | 2 | 1 | 0 | — 3 | 1/2 | ||
| X 2 | 1 | 0 | 1 | 0 | 2 | ||
| Е | 10 | 0 | 0 | 11 | — 15 | — 11/2 |
X 1 = (2; 1; 0; 0) F 1 = 10.
II итерация Таблица 2
| X 3 | 1 | 1/2 | 0 | 1 | -3/2 | 3/4 | |
| X 2 | 1 | 0 | 1 | 0 | 1/2 | ||
| Е | — 1 | — 11/2 | 0 | 0 | 3/2 | — 3/4 |
X 2 = (0; 1; 1; 0) Ф 2 = -1.
III итерация Таблица 3
| X 3 | 7/4 | 1/2 | 3/4 | 1 | 0 | ||
| X 4 | 1/2 | 0 | 1/2 | 0 | 1 | ||
| Е | — 7/4 | — 11/2 | — 3/4 | 0 | 0 |
X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.
В индексния ред на последната таблица няма положителни числа, т.е. в израза за целевата функция всички Г i > 0. Имаме случай I, следователно последното основно решение е оптимално.
Отговор: Ф min = -7/4, оптимално решение (0; 0; 7/4; 1/2)
********************
Вариант 10. Минимизиране на целевата функция Ф = x 1 + x 2,
при ограничения: x 1 –2 x 3 + x 4 = 2,
x 2 – x 3 + 2 x 4 = 1,
Решение:
Броят на променливите е 5, рангът на матрицата е 3, следователно броят на свободните променливи е r = 6-3 = 2. Нека вземем x 3 и x 4 като свободни променливи и x 1 , x 2 , х 5 като основни. Всички уравнения на системата вече са сведени до единица (основните променливи са изразени чрез свободни), но са написани във форма, която не е удобна за използване на симплексни таблици. Нека запишем системата от уравнения във формата
x 1 - 2 x 3 + x 4 = 2
x 2 - x 3 +2 x 4 = 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 = (2; 3; 0; 0; 5) F 1 = 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 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.
В индексния ред на последната таблица няма положителни числа, тоест в израза за целевата функция всички Gi > 0. Имаме случай 1, следователно последното основно решение е оптимално.
Отговор: Ф min = 3/2, оптимално решение (3/2; 0; 0; 1/2; 11/2).