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

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

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

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

1. Приведете проблема в канонична форма
2. Намерете първоначалното решение за поддръжка с „основа на единица“ (ако няма решение за поддръжка, тогава проблемът няма решение поради несъвместимостта на системата от ограничения)
3. Изчислете оценки на векторни разложения на базата на референтното решение и попълнете таблицата на симплексния метод
4. Ако критерият за уникалност на оптималното решение е изпълнен, тогава решението на задачата приключва
5. Ако условието за съществуване на набор от оптимални решения е изпълнено, тогава всички оптимални решения се намират чрез просто изброяване

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

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

Решение:

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

За да направим това, въвеждаме допълнителна променлива 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

х 1

+х 2

+х 3

х 1

+х 2

+х 3

х 1

+х 2

+х 3

×

Внимание

Изчистване на всички клетки?

Затвори Изчисти

Инструкции за въвеждане на данни.Числата се въвеждат като цели числа (примери: 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 е отрицателно. Тогава първоначалният проблем няма референтен план. Следователно е нерешимо.

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

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

Алгоритъм за графичния метод за решаване на задачи

Ще разгледаме прилагането на графичния метод за решаване на ZLP с помощта на примери.

Пример 2.2.1. Решете ZLP графично:

(2.2.1)

макс z=х 1 + 4х 2 (2.2.2)

Решение.За да конструираме област от възможни решения, която се състои от пресичане на полуравнини, съответстващи на всяко неравенство на системата от ограничения (2.2.1), записваме уравненията на граничните прави линии:

л 1: х 1 + 5х 2 = 5; л 2: х 1 + х 2 = 6; л 3: 7х 1 + х 2 = 7.

л 1 на формата (2.2.3.) разделяме двете му части на 5:
. Така, направо л 1 реже по ос о 1 5 единици, на ос о 2 1 единица. По същия начин имаме за л 2:
И л 3:
.

За да определите полуравнини, които отговарят на ограниченията на системата (2.2.1), трябва да замените координатите на всяка точка, която не лежи на граничната линия, в ограниченията. Ако получим истинско неравенство, то всички точки от тази полуравнина са решения на това неравенство. В противен случай изберете друга полуравнина.

Така първата и втората желани полуравнини са разположени в обратна посока от началото на координатите (0 – 5 0 - 5; 7 0 + 0 7), а втората – към началото на координатите (0 + 0 6). Областта на осъществимите решения на фигура 2.2.1 е защрихована.

Фигура 2.2.1 – Област на осъществими решения

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

В тази задача векторът на посоката
= (1, 4): започва от точката ОТНОСНО(0,0) и завършва в точката н(1, 4).

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

По този начин максималната точка на целевата функция zе точката Апресичания на линии л 2 и л 3 .

Да се ​​изчисли оптималната стойност на целевата функция z намерете координатите на точкатаА . Тъй като точкатаА е пресечната точка на линиител 2 ил 3, тогава неговите координати удовлетворяват система от уравнения, съставена от уравненията на съответните гранични линии:

Така че точкатаА има координатих 1 =1/6, х 2 = 35/6.

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

Заместване на координатите на точкатаА в целевата функция (2.4), получаваме

макс z = 1/6 + 4·(35/6) = 47/2.

Пример 2.2.2. Конструирайте в равнината областта на възможните решения на системата от линейни неравенства (2.2.4) и намерете най-големите и най-малките стойности на целевата функция (2.2.5):

(2.2.4)

z= –2х 1 –х 2 (2.2.5)

Решение.За да конструираме област от възможни решения, която се състои от пресичане на полуравнини, съответстващи на всяко неравенство на системата от ограничения (2.2.4), записваме уравненията на граничните прави линии:

л 1: 4х 1 – х 2 = 0; л 2: х 1 + 3х 2 = 6; л 3: х 1 – 3х 2 = 6; л 4: х 2 = 1.

Направо л 1 минава през точката с координати (0;0). За да го конструираме, ние изразяваме х 2 чрез х 1: х 2 = 4х 1 . Нека намерим друга точка, през която минава правата л 1, например (1;4). През точката с координати (0;0) и точката с координати (1;4) прекарваме права линия л 1 .

Да се ​​намали уравнението на права линия л 2 до формата на сегменти по осите (2.2.3), разделяме двете му части на 6:
. Така, направо л 2 разфасовки по оста о 16 единици, на ос о 2 - 2 единици. По същия начин имаме за л 3:
и Директно л 4 успоредно на оста о 1 и минава през точката с координати (0;1) .

За да се определят полуравнини, които отговарят на ограниченията на системата (2.2.4), е необходимо да се заменят координатите на всяка точка, която не лежи на граничната линия в ограниченията. Поради ограничениях 1 0, х 2 0, областта на допустимите решения на ZLP лежи в първата четвърт на координатната равнина.

ОТНОСНО
областта на осъществимите решения на фигура 2.2.2 е защрихована.

Фигура 2.2.2 – Област на осъществими решения

Нека построим вектор от посоки
= (–2,–1). След това изграждаме линия на ниво, перпендикулярна на вектора .

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

Да се ​​изчисли оптималната стойност на целевата функция zнамерете координатите на точката А. Тъй като точката Ае пресечната точка на линиите л 1 и л 2, тогава неговите координати удовлетворяват система от уравнения, съставена от уравненията на съответните гранични линии:

Така че точкатаА има координатих 1 =6/13, х 2 = 24/13.

Заместване на координатите на точкатаА в целевата функция (2.2.5), получаваме оптималната стойност на целевата функция

макс z= – 2·(6/13) – (24/13) = – 36/13.

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

В резултат на решението на ПЧП са възможни следните случаи:

Целевата функция достига своята оптимална стойност в един връх на многоъгълника на решението;

Целевата функция достига своята оптимална стойност във всяка точка на ръба на многоъгълника на решение (ZLP има алтернативни референтни планове със същите стойности z );

PAP няма оптимални планове;

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

Най-простият и визуален метод на линейно програмиране (LP) е графичният метод. Използва се за решаване на проблеми с LP с две променливи. Разгледайте проблема с LP в стандартна форма:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Да сложим n=2и ще разгледаме проблема в самолета. Нека системата от неравенства е последователна (има поне едно решение).

Всяко неравенство на тази система геометрично определя полуравнина с граничната линия a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, м. Условията за неотрицателност определят полуравнини с гранични прави x 1 = 0, x 2 = 0, съответно. Системата е последователна, следователно полуравнините, като изпъкнали множества, пресичащи се, образуват обща част, която е изпъкнало множество и е колекция от точки, където координатите на всяка точка са решение на тази система. Наборът от тези точки се нарича многоъгълник на решение. Може да бъде точка, отсечка, лъч, ограничен или неограничен многоъгълник.

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

Линейно уравнение описва набор от точки, лежащи на една права. Линейно неравенство описва някаква област в равнината. Нека определим коя част от равнината се описва от неравенството 2x 1 + 3x 2 12.

Първо, нека построим права линия 2x 1 + 3x 2= 12. Минава през точките (6; 0) и (0; 4). За да се определи коя полуравнина удовлетворява неравенството, е необходимо да се избере всяка точка от графиката, която не принадлежи на правата, и да се заменят нейните координати в неравенството. Ако неравенството е в сила, тогава дадената точка е допустимо решение и полуравнината, съдържаща точката, удовлетворява неравенството. За заместване в неравенството е удобно да използвате началната точка. Заместете x 1 = x 2 = 0 в неравенството 2x 1 + 3x 2 12. Получаваме 2x0 + 3x0 12. Това твърдение е вярно, следователно неравенството 2x 1 + 3x 2 12 съответства на долната полуравнина, съдържаща точката (0; 0). Това е отразено в графиката, показана на фиг. 1.1.

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

Решението на всяко неравенство на ограничителната система ZLP е полуравнина, съдържаща граничната линия и разположена от едната й страна. Пресечната точка на полуравнини, всяка от които се определя от съответното неравенство на системата, се нарича област на допустимите решения или област на дефиниция. Трябва да се помни, че областта на възможните решения отговаря на условията за неотрицателност ( x j 0, j = 1, 2, …,н). Координатите на всяка точка, принадлежаща към домейна на дефиниция, са валидно решение на проблема.

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

Този вектор показва посоката на най-бързата промяна на целевата функция. Директна линия с 1 x 1 + с 2 x 2 = f(x 0), перпендикулярна на вектора на градиента, е линията на нивото на целевата функция. Във всяка точка на линията на нивото целевата функция приема същата стойност. Нека приравним целевата функция към постоянна стойност "А". Променяйки стойността на „a“, получаваме семейство от успоредни линии, всяка от които е линия на ниво на целевата функция.

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

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

Графичен методрешението на ПЧП се състои от следните етапи.

1. Построена е полигонална област от допустими решения (ADS) на ПЛР.

2. Градиентният вектор на целевата функция (TF) се конструира в някаква точка x 0, принадлежаща на ODR:

3. Линията на нивото c 1 x 1 + c 2 x 2 = a (a е постоянна стойност) - права линия, перпендикулярна на градиентния вектор - се движи в посоката на този вектор в случай на максимизиране на f (x 1, x 2) докато напусне ODR. Граничната точка (или точки) на областта по време на това движение е максималната точка f(x 1, x 2).

4. За да се намерят координатите на максималната точка, е достатъчно да се решат две уравнения на права линия, получени от съответните ограничения и даващи максималната точка в пресечната точка. Стойността f(x 1, x 2), намерена в резултатната точка, е максималната.

При минимизиране (максимизиране) на функцията f(x 1, x 2) линията на нивото се движи в посока, обратна на градиентния вектор. Ако правата, съответстваща на линията на нивото, не напуска ODR по време на движението си, тогава минимумът (максимумът) на функцията f(x 1, x 2) не съществува.

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

Таблица 1.3

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

Пример 1.1. Планиране на производството на шивашко предприятие (проблем за костюми).

Предвижда се да бъдат пуснати два вида костюми - мъжки и дамски. За един женски костюм са необходими 1 м вълна, 2 м лавсан и 1 човек/ден труд. За мъжки костюм - 3,5 м вълна, 0,5 м лавсан и 1 човек/ден труд. Общо има 350 м вълна, 240 м лавсан и 150 човекодни труд. Необходимо е да се определи колко костюма от всеки вид трябва да бъдат направени, за да се осигури максимална печалба, ако печалбата от продажбата на дамски костюм е 10 парични единици, а от мъжки костюм - 20 парични единици. Трябва да се има предвид, че е необходимо да се ушият поне 60 мъжки костюма.

Нека въведем следното обозначение: x 1 - броят на дамските костюми; x 2 – брой мъжки костюми. Печалбата от продажбата на дамски костюми е 10х1, а от продажбата на мъжки костюми - 20х2, т.е. необходимо е да се максимизира целевата функция:

10x 1 + 20x 2

Ограниченията на задачата имат формата:

x 1 + x 2 150,

2 x 1 + 0,5 x 2 240,

х 1 + 3,5 х 2 350,

х 2 60,

х 1 0.

Първото работно ограничение е x 1 + x 2 150. Правата x 1 + x 2 = 150 минава през точките (150; 0) и (0; 150) (фиг. 1.2).

Второто ограничение за лавсан е 2 x 1 + 0,5 x 2 240. Правата линия 2 x 1 + 0,5 x 2 = 240 минава през точките (120; 0) и (0; 480). Трето ограничение за вълна x 1 + 3,5x 2 350. Нека добавим четвърто ограничение за броя на мъжките костюми x 2 60. Решението на това неравенство е полуравнината, лежаща над правата x 2 = 60. На фиг. 1.3 областта на възможните решения е защрихована. За да определим посоката на движение към оптимума, изграждаме градиентен вектор, чиито координати са частични производни на целевата функция, т.е.

За да конструирате такъв вектор, трябва да свържете точката (10;20) с началото. При максимизиране на целевата функция е необходимо да се движите по посока на градиентния вектор, а при минимизиране - в обратна посока. За удобство можете да конструирате вектор, пропорционален на вектора. И така, на фиг. 1.4 показва градиентния вектор (30;60).

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

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

х 1 + 3,5 х 2 = 350,

x 1 + x 2 = 150.

От тук е лесно да запишете решението на оригиналния ZLP: макс. f(x)= 2300 и се постига при x 1 = 70 и x 2 = 80 (виж фиг. 1.4).

1.3.ТЕХНОЛОГИЯ ЗА РЕШАВАНЕ НА ПРОБЛЕМИ С ЛИНЕЙНО ПРОГРАМИРАНЕ С ИЗПОЛЗВАНЕ НА ДОБАВКАТА ЗА ТЪРСЕНЕ НА РЕШЕНИЯ В СРЕДАТА НА EXCEL

1.3.1. Главна информацияотносно работата с процесора за електронни таблици на Excel

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

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

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

Работа с формули.Програмите за електронни таблици използват формули за извършване на много различни изчисления. С помощта на Excel можете бързо да създадете формула. Формулата се състои от три основни части:

1) знак за равенство;

