Този метод е метод за целенасочено изброяване на справочни решения на проблема линейно програмиране. Тя позволява в краен брой стъпки или да се намери оптимално решение, или да се установи, че няма оптимално решение.
Основното съдържание на симплексния метод е следното:- Посочете метод за намиране на оптималното еталонно решение
- Посочете метода на преход от едно референтно решение към друго, при което стойността на целевата функция ще бъде по-близо до оптималната, т.е. посочете начин за подобряване на референтния разтвор
- Задайте критерии, които ви позволяват незабавно да спрете търсенето на решения за поддръжка при оптималното решение или да направите заключение за липсата на оптимално решение.
Алгоритъм на симплексния метод за решаване на задачи от линейното програмиране
За да разрешите проблем с помощта на симплексния метод, трябва да направите следното:- Доведете задачата до канонична форма
- Намерете първоначалното решение за поддръжка с „основа на единица“ (ако няма решение за поддръжка, тогава проблемът няма решение поради несъвместимостта на системата от ограничения)
- Изчислете оценки на векторни разложения на базата на референтното решение и попълнете таблицата на симплексния метод
- Ако критерият за уникалност на оптималното решение е изпълнен, тогава решението на задачата приключва
- Ако условието за съществуване на набор от оптимални решения е изпълнено, тогава всички оптимални решения се намират чрез просто изброяване
Пример за решаване на задача по симплексния метод
Пример 26.1Решете задачата, като използвате симплексния метод:
Решение:
Привеждаме проблема в каноничен вид.
За да направим това, въвеждаме допълнителна променлива x 6 с коефициент +1 от лявата страна на първото ограничение на неравенството. Променливата x 6 е включена в целевата функция с коефициент нула (т.е. не е включена).
Получаваме:
Ние намираме първоначалното решение за поддръжка. За да направим това, ние приравняваме свободните (неразрешени) променливи на нула x1 = x2 = x3 = 0.
Получаваме референтен разтвор X1 = (0,0,0,24,30,6) с единична основа B1 = (A4, A5, A6).
Ние изчисляваме оценки на векторни декомпозицииусловия на базата на референтния разтвор по формулата:
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., c m) - вектор на коефициентите на целевата функция за основните променливи
- X k = (x 1k , x 2k , ... , x mk) - вектор на разлагане на съответния вектор A k според базата на еталонното решение
- C k е коефициентът на целевата функция за променливата x k.
Оценките на векторите, включени в основата, винаги са равни на нула. Референтното решение, коефициентите на разширения и оценките на разширенията на векторите на условията на базата на референтното решение са записани в симплексна таблица:
В горната част на таблицата, за по-лесно изчисляване на оценките, са написани коефициентите на целевата функция. Първата колона "B" съдържа векторите, включени в основата на еталонното решение. Редът, в който са записани тези вектори, съответства на броя на разрешените неизвестни в уравненията на ограниченията. Във втората колона на таблицата "C b" в същия ред са записани коефициентите на целевата функция за основните променливи. При правилното подреждане на коефициентите на целевата функция в колоната "C b" оценките на единичните вектори, включени в основата, винаги са равни на нула.
В последния ред на таблицата с оценки на Δ k в колоната "A 0" са записани стойностите на целевата функция върху референтното решение Z (X 1).
Първоначалното опорно решение не е оптимално, тъй като в максималния проблем оценките Δ 1 = -2, Δ 3 = -9 за векторите A 1 и A 3 са отрицателни.
Според теоремата за подобряване на опорното решение, ако в максимален проблем поне един вектор има отрицателна оценка, тогава можете да намерите ново опорно решение, при което стойността на целевата функция ще бъде по-голяма.
Нека определим кой от двата вектора ще доведе до по-голямо увеличение на целевата функция.
Приращението на целевата функция се намира по формулата: .
Изчисляваме стойностите на параметъра θ 01 за първата и третата колона по формулата:
Получаваме θ 01 = 6 за l = 1, θ 03 = 3 за l = 1 (Таблица 26.1).
Намираме увеличението на целевата функция, когато въвеждаме в основата първия вектор ΔZ 1 = - 6*(- 2) = 12 и третия вектор ΔZ 3 = - 3*(- 9) = 27.
Следователно, за по-бърз подход към оптималното решение е необходимо да се въведе вектор A3 в основата на референтното решение вместо първия вектор на основата A6, тъй като минимумът на параметъра θ 03 се постига в първия ред ( l = 1).
Извършваме трансформацията на Йордан с елемента X13 = 2, получаваме второто референтно решение X2 = (0,0,3,21,42,0) с основа B2 = (A3, A4, A5). (Таблица 26.2)
Това решение не е оптимално, тъй като вектор A2 има отрицателна оценка Δ2 = - 6. За да се подобри решението, е необходимо да се въведе вектор A2 в основата на референтното решение.
Определяме номера на вектора, получен от основата. За да направим това, изчисляваме параметъра θ 02 за втората колона, той е равен на 7 за l = 2. Следователно извличаме втория базисен вектор A4 от основата. Извършваме трансформацията на Йордан с елемента x 22 = 3, получаваме третото референтно решение X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Таблица 26.3).
Това решение е единственото оптимално, тъй като за всички вектори, които не са включени в основата, оценките са положителни
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Отговор: max Z(X) = 201 при X = (0,7,10,0,63).
Метод на линейно програмиране в икономическия анализ
Метод на линейно програмиранедава възможност да се обоснове най-оптималното икономическо решение при условия на строги ограничения, свързани с ресурсите, използвани в производството (дълготрайни активи, материали, трудови ресурси). Използването на този метод в икономическия анализ позволява да се решават проблеми, свързани главно с планирането на дейността на организацията. Този метод помага да се определят оптималните количества продукция, както и насоките за най-ефективно използване на производствените ресурси, с които разполага организацията.
С помощта на този метод се решават така наречените екстремални проблеми, които се състоят в намирането на екстремни стойности, тоест максимума и минимума на функциите променливи.
Този период се основава на решението на системата линейни уравненияв случаите, когато анализираните икономически явления са свързани линейно, строго функционална зависимост. Методът на линейното програмиране се използва за анализ на променливи при наличието на определени ограничаващи фактори.
Много често се решава така наречената транспортна задача с помощта на метода на линейно програмиране. Съдържанието на тази задача е да се минимизират разходите, направени във връзка с експлоатацията на превозни средства при съществуващи ограничения по отношение на броя на превозните средства, тяхната товароподемност, продължителността на тяхната експлоатация, ако има нужда от обслужване на максимален брой клиенти.
В допълнение, този метод се използва широко при решаване на проблема с планирането. Тази задача се състои в такова разпределение на работното време за персонала на дадена организация, което би било най-приемливо както за членовете на този персонал, така и за клиентите на организацията.
Тази задача е да се увеличи максимално броят на обслужваните клиенти при условия на ограничения на броя на наличните служители, както и на фонда работно време.
По този начин методът на линейно програмиране е доста често срещан при анализа на разположението и използването. различни видовересурси, както и в процеса на планиране и прогнозиране дейността на организациите.
Въпреки това, математическото програмиране може да се приложи и към тях икономически явления, връзката между които не е линейна. За тази цел могат да се използват нелинейни, динамични и изпъкнали методи на програмиране.
Нелинейното програмиране разчита на нелинейния характер на целевата функция или ограниченията, или и двете. Формите на целевата функция и ограниченията на неравенството при тези условия могат да бъдат различни.
Нелинейното програмиране се използва в икономическия анализ, по-специално при установяване на връзката между показателите, изразяващи ефективността на дейността на организацията и обема на тази дейност, структурата на производствените разходи, пазарните условия и др.
Динамичното програмиране се основава на конструирането на дърво на решенията. Всяко ниво на това дърво служи като етап за определяне на последствията от предишно решение и за елиминиране на неефективни варианти за това решение. По този начин динамичното програмиране има многоетапен, многоетапен характер. Този вид програмиране се използва в икономическия анализ за намиране на оптимални варианти за развитие на една организация както сега, така и в бъдеще.
Конвексното програмиране е вид нелинейно програмиране. Този тип програмиране изразява нелинейния характер на връзката между резултатите от дейността на организацията и нейните разходи. Изпъкналото (известно още като вдлъбнато) програмиране анализира изпъкнали целеви функции и изпъкнали системи за ограничения (точки за осъществимост). Конвексно програмиране, приложено в анализа стопанска дейностза да се минимизират разходите, а вдлъбнати - за да се максимизират доходите при съществуващите ограничения върху действието на фактори, които влияят върху анализираните показатели по обратен начин. Следователно, с разглежданите типове програмиране, изпъкналите целеви функции са сведени до минимум, а вдлъбнатите целеви функции са максимизирани.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Внимание
Изчистване на всички клетки?
Затвори Изчисти
Инструкции за въвеждане на данни.Числата се въвеждат като цели числа (примери: 487, 5, -7623 и т.н.), десетични знаци (напр. 67., 102,54 и т.н.) или дроби. Дробта трябва да бъде въведена във формата a/b, където a и b (b>0) са цели или десетични числа. Примери 45/5, 6.6/76.4, -7/6.7 и т.н.
Симплексен метод
Примери за решаване на ZLP чрез симплексния метод
Пример 1. Решете следната задача на линейното програмиране:
 |
