Симплексен метод - правило за липса на решение. Пример за решаване на проблем. Симплексен метод за решаване на LLP. Пример за решение с помощта на P-метод
Цел на услугата. Услугата е предназначена за онлайн решенияПроблеми с линейно програмиране (LPP) с помощта на симплексния метод в следните формизаписи:
- под формата на симплексна таблица (метод на трансформация на Йордан); основна форма за запис;
- модифициран симплекс метод; под формата на колона; под формата на линия.
Инструкции. Изберете броя на променливите и броя на редовете (броя на ограниченията). Полученото решение се записва във файл на Word и Excel. В този случай не вземайте предвид ограничения като x i ≥0. Ако няма ограничения в задачата за някои x i, тогава ZLP трябва да се преобразува в KZLP или да се използва тази услуга. При решаване използването се определя автоматично М-метод(симплексен метод с изкуствена основа) и двуетапен симплекс метод.
Следните също се използват с този калкулатор:
Графичен метод за решаване на ЗЛП
Решение на транспортния проблем
Решаване на матрична игра
С помощта на онлайн услугата можете да определите цената на матрична игра (долна и горна граница), да проверите за наличието на седлова точка, да намерите решение на смесена стратегия, като използвате следните методи: минимаксен, симплексен метод, графичен (геометричен ) метод, метод на Браун.
Екстремум на функция на две променливи
Проблеми на динамичното програмиране
Разпределете 5 хомогенни партиди стоки между три пазара, така че да получите максимален доход от продажбата им. Приходите от продажби на всеки пазар G(X) зависят от броя на продадените партиди от продукта X и са представени в таблицата.
| Обем на продукта X (в партиди) | Приходи G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Алгоритъм на симплексния методвключва следните стъпки:
- Изготвяне на първия основен план. Преход към каноничната форма на задачата за линейно програмиране чрез въвеждане на неотрицателни допълнителни балансови променливи.
- Проверка на плана за оптималност. Ако има поне един коефициент на индексна линия по-малък от нула, тогава планът не е оптимален и трябва да бъде подобрен.
- Определяне на водещата колона и ред. От отрицателните коефициенти на индексната линия се избира най-големият по абсолютна стойност. След това елементите на колоната със свободни членове на симплексната таблица се разделят на елементи от същия знак на водещата колона.
- Изграждане на нов референтен план. Преходът към нов план се извършва в резултат на преизчисляване на симплексната таблица по метода на Йордан-Гаус.
Ако е необходимо да се намери екстремума на целевата функция, тогава ние говорим заотносно намирането на минималната стойност (F(x) → min, вижте примера за решение за минимизиране на функция) и максималната стойност (F(x) → max, вижте примера за решение за максимизиране на функция)
Екстремно решение се постига на границата на областта на допустимите решения в един от върховете на ъгловите точки на многоъгълника или на сегмента между две съседни ъглови точки.
Основна теорема на линейното програмиране. Ако целевата функция на ZLP достигне екстремна стойност в дадена точка от областта на възможните решения, тогава тя приема тази стойност в ъгловата точка. Ако целевата функция на ZLP достигне екстремна стойност в повече от една ъглова точка, тогава тя приема същата стойност във всяка от изпъкналите линейни комбинации от тези точки.
Същността на симплексния метод. Движението до оптималната точка се осъществява чрез преместване от една ъглова точка към съседна, което доближава и по-бързо до X опт. Такава схема за изброяване на точки, наречен симплекс метод, предложено от Р. Данциг.
Ъгловите точки се характеризират с m основни променливи, така че преходът от една ъглова точка към съседна може да се осъществи чрез промяна на само една основна променлива в основата към променлива от не-базис.
Реализация на симплексния метод в сила различни функциии формулировки на проблеми, LP има различни модификации.
Изграждането на симплексни таблици продължава до получаването му оптимално решение.
Как можете да използвате симплексна таблица, за да определите, че решението на проблем с линейно програмиране е оптимално?
Ако последният ред (стойности на целевата функция) не съдържа отрицателни елементи, следователно, той ще намери оптималния план.
Бележка 1. Ако една от основните променливи е равна на нула, тогава екстремната точка, съответстваща на такова основно решение, е изродена. Дегенерация възниква, когато има неяснота в избора на водещата линия. Може изобщо да не забележите израждането на проблема, ако изберете друга линия като ориентир. В случай на неяснота трябва да се избере редът с най-нисък индекс, за да се избегне зацикляне.
Бележка 2. Нека в някаква крайна точка всички симплексни разлики са неотрицателни D k ³ 0 (k = 1..n+m), т.е. се получава оптимално решение и съществува A k - небазисен вектор, за който D k = 0. Тогава максимумът се постига поне в две точки, т.е. има алтернативен оптимум. Ако въведем тази променлива x k в основата, стойността на целевата функция няма да се промени.
Бележка 3. Решението на двойствения проблем се намира в последната симплексна таблица. Последните m компонента на вектора на симплексните разлики (в колоните на балансовите променливи) са оптималното решение на двойствения проблем. Стойностите на целевите функции на директните и двойните задачи в оптимални точки съвпадат.
Бележка 4. При решаване на задачата за минимизиране векторът с най-голямата положителна симплексна разлика се въвежда в основата. След това се прилага същият алгоритъм, както при проблема с максимизирането.
Ако е посочено условието „Необходимо е суровините от тип III да бъдат напълно изразходвани“, тогава съответното условие е равенство.
Аналитично въведение в симплексния метод
Симплексен методе универсален метод за линейно програмиране.Така че, ако решим ZLP в канонична форма, тогава системата от ограничения е обикновена система от линейни уравнения. При решаване на задачи на ЛП се получават системи от линейни уравнения, които като правило имат безкрайно много решения.
Например, нека системата бъде дадена
Тук броят на уравненията е 2, а броят на неизвестните е 3, има по-малко уравнения. Нека изразим x 1 и x 2 чрез x 3:
Това е общото решение на системата. ако на променливата x 3 са дадени произволни числени стойности, тогава ще намерим частични решения на системата. Например, х 3 =1 → х 1 =1 → х 2 =6. Имаме (1, 6, 1) - конкретно решение. Позволявам х 3 =2 → х 1 =-3, х 2 = 1, (-3, 1, 2) - друго конкретно решение. Има безкрайно много такива конкретни решения.
Променливи х 1 и х 2 се наричат основнии променливата х 3 - не основно, безплатно.
Набор от променливи х 1 и х 2 представлява основа: б (х 1 , х 2). Ако х 3 = 0, тогава полученото конкретно решение (5, 11, 0) се нарича основно решение, съответстващо на основата б (х 1 , х 2).
Базовото решение е това, което съответства на нулеви стойности на свободните променливи.
Други променливи биха могли да бъдат взети като базови: ( х 1 , х 3) или ( х 2 , х 3).
Как да преминем от една основа б(х 1 , х 2) на друга основа б(х 1 , х 3)?
За това ви трябва променлива х 3 преобразуване в основен и х 2 - към неосновните, т.е. в уравненията е необходимо х 3 експрес чрез х 2 и заменете в 1-во:
б(х 1 , х 3), е: (-19/5; 0; 11/5).
Ако сега от осн б(х 1 , х 3) ще искаме да отидем до основата б(х 2 , х 3), тогава
Основно решение, съответстващо на основата б (х 2 , х 3): (0;19/4; 7/8).
От трите намерени основни решения, решението, съответстващо на основата б (х 1 , х 3) - отрицателен х 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.
Ако проблемът с LP има решение, тогава то се постига върху множеството от основни неотрицателни решения на системата от ограничения на каноничната форма.
Следователно идеята на симплексния метод е последователно преминаване от една основа към друга, което е по-добро от гледна точка на стойността на целевата функция.
Пример. Решете проблема с LP.
функция Е= х 2 - х 1 → min трябва да се минимизира при дадена система от ограничения:
-2х 1 + х 2 + х 3 = 2
х 1 + х 2 + х 5 = 5
х 1 - 2х 2 + х 4 = 12
х i ≥ 0, аз = 1, 5
Тези ограничения могат да се разглеждат като произтичащи от неравенствата и променливите х 3 , х 5 , х 4 - като допълнителни.
Нека запишем ограниченията, като изберем база от променливите б{ х 3 , х 4 , х 5 }:
Тази база съответства на основното неотрицателно решение
х 1 = 0, х 2 = 0, х 3 = 2, х 4 = 2, х 5 = 5 или (0, 0, 2, 2, 5).
Сега трябва да изразим Ечрез неосновни променливи, в нашия случай това вече е направено: Е= х 2 - х 1 .
Нека проверим дали функцията е достигнала Еминималната му стойност. За това основно решение Е= 0 - 0 = 0 - стойността на функцията е 0. Но тя може да бъде намалена, ако х 1 ще се увеличи, тъй като коефициентът във функцията при х 1 е отрицателна. Въпреки това, с увеличаване х 1 променливи стойности х 4 , х 5 намаление (виж второто и третото равенство на системата от ограничения). Променлива х 1 не може да се увеличи до повече от 2, в противен случай х 4 ще стане отрицателно (поради равенство 2) и не повече от 5, в противен случай х 5 - отрицателен. И така, от анализа на равенствата следва, че променливата х 1 може да се увеличи до 2 и стойността на функцията ще намалее.
Нека да преминем към новата база B 2, като въведем променливата х 1 към основа вместо това х 4 .
б 2 {х 1 , х 3 , х 5 }.
Нека изразим тези основни променливи чрез неосновни. За да направим това, първо изразяваме х 1 от второто уравнение и го заместете в останалото, включително функцията. 
Основно решение, съответстващо на основата б 3 {х 1 , х 2 , х 3 ), се записва (4, 1, 9, 0, 0) и функцията приема стойността Е= -3. Имайте предвид, че стойността Енамалена, т.е. подобрена в сравнение с предишната база.
Разглеждане на формата на целевата функция 
, имайте предвид, че за да подобрите, т.е. да намалите стойността Ене е възможно и само когато х 4 = 0, х 5 = 0 стойност Е= -3. възможно най-скоро х 4 , х 5 ще стане положителна, стойността Есамо ще нараства, тъй като коефициентите за х 4 , х 5 са положителни. Така че функцията Едостигна оптималната си стойност Е* = -3. Така че най-малката стойност Е, равно на -3, се постига при х 1 * = 4, х 2 * = 1, х 3 * = 9, х 4 * = 0, х 5 * = 0.
Този пример много ясно демонстрира идеята на метода: постепенно преминавайки от база към база, като винаги обръщаме внимание на стойностите на целевата функция, които трябва да бъдат подобрени, достигаме до основа, в която стойността на целта функцията не може да бъде подобрена; тя е оптимална. Имайте предвид, че има краен брой бази, така че броят на стъпките, които предприемаме, за да стигнем до желаната база, е краен.
Ако вече сте разбрали графичния метод за решаване на проблеми с линейно програмиране, време е да преминете към симплексен метод. За разлика от първия, той практически няма ограничения за проблема (произволен брой променливи, различни знации т.н.) и се модифицира в зависимост от вида на проблема (например М-метод или метод на изкуствена основа).
При решаване на задача по симплексния метод изчисленията обикновено се извършват (за компактност и яснота) в таблици (табуличен симплексен метод), а последната таблица с оптималното решение съдържа важно Допълнителна информация: решение на двоен проблем, баланси на ресурси, информация за оскъдни ресурси и т.н., което позволява икономически анализ на проблем с линейно програмиране (вижте пример 3 по-долу).
Примери за решения на задачи по симплексния метод са публикувани безплатно за ваше удобство - изучавайте, търсете подобни, решавайте. Ако имате нужда от помощ за попълване подобни задачи, отидете на раздел: персонализирано решение за линейно програмиране.
Решаване на задачи по симплексния метод: онлайн примери
Задача 1.Компанията произвежда рафтове за баня в два размера - A и B. Търговските агенти изчисляват, че на пазара могат да се продават до 550 рафта седмично. Всеки рафт тип А изисква 2 m2 материал, а всеки рафт тип B изисква 3 m2 материал. Фирмата може да получи до 1200 м2 материал на седмица. За изработването на един рафт от тип А са необходими 12 минути машинно време, а за изработването на един рафт от тип В - 30 минути; Машината може да се използва 160 часа седмично. Ако печалбата от продажбата на рафтове от тип А е 3 парични единици, а от рафтове от тип B - 4 парични единици. единици, тогава колко рафта от всеки тип трябва да се произвеждат на седмица?
Съставяне на математически модел и решаване на ЗЛП по симплексния метод (pdf, 33 Kb)
Задача 2.Решете задача от линейното програмиране, като използвате симплексния метод. 
Решение по симплекс метод с изкуствена основа (pdf, 45 Kb)
Задача 3.Фирмата произвежда 3 вида продукти: А1, А2, А3, използвайки два вида суровини. Известни са разходите за всеки вид суровина за единица продукция, запасите от суровини за плановия период, както и печалбата от единица продукция от всеки вид.
- Колко артикула от всеки тип трябва да бъдат произведени, за да се увеличи максимално печалбата?
- Определете състоянието на всеки вид суровина и нейната специфична стойност.
- Определете максималния интервал за промени в запасите от всеки вид суровина, в рамките на който структурата на оптималния план, т.е. Производствената номенклатура няма да се променя.
- Определете количеството произведени продукти и печалбата от производството при увеличаване на запасите от един от дефицитните видове суровини до максимално възможната (в рамките на дадения диапазон на продукцията) стойност.
- Определете интервалите на промяна на печалбата от единица продукция от всеки тип, при които полученият оптимален план няма да се промени.
Решение на задача от линейно програмиране с икономически анализ (pdf, 163 Kb)
Задача 4.Решете задача от линейното програмиране, като използвате симплексния метод: 
Решение по табличния симплекс метод с търсене на опорен план (pdf, 44 Kb)
Задача 5.Решете задача от линейното програмиране, като използвате симплексния метод: 
Решение чрез табличен симплекс метод (pdf, 47 Kb)
Задача 6.Решете задачата, като използвате симплексния метод, като вземете за първоначален референтен план плана, даден в условието: 
Решение по ръчен симплексен метод (pdf, 60 Kb)
Задача 7.Решете задачата, като използвате модифицирания симплекс метод.
За производството на два вида продукти А и Б се използват три вида технологично оборудване. За да произведе единица продукт А, оборудване от първи тип използва a1=4 часа, оборудване от втори тип a2=8 часа и оборудване от трети тип a3=9 часа. За да произведе единица продукт B, оборудването от първия тип използва b1=7 часа, оборудването от втория тип b2=3 часа и оборудването от третия тип b3=5 часа.
Оборудване от първи тип може да работи за производството на тези продукти за не повече от t1=49 часа, оборудване от втори тип за не повече от t2=51 часа, оборудване от трети тип за не повече от t3=45 часа.
Печалбата от продажбата на единица готов продукт А е ALPHA = 6 рубли, а продукт B е BETTA = 5 рубли.
Съставете производствен план за продуктите А и Б, като осигурите максимална печалба от продажбата им.
Решение, използващо модифициран симплексен метод (pdf, 67 Kb)
Задача 8.Намерете оптималното решение, като използвате двойния симплексен метод 
Решение, използващо двойния симплексен метод (pdf, 43 Kb)
Примери за решения на задачи по линейно програмиране
Методи за решаване на задачи по линейно програмиране
Референтни решения на задача от линейно програмиране
Нека проблем с линейно програмиране е даден в канонична нотация
при условия
С множеството решения ще обозначаваме системи (2) – (3). Да приемем, че , където е рангът на матрицата , а е броят на уравненията в системата (2).
От системата от колонни вектори на матрицата избираме някаква линейно независима подсистема от вектори. Съществува, защото. Тази система формира основа в. Нека означим с , . Да се обадим набор от основни ценности индекс , – базисна подматрица матрици Ще наричаме координатите на вектора основен , ако неосновни в противен случай.
Нека запишем система (2) във вида . Нека разделим термините от лявата страна на основни и неосновни, т.е
Нека дефинираме конкретно решение на тази система, както следва. Нека зададем всички неосновни променливи равни на нула в (4). Тогава системата (4) ще приеме формата
Да се обадим (5) основна подсистема система от уравнения (2). Нека означим с вектор, съставен от основните координати на вектора . Тогава система (2) може да бъде пренаписана във векторно-матрична форма
Тъй като подматрицата е основна, тя
неизродени. Следователно системата (6) има единствено решение. Полученото по този начин частно решение на система (2) ще се нарича референтен разтвор задача за пряко линейно програмиране, съответстваща на базиса. (Понякога референтният разтвор също се нарича основен ). Както виждаме, основата съответства на едно решение за поддръжка. Очевидно броят на решенията за поддръжка е ограничен.
За тази основа ние също определяме референтното решение на проблема с двойното линейно програмиране. Припомнете си, че задачата, двойна на каноничната, има формата
при условия
Нека запишем системата (8) във формата
Припомнете си, че множеството от решения на система (8) се означава с .
Нека дефинираме вектора на дуалните променливи от условието за изпълнение на основните ограничения в системата (9) като равенства. Получаваме следната система от линейни уравнения:
Нека означим с вектор, съставен от ba-
zis координати на вектора. Тогава системата (10) може да бъде пренаписана във векторно-матрична форма
Система (11) също има уникално решение.
Да му се обадим поддържащ (основен )решение двойна задача за линейно програмиране, съответстваща на базиса. Това референтно решение също е еднозначно определено.
И така, всяка основа съответства на два вектора - две опорни решения и съответно задачи за директно и двойно линейно програмиране.
Нека да дефинираме допълнително следните типове бази и решения за поддръжка. Ако всички координати на опорното решение са неотрицателни, тогава се нарича основата, на която съответства това опорно решение приемливо референтен план задача за директно линейно програмиране и се извиква референтното решение, съответстващо на същата база псевдоплан двоен проблем. Всъщност, за да бъде базисът допустим, е достатъчна неотрицателността на базисните координати. Обърнете внимание, че референтният план е възможен вектор на задачата за предно линейно програмиране ().
Ако референтното решение удовлетворява всички ограничения (9) на двойствения проблем, тогава основата, на която съответства това еталонно решение, се нарича двойно валиден . В този случай векторът се нарича референтен план задача с двойно линейно програмиране и референтното решение, съответстващо на същата основа
нарича се псевдоплан пряка задача.
За двойна допустимост на базис е достатъчно да се удовлетворяват само небазисни неравенства. Обърнете внимание, че референтният план е възможен вектор на задачата за двойно линейно програмиране ().
Разликите между лявата и дясната част на неравенства (9) означаваме с , . Тогава двойствената допустимост на база може да се установи чрез проверка на неотрицателността на всички . Имайте предвид, че както следва директно от дефиницията, всички базисни остатъци са равни на нула ().
Пример за решаване на директна и двойна задача по симплексния метод
Следователно е достатъчно да се уверим, че неравенствата са валидни за всички.
Теорема 1.ПозволявамИ– референтни решения на задачата за линейно програмиране, съответстващи на определен базис, тогава равенството е в сила .
Доказателство . От дефинициите на опорните решения е лесно да се получат равенствата
оттук следва валидността на теоремата.
Теорема 2. (Критерий за оптималност за решения за поддръжка) Ако основае едновременно допустимо и двойно допустимо, тогава съответните решения за поддръжкаИса решения, съответно, на проблемите с директното и двойното линейно програмиране.
Доказателство. Валидността на това твърдение следва от теорията на дуалността в линейното програмиране и теорема 1.
Теорема 3.Допустимо решение на задача (1) – (3) е опорен план на задачата тогава и само ако е връх на изпъкнало многостенно множество.
Доказателство. Позволявам – референтен план на проблема (1) – (3). Нека докажем това – горна част на комплекта . По дефиниция референтен план – допустимо референтно решение, съответстващо на някаква основа, т.е – решаване на система от линейни уравнения по отношение на променливи
Лесно се вижда, че тази система има уникално решение. Това означава, че опорната равнина на лицето, съдържаща точката , има размерност 0. Следователно, – горна част на комплекта .
Обратно. Позволявам – горната част на комплекта. Нека докажем това – референтен план на проблема (1) – (3). Тъй като е връх, той е лице на множеството, чиято размерност е нула. Следователно векторът има най-малко нула компоненти, множеството от чиито числа означаваме . По този начин, – единственото решение на системата
Където . Следователно остава да се докаже, че системата от вектори е линейно независима. Да приемем обратното. След това има числа, които не всички са равни на нула, така че . Ето защо
Това означава, че система (12) има решение, различно от , което противоречи на уникалността на неговото решение. Така това е основата и векторът – съответния референтен план на проблема (1) – (3). Това се изискваше.
Забележете, че едно допустимо решение на задача (7), (8) (двойствената задача (1) – (3)) също е опорен план тогава и само ако е върхът на допустимото множество.
Дата на публикуване: 2015-01-10; Прочетено: 695 | Нарушаване на авторските права на страницата
Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)…
За категоричност приемаме, че решаваната задача е намирането на минимума.
1. Намалете проблема с линейното програмиране до канонична форма.
След като въведем допълнителни променливи, записваме системата от уравнения и линейната функция във форма, наречена разширена система:
Предполагаме, че всички допълнителни променливи имат същия знак като свободните членове; иначе използваме т.нар М– метод, който ще бъде разгледан по-долу.
2. Дефинирайте основни и свободни променливи.
3. Въвеждаме оригиналната разширена система в първата симплексна таблица. Извиква се последният ред на таблицата, който дава уравнението за линейната целева функция Оценяване. Показва коефициентите на целевата функция. В лявата колона на таблицата записваме основните променливи (база), в следващите колони записваме коефициентите за свободните променливи. Предпоследната колона съдържа безплатни членове на разширената система. Последната колона е подготвена за оценъчните взаимовръзки, необходими за определяне на основната променлива въз основа на връзката (6.29).
4. Определете възможността за решаване на проблема чрез стойности съгласно теореми 6.7,…, 6.9.
5. Изберете разрешаващия (референтен) елемент.
Решаване на производствена задача по табличния симплекс метод
Ако критерият за оптималност не е изпълнен (условията на теорема 6.7 или 6.8 не са изпълнени), тогава най-големият абсолютен отрицателен коефициент в последния ред определя разрешаващата (референтна) колона 
.
Ние съставяме прогнозните съотношения на всеки ред съгласно следните правила:
1 0) ако всички и имат различни знаци;
2 0) ако всички и ;
3 0) ако ;
4 0) 0 ако и ;
5 0), ако и имат еднакви знаци.
Да дефинираме. Ако няма краен минимум, тогава проблемът няма краен оптимум (). Ако минимумът е краен, изберете линията р, на която се постига (която и да е, ако има няколко), и я наричаме разрешаваща (референтна) линия. В пресечната точка на разрешаващия ред и колоната има разрешаващ (референтен) елемент.
6 0) Отидете на следващата таблица според правилата:
а) в лявата колона пишем нова основа: вместо основната променлива - променлива, т.е. Нека разменим променливите и ;
б) поставете 1 на мястото на носещия елемент;
в) оставете елементите на оригиналната таблица на останалите места от референтния ред в новата таблица;
г) на останалите места в референтната колона поставете съответните елементи от оригиналната таблица, умножени по –1;
д) за останалите свободни места на елементите , , в новата таблица запишете числата , , , които се намират, както следва:
За да се опростят изчисленията с помощта на тези формули, те могат да бъдат формулирани като "Правила на правоъгълника"(Фиг. 6.8): елементите по диагоналите на правоъгълник с върхове (или , , , , или , , , ) се умножават (произведението, което не съдържа опорния елемент, се взема със знак минус) и получените произведения се добавено;
е) разделя всички получени елементи от новата таблица на референтния елемент.
7 0) Използвайки стойността на елемента, определете дали е намерена оптималната стойност на целевата функция. Ако отговорът е отрицателен, продължете решението (върнете се към точка 6).
Ориз. 6.8. Правило на правоъгълника за определяне на числата:
a − , b − , c − .
Разглежда се алгоритъм за преобразуване на симплексни таблици за неизродени допустими базисни решения, т.е. ситуацията, описана от теорема 6.9, беше изпълнена. Ако първоначалният проблем с линейното програмиране е изроден, тогава в хода на решаването му по симплексния метод могат да се появят изродени основни решения. В този случай са възможни празни стъпки на симплексния метод, т.е. итерации, в които f(х)не се променя. Възможен е и зацикляне, т.е. безкрайна поредица от празни стъпки. За предотвратяването му са разработени специални алгоритми - антициклини. Въпреки това, в преобладаващото мнозинство от случаите, празните стъпки се заменят със стъпки с намаляване на целевата функция и процесът на решение завършва в резултат на краен брой итерации.
Пример 6.8.Решете задачата, дадена в пример 6.7, като използвате симплексния метод.
⇐ Предишен45678910111213Следващ ⇒
Дата на публикуване: 2015-01-23; Прочетено: 174 | Нарушаване на авторските права на страницата
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)…
Начало >> Пример №3. Симплексен метод. Намиране на най-голямата стойност на функция (изкуствена основа)
Симплексен метод
| — | х 1 | + | х 2 | ≥ | 1 | |
| х 1 | + | 3 | х 2 | ≤ | 15 | |
| — | 2 | х 1 | + | х 2 | ≤ | 4 |
| Една променлива се нарича основна за дадено уравнение, ако е включена в това уравнение с коефициент единица и не е включена в останалите уравнения (при условие, че има положително число от дясната страна на уравнението). Ако всяко уравнение има базисна променлива, тогава се казва, че системата има основа. Идеята на симплексния метод е да се премине от една база към друга, като се получи функционална стойност, която е поне не по-малка от съществуващата (всяка база съответства на една единствена функционална стойност). Как се извършва преходът от една основа към друга? |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| х 1 | х 2 | S 1 | S 2 | S 3 | R 1 | Св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| х 1 | х 2 | S 1 | S 2 | S 3 | Св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | Е - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Сред избраните коефициенти на реда няма положителни коефициенти. Следователно намерени най-висока стойностфункции Ф.
Отговор:
x 1 = 3 x 2 = 4
F max = 13
Отидете до решението на вашия проблем
© 2010-2018, за всякакви въпроси, моля пишете на [имейл защитен]
Задачата
За продажба на три групи стоки търговско предприятиеразполага с три вида ограничени материални и парични ресурси в размер на b 1 = 240, b 2 = 200, b 3 = 160 единици. В същото време за продажба на 1 група стоки за 1 хил. Рубли. стокооборот, ресурсът от първи вид се изразходва в размер на a 11 = 2 единици, ресурсът от втори вид в размер на a 21 = 4 единици, ресурсът от трети вид в размер на a 31 = 4 единици. За продажба на 2 и 3 групи стоки за 1 хил. Рубли. оборотът се изразходва според ресурса от първия вид в размер на a 12 = 3, a 13 = 6 единици, ресурсът от втория вид в размер на a 22 = 2, a 23 = 4 единици, ресурсът на третият тип в размер на a 32 = 6, a 33 = 8 единици . Печалба от продажба на три групи стоки на 1 хил.
Симплексен метод за решаване на ЗЛП
търкайте. оборотът е съответно c 1 = 4, c 2 = 5, c 3 = 4 (хиляда рубли). Определете планирания обем и структура на търговския оборот, така че печалбата на търговското предприятие да бъде максимална.
Към прекия проблем с планирането на оборота, решен по симплекс метод, композирайте двоен проблемлинейно програмиране.
Инсталирай спрегнати двойки променливидиректни и двойни проблеми.
Според спрегнати двойки променливи, от решението на директния проблем получаваме решение на двойния проблем, в който се произвежда оценка на ресурсите, изразходвани за продажба на стоки.
Решаване на задачата чрез симплексния метод
Нека x 1, x 2, x 3 е броят на продадените стоки в хиляди рубли, 1, 2, 3 - нейните групи, съответно. Тогава математическият модел на задачата има формата:
F = 4 x 1 + 5 x 2 + 4 x 3 -> макс
Решаваме симплексния метод.
Въвеждаме допълнителни променливи x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, за да преобразуваме неравенствата в равенства.
Да вземем x 4 = 240 като основа; х 5 = 200; х 6 = 160.
Въвеждаме данните в симплексна таблица
Симплексна таблица №1
Целева функция:
0 240 + 0 200 + 0 160 = 0
Изчисляваме прогнозите по формулата:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Тъй като има отрицателни оценки, планът не е оптимален. Най-нисък резултат:
Въвеждаме променливата x 2 в основата.
Ние дефинираме променлива, излизаща от основата. За да направим това, намираме най-малкото неотрицателно съотношение за колоната x2.
= 26.667
Най-малкото неотрицателно: Q 3 = 26,667. Извличаме променливата x 6 от основата
Разделете третия ред на 6.
От първия ред извадете третия ред, умножен по 3
От втория ред извадете третия ред, умножен по 2
Изчисляваме:
Получаваме нова таблица:
Симплексна таблица № 2
Целева функция:
0 160 + 0 440/3 + 5 80/3 = 400/3
Изчисляваме прогнозите по формулата:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Тъй като има отрицателна оценка Δ 1 = - 2/3, планът не е оптимален.
Въвеждаме променливата x 1 в основата.
Ние дефинираме променлива, излизаща от основата. За да направим това, намираме най-малкото неотрицателно съотношение за колоната x 1.
Най-малкото неотрицателно: Q 3 = 40. Извличаме променливата x 2 от основата
Разделете 3-тия ред на 2/3.
От втория ред извадете третия ред, умножен по 8/3
Изчисляваме:
Получаваме нова таблица:
Симплексна таблица №3
Целева функция:
0 160 + 0 40 + 4 40 = 160
Изчисляваме прогнозите по формулата:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Тъй като няма отрицателни оценки, планът е оптимален.
Решението на проблема:
Отговор
х 1 = 40; x2 = 0; х 3 = 0; х 4 = 160; х 5 = 40; x6 = 0; F max = 160
Тоест, необходимо е да продадете първия вид стоки в размер на 40 хиляди.
търкайте. Продукти от тип 2 и 3 не е необходимо да се продават. В този случай максималната печалба ще бъде F max = 160 хиляди рубли.
Решение на двойствения проблем
Двойният проблем има формата:
Z = 240 y 1 + 200 y 2 + 160 y 3 -> min
Въвеждаме допълнителни променливи y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, за да преобразуваме неравенствата в равенства.
Конюгираните двойки променливи на директните и двойствените задачи имат формата:
От последната симплексна таблица № 3 на директния проблем намираме решението на двойния проблем:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Отговор
y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;
Симплексният метод е изчислителна процедура, основана на принципа на последователно подобряване на решенията при преминаване от една базова точка (базово решение) към друга. В този случай стойността на целевата функция се подобрява.
Базовото решение е едно от допустимите решения, разположени във върховете на областта на допустимите стойности. Като проверяват връх след връх на симплекса за оптималност, те стигат до желания оптимум. На този принцип се основава симплексният метод.
Симплексът е изпъкнал многоъгълник в n-мерно пространство с n+1 върха, които не лежат в една и съща хиперравнина (хиперравнината разделя пространството на две полупространства).
Например линията на бюджетните ограничения разделя стоките на налични и неналични.
Доказано е, че ако съществува оптимално решение, то със сигурност ще бъде намерено след краен брой итерации (стъпки), освен в случаите на „циклене“.
Алгоритъмът на симплексния метод се състои от няколко етапа.
Първи етап. Изгражда се първоначален оптимизационен модел. След това оригиналната матрица от условия се трансформира в редуцирана канонична форма, която сред всички други канонични форми се отличава с факта, че:
а) десните части на условията (свободни членове bi) са неотрицателни величини;
б) самите условия са равенства;
в) матрицата на условията съдържа пълна подматрица на единица.
Ако свободните членове са отрицателни, тогава и двете страни на неравенството се умножават по – 1 и знакът на неравенството се обръща. За да се трансформират неравенствата в равенства, се въвеждат допълнителни променливи, които обикновено показват количеството на недостатъчно използвани ресурси. Това е техният икономически смисъл.
И накрая, ако след добавяне на допълнителни променливи матрицата на условията не съдържа пълна подматрица на идентичност, тогава се въвеждат изкуствени променливи, които нямат никакъв икономически смисъл. Те се въвеждат единствено, за да се получи подматрицата на идентичността и да започне процесът на решаване на проблема с помощта на симплексния метод.
При оптимално решение на проблема всички изкуствени променливи (AI) трябва да са равни на нула. За да направите това, в целевата функция на проблема се въвеждат изкуствени променливи с големи отрицателни коефициенти (-M), когато проблемът се решава при max, и с големи положителни коефициенти (+M), когато проблемът се решава при min. В този случай дори незначителна ненулева стойност на изкуствената променлива рязко ще намали (увеличи) стойността на целевата функция. Обикновено M трябва да бъде 1000 пъти по-голямо от стойностите на коефициентите за основните променливи.
Втора фаза. Изгражда се начална симплексна таблица и се намира някакво първоначално основно решение. Наборът от променливи, които формират подматрицата на идентичността, се приема като първоначално базово решение. Стойностите на тези променливи са равни на свободните условия. Всички други извънбазисни променливи са нула.
Трети етап. Проверката на основното решение за оптималност се извършва с помощта на специални оценки на коефициентите на целевата функция. Ако всички оценки на коефициентите на целевата функция са отрицателни или равни на нула, тогава съществуващото основно решение е оптимално. Ако поне една оценка на коефициента на целевата функция е по-голяма от нула, тогава съществуващото основно решение не е оптимално и трябва да бъде подобрено.
Четвърти етап. Преход към ново основно решение. Очевидно оптималният план трябва да включва променлива, която увеличава в най-голяма степен целевата функция. При решаване на задачи за максимална печалба оптималният план включва продукти, чието производство е най-рентабилно. Това се определя от максималната положителна стойност на оценката на коефициента на целевата функция.
Колоната на симплексната таблица с това число при тази итерация се нарича обща колона.
За да намерите общия ред, всички безплатни членове (ресурси) се разделят на съответните елементи на общата колона (разход на ресурс за единица продукт). От получените резултати се избира най-малкият. Съответстващата линия на дадена итерация се нарича обща линия. Той съответства на ресурса, който ограничава производството при дадена итерация.
Елемент от симплексна таблица, разположен в пресечната точка на обща колона и ред, се нарича общ елемент.
Тогава всички елементи на общия низ (включително свободния член) се разделят на общия елемент. В резултат на тази операция генералният елемент става равен на единица. След това е необходимо всички останали елементи на общата колона да станат равни на нула, т.е. общата колона трябва да стане единична. Всички редове (с изключение на общия) се преобразуват, както следва. Получените елементи от новия ред се умножават по съответния елемент от общата колона и полученият продукт се изважда от елементите на стария ред.
Получаваме стойностите на новите основни променливи в съответните клетки на колоната със свободни условия.
Пети етап. Полученото основно решение се проверява за оптималност (виж третия етап). Ако е оптимално, изчисленията спират. В противен случай е необходимо да се намери ново основно решение (четвърти етап) и т.н.
Симплексен метод
Пример за решаване на оптимизационни проблеми на линейното програмиране с помощта на симплексния метод
Нека е необходимо да се намери оптималният план за производството на два вида продукти (x1 и x2).
Първоначални данни:
Нека изградим модел за оптимизация
– ограничение на ресурса А;
– ограничение на ресурсите B.
Нека сведем проблема до намалената канонична форма. За да направите това, достатъчно е да въведете допълнителни променливи X3 и X4. В резултат на това неравенствата се трансформират в строги равенства.
Нека изградим началната симплексна таблица и да намерим първоначалното основно решение. Те ще бъдат допълнителни променливи, тъй като съответстват на единична подматрица.
1-ва итерация. Намерете общата колона и общия ред:
Общият елемент е 5.
2-ро повторение. Намереното принципно решение не е оптимално, т.к рейтинговата линия (Fj-Cj) съдържа един положителен елемент. Намерете общата колона и общия ред:
max(0,0,3,-1,4,0) = 0,2
Намереното решение е оптимално, тъй като всички специални оценки на целевата функция Fj – Cj са равни на нула или отрицателни. F(x)=29 x1=2; х2=5.
Ето ръчно (не аплетно) решение на две задачи, използвайки симплексния метод (подобен на аплетното решение) с подробни обяснения, за да разберете алгоритъма за решаване на проблеми, използвайки симплексния метод. Първата задача съдържа знаци за неравенство само „≤“ (задача с начална основа), втората може да съдържа знаци „≥“, „≤“ или „=“ (задача с изкуствена основа), те се решават по различен начин.
Симплексен метод, решаване на задача с начален базис
1)Симплексен методза задача с начална база (всички признаци на неравенство ограничения " ≤ ").
Нека напишем проблема канониченформа, т.е. пренаписваме ограниченията на неравенството под формата на равенства, добавяйки балансапроменливи:
Тази система е система с базис (базис s 1, s 2, s 3, всеки от тях е включен само в едно уравнение на системата с коефициент 1), x 1 и x 2 са свободни променливи. Задачите, които се решават чрез симплексния метод, трябва да притежават следните две свойства: - системата от ограничения трябва да бъде система от уравнения с базис; -свободните членове на всички уравнения в системата трябва да са неотрицателни.
Получената система е система с база и нейните свободни условия са неотрицателни, така че можем да приложим симплексен метод. Нека създадем първата симплексна таблица (итерация 0), за да решим проблема симплексен метод, т.е. таблица с коефициенти на целевата функция и система от уравнения за съответните променливи. Тук „BP“ означава колоната от основни променливи, „Разтвор“ означава колоната от дясната страна на уравненията на системата. Решението не е оптимално, т.к има отрицателни коефициенти в z-реда.
симплекс метод итерация 0
|
Поведение |
|||||||
За да подобрим решението, нека преминем към следващата итерация симплексен метод, получаваме следната симплексна таблица. За да направите това, трябва да изберете активиране на колона, т.е. променлива, която ще бъде включена в основата при следващата итерация на симплексния метод. Избира се по най-големия абсолютен отрицателен коефициент в z-реда (в максималния проблем) - в началната итерация на симплексния метод това е колона x 2 (коефициент -6).
След това изберете активиране на низ, т.е. променлива, която ще напусне основата при следващата итерация на симплексния метод. Избира се чрез най-малкото съотношение на колоната „Решение“ към съответните положителни елементи на колоната за разделяне (колона „Съотношение“) - в първоначалната итерация това е ред s 3 (коефициент 20).
Разрешителен елементе в пресечната точка на разделящата колона и разрешаващия ред, нейната клетка е маркирана в цвят, тя е равна на 1. Следователно, при следващата итерация на симплексния метод, променливата x 2 ще замени s 1 в основата. Имайте предвид, че връзката не се търси в z-низ; там се поставя тире „-“. Ако има еднакви минимални отношения, тогава се избира всяка от тях. Ако всички коефициенти в разделителната колона са по-малки или равни на 0, тогава решението на проблема е безкрайно.
Нека попълним следната таблица „Итерация 1“. Ще го получим от таблицата „Итерация 0“. Целта на по-нататъшните трансформации е колоната с разделителна способност x2 да се превърне в колона с единица (с единица вместо разделителния елемент и нули вместо останалите елементи).
1) Изчислете ред x 2 от таблицата „Итерация 1“. Първо, разделяме всички членове на разрешаващия ред s 3 на таблицата „Итерация 0“ на разделящия елемент (той е равен на 1 в в такъв случай) от тази таблица, получаваме ред x 2 в таблицата „Итерации 1“. защото разрешаващият елемент в този случай е равен на 1, тогава ред s 3 от таблицата „Итерация 0“ ще съвпадне с ред x 2 от таблицата „Итерация 1“. Ред x 2 от таблицата от Итерация 1 получихме 0 1 0 0 1 20, останалите редове от таблицата от Итерация 1 ще бъдат получени от този ред и редовете от таблицата от Итерация 0, както следва:
2) Изчисляване на z-реда на таблицата „Итерация 1“. На мястото на -6 в първия ред (z-ред) в колоната x2 на таблицата Итерация 0 трябва да има 0 в първия ред на таблицата Итерация 1. За да направите това, умножете всички елементи на реда x 2 на таблицата "Итерация 1" 0 1 0 0 1 20 по 6, получаваме 0 6 0 0 6 120 и добавете този ред с първия ред (z - ред) на таблицата "Итерация 0" -4 -6 0 0 0 0, получаваме -4 0 0 0 6 120. В колоната x 2 се появява нула 0, целта е постигната. Елементите на колоната за разделителна способност x 2 са маркирани в червено.
3) Изчисляване на ред s 1 от таблицата „Итерация 1“. На мястото на 1 в s 1 ред на таблицата „Итерация 0“ трябва да има 0 в таблицата „Итерация 1“. За да направите това, умножете всички елементи на ред x 2 от таблицата "Итерация 1" 0 1 0 0 1 20 по -1, получете 0 -1 0 0 -1 -20 и добавете този ред с s 1 - ред на таблица "Iteration 0" 2 1 1 0 0 64, получаваме реда 2 0 1 0 -1 44. В колоната x 2 получаваме необходимата 0.
4) Изчислете ред s 2 от таблицата „Итерация 1“. На място 3 в s 2 ред на таблицата "Итерация 0" трябва да има 0 в таблицата "Итерация 1". За да направите това, умножете всички елементи на ред x 2 от таблицата "Итерация 1" 0 1 0 0 1 20 по -3, получаваме 0 -3 0 0 -3 -60 и добавете този ред с s 1 - ред от таблицата "Итерация 0" 1 3 0 1 0 72, получаваме реда 1 0 0 1 -3 12. В колоната x 2 се получава необходимата 0. Колоната x 2 в таблицата "Итерация 1" е станала единица, тя съдържа една 1, а останалите 0.
Редовете на таблицата „Итерация 1” се получават по следното правило:
Нов ред = Стар ред – (Коефициент на разделителна способност на стария ред)*(Нов ред на разделителна способност).
Например за z-низ имаме:
Стар z-низ (-4 -6 0 0 0 0) -(-6)*Нов разрешаващ низ -(0 -6 0 0 -6 -120) =Нов z-низ (-4 0 0 0 6 120).
За следващите таблици преизчисляването на елементите на таблицата се извършва по подобен начин, затова го пропускаме.
симплекс метод итерация 1
|
Поведение |
|||||||
Резолвираща колона x 1, разрешаващ ред s 2, s 2 излиза от основата, x 1 влиза в основата. По абсолютно същия начин получаваме останалите симплексни таблици, докато получим таблица с всички положителни коефициенти в z-реда. Това е знак за оптимална маса.
симплекс метод итерация 2
|
Поведение |
|||||||
Резолвираща колона s 3, разрешаваща ред s 1, s 1 напуска основата, s 3 влиза в основата.
симплекс метод итерация 3
|
Поведение |
|||||||
В z-реда всички коефициенти са неотрицателни, следователно се получава оптималното решение x 1 = 24, x 2 = 16, z max = 192.
За направата на три вида ризи се използват конци, копчета и плат. Запасите от конци, копчета и тъкани, нормите на тяхното потребление за шиене на една риза са посочени в таблицата. Намерете максималната печалба и оптималния план за производство на продукта, който я осигурява (намерете).
| риза 1 | риза 2 | риза 3 | Резерви | нишки (m.) | 1 | 9 | 3 | 96 | копчета (бр.) | 20 | 10 | 30 | 640 | текстил ( | 1 | 2 | 2 | 44 | Печалба (р.) | 2 | 5 | 4 |
Решението на проблема
Изграждане на модел
Чрез и броя на ризите от 1-ви, 2-ри и 3-ти тип, предназначени за освобождаване.
Тогава ограниченията на ресурсите ще изглеждат така:
Освен това според смисъла на задачата
Целева функция, изразяваща получената печалба:
Получаваме следната задача за линейно програмиране:
Намаляване на проблем с линейно програмиране до канонична форма
Нека сведем проблема до каноничен вид. Нека въведем допълнителни променливи. Въвеждаме всички допълнителни променливи в целевата функция с коефициент, равен на нула. Добавяме допълнителни променливи към левите страни на ограниченията, които нямат предпочитана форма, и получаваме равенства.
Решаване на задачата чрез симплексния метод
Попълнете симплексната таблица:
Тъй като решаваме проблема до максимум, наличието на отрицателни числа в индексния ред при решаване на проблема до максимум показва, че не сме получили оптималното решение и че е необходимо да преминем от таблицата на 0-та итерация към следващия.
Продължаваме към следващата итерация, както следва:
водещата колона съответства
Ключовият ред се определя от минималното съотношение на свободните термини и членовете на водещата колона (симплексни отношения):
В пресечната точка на ключовата колона и ключовия ред намираме разрешаващия елемент, т.е. 9.
Сега пристъпваме към компилирането на 1-ва итерация: Вместо единичен вектор въвеждаме вектора.
В новата таблица на мястото на разрешаващия елемент записваме 1, всички останали елементи от ключовата колона са нули. Ключовите низови елементи са разделени на активиращия елемент. Всички останали елементи на таблицата се изчисляват по правилото на правоъгълника.
Ключовата колона за 1-ва итерация съответства на
Разрешаващият елемент е числото 4/3. Извличаме вектора от базиса и вместо него въвеждаме вектора. Получаваме таблицата от 2-ра итерация.
Ключовата колона за 2-ро повторение съответства на
Намираме ключовия ред, за това дефинираме:
Разрешаващият елемент е числото 10/3. Извличаме вектора от базиса и вместо него въвеждаме вектора. Получаваме таблицата на 3-та итерация.
| № | BP | в Б | А о | х 1 | х 2 | х 3 | х 4 | х 5 | х 6 | Симплекс | 2 | 5 | 4 | 0 | 0 | 0 | връзка | 0 | х 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | х 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | х 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | х 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | х 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | х 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | х 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | х 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | х 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | х 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | х 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | х 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
В индексния ред всички термини са неотрицателни, така че се получава следното решение на проблема с линейното програмиране (изписваме го от колоната със свободни термини):
Необходимо е да се ушият 24 ризи от 1-ви вид, 7 ризи от 2-ри вид и 3 ризи от 3-ти вид. В този случай получената печалба ще бъде максимална и ще възлиза на 95 рубли.
Кратка теория
Решението на проблема
Изграждане на модел
Нека означим оборота съответно на 1-ви, 2-ри и трети вид стоки.
Тогава целевата функция, изразяваща получената печалба:
Ограничения за материални и парични ресурси:
Освен това според смисъла на задачата
Получаваме следната задача за линейно програмиране:
Попълваме симплексната таблица на 0-та итерация.
| BP | Симплекс връзка |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Тъй като решаваме проблема до максимум, наличието на отрицателни числа в индексния ред при решаване на проблема до максимум показва, че не сме получили оптималното решение и че е необходимо да преминем от таблицата на 0-та итерация към следващия.
Продължаваме към следващата итерация, както следва:
Водещата колона съответства на .
Ключовият ред се определя от минималното съотношение на свободните термини и членовете на водещата колона (симплексни отношения):
В пресечната точка на ключовата колона и ключовия ред намираме разрешаващия елемент, т.е. 7.
Сега започваме да компилираме първата итерация. Вместо единичен вектор въвеждаме вектора .
В новата таблица на мястото на разрешаващия елемент записваме 1, всички останали елементи от ключовата колона са нули. Ключовите низови елементи са разделени на активиращия елемент. Всички останали елементи на таблицата се изчисляват по правилото на правоъгълника.
Получаваме таблицата на 1-ва итерация:
| BP | Симплекс връзка |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Ключовата колона за 1-ва итерация съответства на .
Намираме ключовия ред, за това дефинираме:
В пресечната точка на ключовата колона и ключовия ред намираме разрешаващия елемент, т.е. 31/7.
Векторът се извлича от основата и се въвежда векторът.
Получаваме таблицата на 2-ра итерация:
| BP | Симплекс връзка |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
В индексния ред всички термини са неотрицателни, така че се получава следното решение на проблема с линейното програмиране (изписваме го от колоната със свободни термини):
По този начин е необходимо да се продадат 7,1 хиляди рубли. стоки от 1-ви вид и 45,2 хиляди рубли. стоки от 3-ти вид. Не е изгодно да се продава продукт от 2-ри тип. В този случай печалбата ще бъде максимална и ще възлиза на 237,4 хиляди рубли. При изпълнение на оптималния план оставащият ресурс от 3-ти тип ще бъде 701 единици.
Ако не се нуждаете от помощ сега, но може да се нуждаете от нея в бъдеще, тогава, за да не загубите връзка,