2) набор от стойности или препратки в клетките, с които се извършват изчисления;

3) оператори.

4) Ако няма знак за равенство, тогава Excel интерпретира данните не като формула, а като данни, въведени в клетка. Формулите могат да се въвеждат директно в клетка или в лентата с формули - текст или числа. В този случай трябва да изпълните следните стъпки:

· изберете клетката, която трябва да съдържа формулата и въведете знака (=);

· въведете оператор или знак за действие;

· изберете друга клетка, включена във формулата;

· натиснете клавиша Enter.

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

Използване на функции във формули. За да улесните въвеждането на формули, можете да използвате функциите на Excel. Функциите са формули, вградени в Excel. Excel съдържа много формули. Те са групирани по различни видове: логически, математически, инженерни, статистически и др.

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

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

Find a Solution е добавка на Excel, която ви позволява да решавате проблеми с оптимизацията. Ако командата Търсене на решение не е налична в менюто Инструменти, тогава трябва да изтеглите тази добавка. Изберете командата Инструменти => Добавки и активирайте добавката Търсене на решение. Ако тази добавка не е в диалоговия прозорец Добавки, тогава трябва да отидете в панела Управление на Windows, щракнете върху иконата Добавяне или премахване на програми и използвайте инсталатора на Excel (или Office), за да инсталирате добавката Find a Solution.