Дясната страна на ограниченията на системата от уравнения има формата:
Нека запишем текущия референтен план:
 |
Този референтен план не е оптимален, защото в последния ред има отрицателни елементи. Най-големият отрицателен елемент в модула е (-3), следователно векторът е включен в основата х 
при 
. мин(40:6, 28:2)=20/3 съответства на ред 1. Векторът излиза от основата х 3. Нека направим елиминиране по Гаус за колоната х 2, като се има предвид, че водещият елемент съответства на ред 1. Нека нулираме всички елементи от тази колона с изключение на водещия елемент. За да направите това, добавете редовете на ред 2, 3, 4 с ред 1, умножени съответно по -1/3, 1/6, 1/2. След това разделяме линията с водещия елемент на водещия елемент.
Този референтен план не е оптимален, тъй като последният ред има отрицателен елемент (-3), следователно основата включва вектора х 1. Определяме кой вектор излиза от основата. За да направите това, ние изчисляваме 
при 
. min(44/3:11/3, 62/3:5/3)=4 съответства на ред 2. Векторът излиза от основата х 4 . Нека направим елиминирането по Гаус за колоната х 1, като се има предвид, че водещият елемент съответства на ред 2. Нека нулираме всички елементи от тази колона с изключение на водещия елемент. За да направите това, добавете редове 1, 3, 4 с ред 2, умножен съответно по 1/11, -5/11, 9/11. След това разделяме линията с водещия елемент на водещия елемент.
Симплексната таблица ще приеме следната форма:
Текущият референтен план е оптимален, тъй като в редове 4 под променливите 
няма отрицателни елементи.
Решението може да се напише така: 
.
Стойността на целевата функция в този момент: Е(х)=
.
Пример 2. Намерете максимума на функция
Решение.
Базисни вектори х 4 , х 3 следователно всички елементи в колони х 4 , х 3 под хоризонталната линия трябва да е нула.
Нулирайте всички елементи на колоната до нула х 4, с изключение на водещия елемент. За да направите това, добавете ред 3 с ред 1, умножен по 4. Нулирайте всички елементи на колоната до нула х 3, с изключение на водещия елемент. За да направите това, добавете ред 3 с ред 2, умножен по 1.
Симплексната таблица ще приеме формата:
Този референтен план не е оптимален, тъй като последният ред има отрицателен елемент (-11), следователно основата включва вектора х 2. Определяме кой вектор излиза от основата. За да направим това, ние изчисляваме 
при 
. Следователно целевата функция е неограничена отгоре. Тези. проблемът с линейното програмиране е неразрешим.
Примери за решаване на ZLP по метода на изкуствената основа
Пример 1. Намерете максимума на функция
Решение Тъй като броят на базисните вектори трябва да бъде 3, добавяме изкуствена променлива и към целевата функция добавяме тази променлива, умножена по −M, където M е много голямо число:
 |
Матрицата на коефициента на системата от уравнения има формата:
Следователно базисни вектори всички елементи в колоните под хоризонталната линия трябва да са нула.
Нека нулираме всички елементи на колоната с изключение на водещия елемент. За да направите това, добавете ред 5 с ред 3, умножен по -1.
Симплексната таблица ще приеме формата:
Този референтен план не е оптимален, защото в последния ред има отрицателни елементи. Най-големият абсолютен отрицателен елемент е (-5), следователно векторът е включен в базиса. Ние определяме кой вектор излиза от базиса. За да направите това, ние изчисляваме 
при 
съответства на ред 3. Нека да направим гаусово изключение за колоната, като се има предвид, че водещият елемент съответства на ред 3. Нека нулираме всички елементи на тази колона, с изключение на водещия елемент. За да направите това, добавете линиите линия 5 с линия 3, умножена по 1. След това разделете линията с водещия елемент на водещия елемент.
Симплексната таблица ще приеме следната форма:
Този референтен план не е оптимален, защото в последния ред има отрицателни елементи. Най-големият абсолютен отрицателен елемент е (-3), следователно векторът е включен в базиса. Ние определяме кой вектор излиза от базиса. За да направите това, ние изчисляваме 
при 
съответства на ред 1. Векторът излиза от основата х 2. Нека направим елиминиране по Гаус за колоната х 1, като се има предвид, че водещият елемент съответства на ред 1. Нека нулираме всички елементи от тази колона с изключение на водещия елемент. За да направите това, добавете редовете на ред 2, 3, 4 с ред 1, умножени съответно по 3/2, -1/10, 3/2. След това разделяме линията с водещия елемент на водещия елемент.
Симплексната таблица ще приеме следната форма:
Този референтен план не е оптимален, защото в последния ред има отрицателни елементи. Най-големият отрицателен елемент в модул (-13/2), следователно основата включва вектора х 3. Определяме кой вектор излиза от основата. За да направим това, ние изчисляваме 
при 
съответства на ред 3. Векторът излиза от основата х 5. Нека направим елиминиране по Гаус за колоната х 3, като се има предвид, че водещият елемент съответства на ред 3. Нека нулираме всички елементи от тази колона с изключение на водещия елемент. За да направите това, добавете редовете на ред 1, 2, 4 с ред 3, умножени съответно по 5/3, 25/9, 65/9. След това разделяме линията с водещия елемент на водещия елемент.
Симплексната таблица ще приеме следната форма:
Текущият референтен план е оптимален, тъй като няма отрицателни елементи под променливите в редове 4-5.
Решението на първоначалния проблем може да бъде написано по следния начин:
Пример 2. Намерете оптималния план за задача на линейно програмиране:
Матрицата на коефициента на системата от уравнения има формата:
Базисни вектори х 4 , х 5 , х 6 следователно всички елементи в колони х 4 , х 5 , х 6, под хоризонталната линия трябва да е нула.
Нулирайте всички елементи на колоната до нула х 4, с изключение на водещия елемент. За да направите това, добавете ред 4 с ред 1, умножен по -1. Нулирайте всички елементи на колона до нула х 5, с изключение на водещия елемент. За да направите това, добавете ред 5 с ред 2, умножен по -1. Нулирайте всички елементи на колона до нула х 6, с изключение на водещия елемент. За да направите това, добавете ред 5 с ред 3, умножен по -1.
Симплексната таблица ще приеме формата:
В ред 5 елементите, съответстващи на променливите х 1 , х 2 , х 3 , х 4 , х 5 , х 6 са неотрицателни, а числото, разположено в пресечната точка на даден ред и колона х 0 е отрицателно. Тогава първоначалният проблем няма референтен план. Следователно е нерешимо.
Симплексен метод е метод за последователен преход от едно основно решение (връх на полиедъра на решението) на система от ограничения на задача за линейно програмиране към друго основно решение, докато целевата функция приеме оптимална стойност (максимална или минимална).
Симплексният метод е универсален метод, който може да реши всяка задача за линейно програмиране, докато графичният метод е подходящ само за система от ограничения с две променливи.
Симплексният метод е предложен от американския математик Р. Данциг през 1947 г. Оттогава проблемите на линейното програмиране с хиляди променливи и ограничения често се решават с този метод за индустриални нужди.
Преди да преминете към алгоритъма на симплексния метод, няколко дефиниции.
Всяко неотрицателно решение на система от ограничения се нарича приемливо решение .
Нека има система мограничения от нпроменливи ( мн).
Допустимо основно решение е разтвор, съдържащ мнеотрицателни основен (основен ) променливи и н - м неосновни . (неосновен, или Безплатно ) променливи. Малките променливи в основното решение са равни на нула, но главните променливи по правило са различни от нула, т.е. те са положителни числа.
Всякакви мсистемни променливи млинейни уравнения с нсе наричат променливи основен , ако детерминантата на коефициентите при тях е различна от нула. След това останалите н - мсе наричат променливи неосновни (или Безплатно ).
Алгоритъм на симплексния метод
- Етап 1. Намалете проблема с линейното програмиране до канонична форма. За да направите това, преместете свободните членове в дясната страна (ако сред тези свободни членове има отрицателни, тогава умножете съответното уравнение или неравенство по - 1) и въведете допълнителни променливи във всяко ограничение (със знак плюс, ако в първоначалното неравенство знакът е „по-малко или равно на“ ", и със знак минус, ако е „по-голямо или равно").
- Стъпка 2. Ако в получената система муравнения, тогава мвземете променливите за главни, изразете главните променливи чрез небазисните и намерете съответното базисно решение. Ако намереното базисно решение се окаже допустимо, преминаваме към допустимото базисно решение.
- Стъпка 3. Изразете целевата функция по отношение на небазисни променливи на допустимо базисно решение. Ако се намери максимумът (минимумът) на линейна форма и в израза му няма неосновни променливи с отрицателни (положителни) коефициенти, тогава критерият за оптималност е изпълнен и полученото базисно решение е оптимално - решението е пълно. Ако при намиране на максимума (минимума) на линейна форма нейният израз съдържа една или повече неосновни променливи с отрицателни (положителни) коефициенти, преминете към ново основно решение.
- Стъпка 4. От неосновните променливи, включени в линейната форма с отрицателни (положителни) коефициенти, изберете тази, която съответства на най-големия (по абсолютна стойност) коефициент и я преобразувайте в основните. Отидете на стъпка 2.
Важни условия
Някои специални случаи са разгледани в отделни статии: кога максимумът на целевата функция е безкрайност, Кога системата няма решение, и когато оптималното решение не е единственото .
След това ще разгледаме типичен пример, когато системата от ограничения е съвместна и има краен оптимум, при това единствен. Разновидност на симплексния метод е метод на разпространение за решаване на транспортен проблем .
Симплексен метод със симплексни таблици
Чрез конструиране на симплексни таблици решаването на проблем с линейно програмиране е много по-лесно, отколкото чрез алгебрични трансформации, което е показано в следващия параграф. Симплексните таблици са много визуални. Има няколко вида правила за работа със симплексни таблици. Ще разгледаме правило, което най-често се нарича правило за водеща колона и водещ ред.
Би било полезно да отворите ръководството Действия с дроби в нов прозорец: има достатъчно от тях, меко казано, в задачи, използващи симплексния метод.
Пример.
Въвеждаме допълнителни неотрицателни променливи и свеждаме тази система от неравенства до еквивалентната й система от уравнения
.
Това беше направено в съответствие със следното правило: ако оригиналното ограничение има знак „по-малко или равно“, тогава трябва да се добави допълнителната променлива, а ако „по-голямо или равно“, тогава допълнителната променлива трябва да се извади.
Въведените допълнителни променливи се приемат за основни (основни). Тогава и са неосновни (свободни) променливи.
Изразявайки основните (основни) променливи по отношение на неосновни (свободни) променливи, получаваме
Можем също да изразим целевата функция по отношение на непървични (свободни) променливи:
От коефициентите на (неизвестните) променливи ще изградим първата симплексна таблица.
| маса 1 | ||||
| Основни неизвестни | Безплатни членове | Безплатни неизвестни | Спомагателни коефициенти | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| Е | 0 | -1 | -2 | |
Последният ред на таблицата, който съдържа целевата функция и коефициентите на свободните променливи в нея, ще се нарича индексен ред.
Полученото решение не е оптимално, тъй като в индексната линия коефициентите на свободните променливи са отрицателни. Тоест оптималното решение ще бъде такова, при което коефициентите на свободните променливи в индексната линия са по-големи или равни на нула.
За да преминем към следващата таблица, нека намерим най-голямото (по модул) от числата и . Това число е 2. Следователно водещата колона е колоната, в която
За да определим водещия ред, намираме минималното съотношение на свободните членове към елементите на водещата колона и ако числителят е положително число, а знаменателят е отрицателен, отношението се счита за равно на безкрайност.
.
Следователно водещият ред е този, в който е написано
Следователно водещият елемент е -2.
Съставяме втората симплексна таблица.
Въвеждаме новия основен елемент в първия ред, а в колоната, в която е стоял, въвеждаме нова свободна променлива
Попълнете първия ред. За да направим това, разделяме всички числа във водещия ред на таблица 1 на водещия елемент и ги записваме в съответната колона на първия ред на таблица 2, с изключение на числото във водещата колона, където обратното на водещото елемент е написан (т.е. един разделен на водещия елемент).
Попълнете колоната за спомагателни коефициенти. За това число във водещата колона на таблица 1, освен водещия елемент, записваме с противоположни знаци в колоната на спомагателните коефициенти на таблица 2.
| таблица 2 | ||||
| Основни неизвестни | Безплатни членове | Безплатни неизвестни | Спомагателни коефициенти | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| Е | 2 | -2 | -1 | 2 |
Всеки, който все още не е отворил ръководството Действия с дроби в нов прозорец, може да го направи сега, защото е време.
За да получим останалите редове от таблица 2, умножаваме числата от първия ред на тази таблица по спомагателния коефициент в реда за попълване и към резултата добавяме числото от таблица 1, което е в същата ред със съответната променлива.
Например, за да получим свободния член на втория ред, умножаваме числото 1 по 1 и добавяме числото -4 от таблица 1. Получаваме -3. Намираме и коефициента за във втория ред: 
. Тъй като предишната таблица няма колона с нова свободна променлива, коефициентът на втория ред в колоната на новата свободна променлива ще бъде 
(т.е. добавяме 0 от таблица 1, тъй като колона c липсва в таблица 1).
Индексният ред също се попълва:
Така полученото решение отново не е оптимално, тъй като в индексната линия коефициентите на свободните променливи отново са отрицателни.
За да преминем към следващата симплексна таблица, намираме най-голямото (модуло) от числата, т.е. модулите на коефициентите в индексния ред. Това число е 2. Следователно водещата колона е колоната, в която .
За да намерим водещия ред, намираме минималното съотношение на свободните членове към елементите на водещия ред. Получаваме:
.
Следователно водещата линия е тази, в която , а водещият елемент е -3/2.
Съставяне на третата симплексна таблица
Записваме новата базова променлива в първия ред. В колоната, в която , въвеждаме нова свободна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 3 | ||||
| Основни неизвестни | Безплатни членове | Безплатни неизвестни | Спомагателни коефициенти | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| Е | 6 | -4/3 | -1/3 | 2 |
Полученото решение отново не е оптимално, тъй като коефициентите на свободните неизвестни в индексната линия отново са отрицателни.
За да преминем към четвъртата симплексна таблица, намираме най-голямото от числата и . Това е числото.
Следователно водещата колона е тази, в която .
Минимални модули на отношенията на свободните членове към елементите на водещата колона:
.
Следователно водещата линия е тази, в която , а водещият елемент е 1/3.
В четвъртата симплексна таблица записваме новата базова променлива като първи ред. В колоната където записваме нова безплатна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 4 | ||||
| Основни неизвестни | Безплатни членове | Безплатни неизвестни | Спомагателни коефициенти | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| Е | 14 | 4 | -3 | 4/3 |
Изчисляване на останалите редове, като се използва вторият ред като пример:
Полученото решение също не е оптимално, но вече е по-добро от предишните, тъй като един от коефициентите на свободните променливи в линията на индекса е неотрицателен.
За да подобрим плана, нека преминем към следващата симплексна таблица.
Нека намерим най-голямото от числата 4 и . Това число е 4. Следователно водещата колона е .
Да намерим водещата линия, която намираме
.
Следователно водещата линия е тази, в която . Но те вече бяха заедно сред свободните променливи. Следователно, за да прехвърлим следващата променлива от свободна към основна, избираме друга водеща колона - тази, в която .
Да намерим водещата линия, която намираме
.
Следователно ключовият ред е този, в който , а водещият елемент е 1.
В петата симплексна таблица записваме новата базова променлива като първи ред. В колоната където записваме нова безплатна променлива.
Първа линия:
Спомагателни коефициенти:
| Таблица 5 | ||||
| Основни неизвестни | Безплатни членове | Безплатни неизвестни | Спомагателни коефициенти | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| Е | 20 | 1 | 3 | 3 |
Нека се опитаме веднага да разберем дали решението е оптимално. Следователно за останалите редове изчисляваме само свободните членове (за да разберем стойностите на основните променливи, когато свободните променливи са равни на нула) и коефициентите за свободните променливи в индексния ред.
Безплатни членове:
Във втория ред;
В третия ред;
В четвъртия ред.
Индексна линия:
Разглеждаме симплексна таблица 5. Виждаме, че е получено оптималното решение, тъй като коефициентите за свободните неизвестни в индексния ред са неотрицателни.
Симплексен метод с алгебрични трансформации
Нека решим същия пример като в предишния параграф, използвайки алгебрични трансформации. Трябва да се отбележи, че когато се решава този тип симплексен метод, е по-добре да не се записва целевата функция във формата , тъй като е лесно да се объркате в знаците. Но в този случай точката на алгоритъма, която определя критерия за оптималност, ще бъде модифицирана, както следва.
Ако се намери максимумът (минимумът) на линейна форма и в израза му няма неосновни променливи с положителни (отрицателни) коефициенти, тогава критерият за оптималност е изпълнен и полученото базисно решение е оптимално - решението е пълно. Ако при намиране на максимума (минимума) на линейна форма нейният израз съдържа една или повече неосновни променливи с положителни (отрицателни) коефициенти, преминете към ново основно решение.
Пример.Намерете максимума на функция при ограничения
Стъпка I. Въвеждаме допълнителни неотрицателни променливи и свеждаме тази система от неравенства до еквивалентната й система от уравнения
.
Ние приемаме въведените допълнителни променливи като основни, тъй като в този случай основното решение на системата се намира лесно. Тогава и са неосновни променливи.
Изразявайки основните променливи по отношение на неосновните, получаваме
Следователно това разделение на променливите на основни и неосновни съответства на основното решение 
, което е невалидно (две променливи са отрицателни) и следователно не е оптимално. Нека преминем от това основно решение към подобрено.
За да решите коя променлива трябва да бъде прехвърлена от второстепенна към основна, разгледайте всяко от двете налични уравнения на последната система с отрицателни свободни членове, например второто. Това показва, че и могат да бъдат преобразувани в главни променливи, тъй като в това уравнение те имат положителни коефициенти (следователно, когато се увеличават, а това ще се случи, ако преобразуваме някоя от тях в главни променливи, променливата ще се увеличава).
Нека се опитаме да го преведем в основната променлива. За да установим коя променлива трябва да се преобразува от основна в неосновна, намираме абсолютната стойност на най-малкото съотношение на свободните членове на системата към коефициентите при . Ние имаме. Получава се от третото уравнение, което показва, че променливата, която е положителна в първоначалното основно решение, трябва да се преобразува в неосновни. Следователно полученото основно решение, подобно на първоначалното, съдържа два отрицателни компонента, т.е. при преминаване към такова основно решение няма да има подобрение.
За направата на три вида ризи се използват конци, копчета и плат. Запасите от конци, копчета и тъкани, нормите на тяхното потребление за шиене на една риза са посочени в таблицата. Намерете максималната печалба и оптималния план за производство на продукта, който я осигурява (намерете).
| риза 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 рубли.
Необходимо е да се реши задача на линейно програмиране.
Целева функция:
2x 1 +5x 2 +3x 3 +8x 4 → мин
Ограничителни условия:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Нека приведем системата от ограничения в канонична форма; за това е необходимо да преминем от неравенства към равенства, с добавяне на допълнителни променливи.
Тъй като нашият проблем е проблем за минимизиране, трябва да го трансформираме в проблем за максимално търсене. За да направите това, нека променим знаците на коефициентите на целевата функция на противоположни. Записваме елементите на първото неравенство непроменени, като добавяме допълнителна променлива x 5 и променяме знака „≤“ на „=“. Тъй като второто и третото неравенство имат знаци „≥“, е необходимо знаците на техните коефициенти да се променят на противоположни и да се въведат допълнителни променливи x 6 и x 7 съответно в тях. В резултат на това получаваме еквивалентен проблем:
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
Пристъпваме към формирането на началната симплексна таблица. На ред F от таблицата се въвеждат коефициентите на целевата функция с обратен знак.
|
Безплатен член |
|||||
| Е | |||||
| X5 | |||||
| X6 | |||||
| X7 |
В таблицата, която съставихме, има отрицателни елементи в колоната със свободни членове, сред тях намираме максимума по модул - това е елементът: -6, той задава водещия ред - X6. В този ред намираме и максималния отрицателен елемент в модул: -10 той се намира в колона X3, която ще бъде водещата колона. Променливата във водещия ред се изключва от основата, а променливата, съответстваща на водещата колона, се включва в основата. Нека преизчислим симплексната таблица:
| X1 | X2 | X6 | X4 | Безплатен член | |
| Е | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
| X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
| X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
| X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
В таблицата, която съставихме, има отрицателни елементи в колоната със свободни членове, сред тях намираме максимума по модул - това е елементът: -0,4, той задава водещия ред - X7. В този ред намираме и максималния отрицателен елемент в модул: -8,3 той се намира в колона X2, която ще бъде водещата колона. Променливата във водещия ред се изключва от основата, а променливата, съответстваща на водещата колона, се включва в основата. Нека преизчислим симплексната таблица:
| X1 | X7 | X6 | X4 | Безплатен член | |
| Е | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
| X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
| X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
| X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Тъй като в колоната със свободни членове няма отрицателни елементи, е намерено допустимо решение, което съдържа отрицателни елементи, което означава, че полученото решение не е оптимално. Нека дефинираме водещата колона. За да направим това, ще намерим в ред F отрицателния елемент с максимален модул - това е -1,988 Водещият ред ще бъде този, за който отношението на свободния член към съответния елемент на водещата колона е минимално. Водещият ред е X2, а водещият елемент е: 0,313.
| X2 | X7 | X6 | X4 | Безплатен член | |
| Е | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
| X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
| X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
| X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
Тъй като в низа F няма отрицателни елементи, тогава
оптималното решение е намерено. Тъй като първоначалната задача беше да се намери минимумът, оптималното решение ще бъде свободният член на низа F, взет с обратен знак. F=1,924
с променливи стойности равни: x 3 =0,539, x 1 =0,153. Променливите x 2 и x 4 не са включени в основата, така че x 2 =0 x 4 =0.
Подобни статии