След избиране на командите Инструменти => Търсене на решение ще се появи диалоговият прозорец Търсене на решение.

Има три основни опции в диалоговия прозорец Намиране на решение;

Задайте целева клетка.

Смяна на клетки.

Ограничения.

Първо трябва да попълните полето Set target cell. Във всички задачи за инструмента Find a Solution се оптимизира резултатът в една от клетките на работния лист. Целевата клетка е свързана с други клетки в този работен лист с помощта на формули. Инструментът Find Solution използва формули, които дават резултат в целевата клетка за проверка възможни решения. Можете да изберете да намерите най-малката или най-голямата стойност за целевата клетка или да зададете конкретна стойност.

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

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

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

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

2) въведете първоначалните данни;

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

4) въвеждане на зависимости за ограничения,

5) изпълнете командата Търсене на решения;

6) присвояване на клетка на целевата функция (задаване на целева клетка);

7) въвеждат ограничения;

8) въведете параметри за решаване на PLP.

Нека разгледаме технологията на решение, използвайки условията на пример 1.1 (проблемът с костюма).

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

Нека x 1 е броят на дамските костюми; x 2 - броят на мъжките костюми,

10 x x 1 + 20 x x 2 макс

Ограниченията на задачата имат формата:

x 1 + x 2 150 - ограничение на труда;

2 x x 1 + 0,5 x х 2240 - лимит на лавсан;

x 1 + 3,5 x x 2 350 - лимит на вълна;

х 2 60 - лимит за мъжки костюми;

х 1 0 - ограничение за дамски костюми.

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

Означете с x 1 , x 2 броя на боите от всеки тип. В нашия проблем оптималните стойности на вектора = (x 1, x 2) ще бъдат поставени в клетки A2: B2, оптималната стойност на целевата функция - в клетка S3.

2. Въведете първоначалните данни.

Въведете първоначалните данни за задачата, както е показано на фиг. 1.6.

3. Въведете зависимост за целевата функция.

· Поставете курсора в клетката “NW”, клетката ще бъде избрана.

· Поставете курсора върху бутона Function Wizard, разположен на лентата с инструменти.

· Въведете Въведете. На екрана се появява диалоговият прозорец на съветника за функции стъпка 1 от 2.

· В прозореца Функции изберете реда SUMPRODUCT (фиг. 1.7). На екрана

· появява се диалоговият прозорец SUMPRODUCT (фиг. 1.8).

· Въведете в реда Array 1 A2:B2.

· Въведете AZ:VZ в реда Array 2.

Масив 1 ще се използва при въвеждане на зависимости за ограничения, така че трябва да се направи абсолютна препратка към този масив. На фиг. Фигура 1.9 показва, че функция е въведена в клетка SZ.

5. Въведете зависимости за ограниченията (Фигура 1.10).

· Поставете курсора в клетка NW.

· В лентата с инструменти има бутон Копиране в клипборда.

· Поставете курсора в клетка C4.

· Поставете курсора в клетка C5.

· В лентата с инструменти бутонът Поставяне от клипборда.

· Поставете курсора в клетката Sat.

· В лентата с инструменти бутонът Поставяне от клипборда.

· Поставете курсора в клетка C7.

· В лентата с инструменти щракнете върху бутона Поставяне от клипборда. (Съдържанието на клетки C4-C7 трябва да бъде отметнато. Те трябва да съдържат информация, както е показано например на фиг. 1.11; съдържанието на клетка C5 е представено като пример.)

· В реда на менюто поставете показалеца на мишката върху услуга. В разширеното меню изберете командата Търсене на решение. Появява се диалоговият прозорец Търсене на решение (фиг. 1.12).

5. Изпълнете командата Търсене на решение.

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

· Поставете курсора в линията Set target cell.

· Въведете адреса на клетка $С$3.

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

· Поставете курсора в ред, като променяте клетките.

· Въведете адресите на необходимите променливи A$2:B$2 (фиг. 1.13).

7. Въведете ограничения.

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

· Въведете знак за ограничение.

· В реда Ограничение въведете адреса $D$4 (фиг. 1.14).

· Поставете показалеца на мишката върху бутона Добавяне. Диалоговият прозорец Добавяне на ограничение ще се появи отново.

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

· След като въведете последното ограничение, щракнете върху бутона OK. На екрана ще се появи диалогов прозорец Търсене на решение с въведените условия (фиг. 1.15).

8. Въведете параметри за решаване на задачата за линейно програмиране.

· В диалоговия прозорец поставете показалеца на мишката върху бутона Опции. На екрана ще се появи диалогов прозорец Опции за търсене на решение (фиг. 1.16).

· Поставете отметки в квадратчетата в Линеен модел (това ще гарантира използването на симплексния метод) и Неотрицателни стойности.

· Поставете показалеца на мишката върху бутона OK. На екрана ще се появи диалоговият прозорец Търсене на решение.

· Поставете показалеца на мишката върху бутона Run.

След кратко време ще се появи диалоговият прозорец с резултати от търсенето на решение и оригиналната таблица с попълнени клетки AZ:VZ за стойности x i и клетка SZ c максимална стойностцелева функция (фиг. 1.17).

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

В резултат на решаването на проблема беше получен отговорът: необходимо е да се шият 70 бр. дамски костюми и 80 бр. мъжки костюми, за да получите максимална печалба от 2300 USD.

1.4. ДУАЛНОСТ В ЗАДАЧИТЕ НА ЛИНЕЙНОТО ПРОГРАМИРАНЕ. АНАЛИЗ НА ПОЛУЧЕНИТЕ ОПТИМАЛНИ РЕШЕНИЯ

През 1975 г. нашият сънародник Л.В. Канторович е удостоен с Нобелова награда по икономика (заедно с американския икономист Т. Купманс) за разработването на теорията за оптималното използване на ресурсите (виж Приложение 1).

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

Променливите на двойствения проблем y i се наричат ​​обективно определени оценки, или двойни оценки, или „цени” на ресурсите, или цени в сянка.

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

Двойната задача по отношение на първоначалната се съставя по следните правила:

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

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

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

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

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

Първа теорема за двойственост. За взаимно двойни проблеми възниква един от взаимно изключващите се случаи.

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

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

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

4. И двете разглеждани задачи имат празни допустими множества.

Втора теорема за дуалност (допълнителна теорема за нетвърдост). Нека = ( x 1, x 2,..., x n) е допустимо решение на пряката задача, a = (y 1,y 2,...,y t) е допустимо решение на двойната задача. За да бъдат те оптимални решения съответно на преките и дуалните задачи, е необходимо и достатъчно да са изпълнени следните съотношения:

Условия (1.4) и (1.5) позволяват, като се знае оптималното решение на един от взаимно двойствените проблеми, да се намери оптималното решение на друг проблем.

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

Теорема за оценка. Стойностите на променливите y i в оптималното решение на двойния проблем представляват оценки на влиянието на свободните членове b i на системата от ограничения (неравенства) на директния проблем върху стойността

Чрез решаване на ZLP, използвайки симплексния метод, ние едновременно решаваме двойния ZLP. Променливите на двойствения проблем y i се наричат ​​обективно определени оценки.

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

Пример 1 .2. Използвайки постановката на проблема с килима, изпълнете следните задачи.

1. Формулирайте икономико-математически модел на задачата за килими за максимална обща себестойност на продукцията, като използвате данните от табл. 1.1.

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

3. Формулирайте икономико-математически модел на двойствената задача към проблема с килима.

4. Намерете оптималния план за двойствения проблем, като използвате теореми за двойственост, обяснете равенството на нула на X 1 и X 4.

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

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

1. Нека формулираме икономико-математически модел на проблема.

Нека означим с X 1, X 2, X 3, X 4 броя на килимите от всеки тип. Целевата функция има формата

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 макс.,

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

7Х 1 + 2Х 2 + 2Х 3 + 6X 4 80,

5Х 1 + 8Х 2 + 4 X 3 + ZH 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130,

X 1, X 2, X 3, X 4 0.

2. Търсете оптималния план за освобождаване.

Нека решим проблема с помощта на добавка Търсене в Excelрешения. Технологията за решаване на проблема беше разгледана подробно в проблема с костюма. В нашия проблем оптималните стойности на вектора X = (X 1, X 2, X 3, X 4) ще бъдат поставени в клетки VZ: EZ, оптималната стойност на целевата функция - в клетката F4.

Да въведем първоначалните данни. Първо, ние описваме целевата функция с помощта на функцията - SUMPRODUCT (фиг. 1.19). След това ще въведем данни за левите части на ограниченията. В Търсене на решение ще въведем посоката на целевата функция, адресите на търсените променливи и ще добавим ограничения. На екрана ще се появи диалогов прозорец Търсене на решение с въведените условия (фиг. 1.20).

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

Полученото решение означава, че максималният доход е 150 хиляди рубли. една фабрика може да получи 30 килима от втори тип и 10 килима от трети тип при производство. В този случай ресурсите „труд” и „оборудване” ще бъдат използвани напълно, като от 480 кг прежда (ресурс „суровини”) ще бъдат използвани 280 кг.

Създаване на отчет въз основа на резултатите от търсенето на решение. Excel ви позволява да представите резултатите от търсенето на решение под формата на отчет (Таблица 1.4). Има три вида такива отчети:

· Резултати (Отговор). Отчетът включва началните и крайните стойности на целевите и модифицираните клетки и допълнителна информация за ограниченията.

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

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

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

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

Всяко от неравенствата на задачата за линейно програмиране определя определена полуравнина на координатната равнина, а системата от неравенства като цяло определя пресечната точка на съответните равнини. Множеството от пресечни точки на тези полуравнини се нарича област приемливо разтвори (ODR). ODR винаги е изпъкнала фигура, т.е. има следното свойство: ако две точки A и B принадлежат на тази фигура, то цялата отсечка AB принадлежи на нея. ODR може да бъде представен графично чрез изпъкнал многоъгълник, неограничена изпъкнала многоъгълна област, сегмент, лъч или една точка. Ако системата от ограничения в задача (1) е непоследователна, ODS е празно множество.

Всичко по-горе се отнася и за случая, когато системата от ограничения (1) включва равенства, тъй като всяко равенство

може да се представи като система от две неравенства

Цифровият филтър при фиксирана стойност определя права линия в равнината. Променяйки стойностите на L, получаваме семейство от успоредни прави, наречени линии ниво.

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

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

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

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

Фигура 1 Геометрична интерпретация на ограниченията и TF на проблема

Нека разгледаме техника за решаване на проблеми с LP с помощта на графичния метод.

• 1) в ограниченията на задача (1) заменете знаците за неравенство с точни знаци за равенство и построете съответните прави линии;
• 2) намерете и засенчете полуравнините, разрешени от всяко от ограниченията на неравенството на задача (1). За да направите това, трябва да замените координатите на точка [например (0;0)] в конкретно неравенство и да проверите истинността на полученото неравенство.

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

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

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

• 3) дефинирайте ODR като част от равнината, която едновременно принадлежи на всички разрешени зони и я изберете. При липса на SDT проблемът няма решения;
• 4) ако ODR не е празен набор, тогава трябва да конструирате целевата линия, т.е. всяка от линиите на нивото (където L е произволно число, например кратно и т.е. удобно за изчисления). Методът на конструиране е подобен на конструирането на директни ограничения;
• 5) конструирайте вектор, който започва в точката (0;0) и завършва в точката. Ако целевата линия и вектор са конструирани правилно, тогава те ще бъдат перпендикулярни;
• 6) при търсене на максималния CF е необходимо да преместите целевата линия до посока на вектора, при търсене на минималния CF - срещу векторни посоки. Последният връх на ODR в посоката на движение ще бъде точката на максимум или минимум на CF. Ако такава точка(и) не съществува, тогава можем да заключим, че CFНа много планове отгоре (при търсене на максимума) или отдолу (при търсене на минимума);
• 7) определяне на координатите на точката max (min) на цифровия филтър и изчисляване на стойността на цифровия филтър. За да се изчислят координатите на оптималната точка, е необходимо да се реши система от уравнения на линиите, в пресечната точка на които се намира.

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

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

Фигура 2 Преход от един връх към друг

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

Симплексен метод – универсален метод за решаване линейна системауравнения или неравенства и линеен функционал.

Алгоритъм за решаване на ЗЛП по симплексния метод.

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

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

• 1) в съставената таблица първо трябва да погледнете колоната с безплатни членове. Ако в него има отрицателни елементи, тогава е необходимо да преминете към втората стъпка, ако не, тогава към петата;
• 2) на втората стъпка е необходимо да се реши коя променлива да се изключи от основата и коя да се включи, за да се преизчисли симплексната таблица. За да направите това, прегледайте колоната с безплатни условия и намерете отрицателен елемент в нея. Линията с отрицателен елемент ще се нарича водеща. В него намираме максималния отрицателен елемент по модул, съответната колона е подчинената. Ако има отрицателни стойности сред свободните условия, но не и в съответния ред, тогава такава таблица няма да има решения. Променливата във водещия ред, разположена в колоната със свободни термини, се изключва от основата, а променливата, съответстваща на водещата колона, се включва в основата. Таблица 1 показва пример на симплексна таблица.

маса 1

Пример за симплексна таблица

• 3) в третата стъпка преизчисляваме цялата симплексна таблица, използвайки специални формули;
• 4) ако след преизчисляване в колоната със свободни термини останат отрицателни елементи, преминете към първата стъпка, ако няма такива елементи, след това към петата;
• 5) ако сте стигнали до петата стъпка, значи сте намерили решение, което е приемливо. Това обаче не означава, че е оптимално. Оптимално ще бъде само ако всички елементи в F-низата са положителни. Ако това не е така, тогава е необходимо да се подобри решението, за което намираме водещия ред и колона за следващо преизчисляване по следния алгоритъм. Първоначално намираме минималното отрицателно число в низа F, като изключим стойността на функцията. Колоната с това число ще бъде водеща. За да намерим водещия ред, намираме отношението на съответния свободен член и елемента от водещия стълб, при условие че са положителни. Минималното съотношение ще ви позволи да определите водещата линия. Преизчисляваме отново таблицата по формулите, т.е. отидете на стъпка 3;
• 6) ако е невъзможно да се намери водещият ред, тъй като във водещата колона няма положителни елементи, тогава функцията в областта на възможните решения на проблема не е ограничена отгоре и F max ->?. Ако всички елементи в ред F и колоната със свободни членове са положителни, тогава оптималното решение е намерено.