• У дома
  •  > 
  • проблеми с ОС
  •  > 
  • Линейно програмиране. Методологическа основа за разработване на управленски решения Решението се нарича оптимално

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

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

Задачи за оптимизация: обща информация

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

В зависимост от свойствата на функциите оптимизационните проблеми могат да бъдат разделени на два вида:

  • задача за линейно програмиране (всички функции са линейни);
  • проблем с нелинейно програмиране (поне една от функциите не е линейна).

Специални случаи на оптимизационни проблеми са дробно-линейни, динамични и стохастични програмни задачи.

Най-изследваните оптимизационни проблеми са задачите на линейното програмиране (LPP), чиито решения приемат само цели числа.

ПРЗ: формулировка, класификация

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

Общо ЗЛП е проблем на формата

под ограничения

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

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

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

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

PAP: примери

Проблем със сместа

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

Проблем с разпределението на ресурсите

Фирмата произвежда нразлични продукти, производството на които изисква мразлични видове ресурси. Запасите от използвани ресурси са ограничени и възлизат на респ b 1, б 2,…, b m c.u. Освен това са известни технологичните коефициенти a ij, които показват колко единици аз-тият ресурс е необходим за производството на една единица продукт й-ти тип (). Печалбата, която предприятието получава при продажба на продукт й-ти вид, възлиза на c jпарични единици Необходимо е да се състави план за производство на продукти, чиято печалба на предприятието по време на изпълнението ще бъде най-голяма.

Проблемите, свързани със смеси и разпределение на ресурси, често се записват в таблична форма.

Ресурси потребности Резерви
Б 1 … Bn
A 1 b 1
… …
Am b m
печалба c 1 … c n

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

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

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

За яснота и лесно възприемане състоянието на транспортния проблем обикновено се записва в следната таблица:

Като цяло решаването на транспортен проблем се извършва на няколко етапа:

  • I етап: изграждане на първоначален опорен план;
  • II етап: проверка на референтния план за оптималност;
  • Етап III: изясняване на референтния план, ако той не е оптимален.

Има няколко метода за получаване на първоначалния референтен план, например методът на северозападния ъгъл, методът на Vogel и методът на минималните разходи.

Планът се проверява за оптималност с помощта на потенциалния метод:

- за заети клетки,
- за незаети клетки.

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

Заключение

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

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

Ето няколко учебника за изучаване на методите за оптимално решение:

  1. Банди Б. Основи на линейното програмиране: Прев. от английски – М.: Радио и съобщения, 1989. – 176 с.
  2. Кремер Н.Ш. Изследване на операциите в икономиката: Proc. ръководство за университети / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Изд. проф. Н.Ш. Кремер. – М.: ЕДИНСТВО, 2005. – 407 с.

Решение на персонализирани методи за оптимизация

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

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

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

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

(1)
(2)
(3)

Метод на изкуствена основа

Както е показано по-горе, за проблем, написан в канонична форма, ако сред колонните вектори на матрицата АИма мединица и линейно независими, можете директно да посочите референтния план. Въпреки това, за много проблеми с линейно програмиране, написани в канонична форма и имащи референтни планове, сред колонните вектори на матрицата Ане винаги на разположение мединица и линейно независима. Помислете за следния проблем:

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

при условия

къде са първите нелементи са нула. Променливи се наричат ​​изкуствени. Векторни колони

(28)

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

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

Теорема 4. Ако в оптималния план разширен проблем (24)-(26) стойности на изкуствени променливи , Че е оптималният план за задача (21)−(23).

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

Стойността на целевата функция за референтния план (27):

Забелязваме това F(X)и се състои от две независими части, едната от които зависи от М, а другото - не.

След изчисление F(X)и техните стойности, както и началните данни на разширената задача, се въвеждат в симплексна таблица, както е показано по-горе. Единствената разлика е, че тази таблица съдържа един ред повече от обикновената симплексна таблица. По същото време в ( м+1)-ият ред съдържа коефициенти, които не съдържат М, и в ( м+2)ти ред − коефициенти за М.

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

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

м+2 реда, колони х 0 е отрицателно, тогава първоначалният проблем няма решение.

Ако не всички изкуствени променливи се изключват от основата и елемента м+2 реда, колони х 0 е равно на нула, тогава референтният план на първоначалната задача е изроден и базисът съдържа поне един от векторите на изкуствения базис.

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

Ако по време на итерации мРедът +2 вече не съдържа отрицателни елементи, след което процесът на итерация продължава с м+1 ред, докато се намери оптималният план за разширения проблем или се разкрие неразрешимостта на проблема.

По този начин процесът на намиране на решение на задачата за линейно програмиране (21)-(23) с помощта на метода на изкуствената основа включва следните основни етапи:

  • Съставете разширената задача (24)−(26).
  • Намерете опорния план на разширената задача.
  • Използвайки симплексния метод, изкуствените вектори се изключват от основата. В резултат на това се намира референтният план на първоначалния проблем или се записва неговата неразрешимост.
  • Използвайки намерения референтен план на ZLP (21)-(23), те или намират оптималния план на първоначалния проблем, или установяват неговата неразрешимост.

За да решавате проблеми с линейното програмиране онлайн, използвайте калкулатор

Общата задача за линейно програмиране (GLP) се формулира по следния начин - намерете проблемните променливи х 1 , х 2 , ..., х n , които осигуряват екстремума на целевата функция

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

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

Каноничният проблем с линейно програмиране (CLP) има формата

(1.2)

Различава се от OZLP по това, че неговата система от ограничения е система само от уравнения и всички променливи са неотрицателни.

Привеждане на OPLP в каноничната форма на OPLP:

За да замените първоначалния проблем за минимизиране с проблем за максимизиране (или обратното, проблем за максимизиране с проблем за минимизиране), достатъчно е да умножите целевата функция по „-1“ и да потърсите максимума (минимума) на получената функция;

Ако има неравенства сред ограниченията, тогава чрез въвеждане на допълнителни неотрицателни променливи х n +1 ≥ 0 те се трансформират в равенства:

неравенство ааз 1 х 1 +…+ав х n ≥ b i се заменя с равенство ааз 1 х 1 +…+ав х n+ х n +1 = bаз,

неравенство ааз 1 х 1 +…+ав х n ≤ b i се заменя с равенство ааз 1 х 1 +…+ав х n+ х n +1 = b i;

Ако някаква променлива х к няма ограничения за знаци, тогава се заменя (в целевата функция и във всички ограничения) от разликата между две нови неотрицателни променливи: х к = х" к – х” к , Където х" к ≥ 0. х” к ≥ 0.

Графичен метод за решаване на ЗЛП с две неизвестни

ZLP с две неизвестни има формата:

Методът се основава на възможността за графично изобразяване на областта от възможни решения и намиране на оптималното решение сред тях.

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

Област на решение на неравенството ааз 1 х 1 +ааз 2 х 2 ≤ b i е една от двете полуравнини, върху които правата ааз 1 х 1 +ааз 2 х 2 = b i, съответстващ на това неравенство, разделя координатната равнина. За да определите коя от двете полуравнини е областта на решението, достатъчно е да замените координатите на всяка точка, която не лежи на разделителната линия, в неравенството:

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

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

За намиране на оптималното сред възможните решения се използват нивелирни линии.

Линията на ниво е права линия с 1 х 1 +с 2 х 2 = л, Където л= const, при което целевата функция на задачата приема постоянна стойност. Всички линии на ниво са успоредни една на друга.

Градиент на целта функция град З(х) определя нормалния вектор ° С = (° С 1 , ° С 2) линии на ниво. Целевата функция на линиите на нивото нараства, ако линиите на нивото се преместят в посока на тяхната нормала, и намалява в обратна посока.

Базовата линия е линия на ниво, която има поне една обща точка с ODR и по отношение на която ODR се намира в една от полуравнините. ODD на проблема има не повече от две поддържащи линии.

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

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

    Изградете ODR.

    Конструирайте нормален вектор ° С = (° С 1 , ° С 2) и линия на ниво с 1 х 1 +с 2 х 2 = 0, минаваща през началото и перпендикулярна на вектора СЪС.

    Преместете линията на нивото до референтната линия по посока на вектора СЪСв макс проблем, или в обратна посока – в мин проблем.

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

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

    Изчислете стойността на целевата функция в точката на екстремума.

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

Симплексният метод се основава на следните разпоредби:

ODP на задача за линейно програмиране е изпъкнало множество с краен брой ъглови точки;

Оптималното решение на ZLP е една от ъгловите точки на ODR. Ъгловите точки на ODR алгебрично представляват някои основни (референтни) решения на системата от ограничения на ZLP.

Базовото (референтно) решение на ЗЛП е такова допустимо решение х 0 =(х 10 , х 20 , ..., х m 0 , 0,…0), за които векторите на условията (колони от коефициенти за неизвестни ограничения в системата) са линейно независими.

Ненулеви координати х 10 , х 20 , ..., х m 0 разтвори х 0 се наричат ​​базисни променливи, а останалите координати на решението х 0 - свободни променливи. Броят на ненулевите координати на референтното решение не може да бъде по-голям от ранга rсистеми от ограничения на PLP (брой линейно независими уравнения в системата от ограничения на PLP). След това приемаме, че системата от PLP ограничения се състои от линейно независими уравнения, т.е. r = м.

Смисълът на симплексния метод е целенасочен преход от едно референтно решение на PLP към друго (т.е. от една ъглова точка на ODP към друга) в посока на екстремума и се състои от последователност от етапи:

Намерете първоначалното решение за поддръжка;

Направете преход от едно референтно решение към друго;

Определете критерия за постигане на оптимално решение или направете заключение за липсата на решение.

Алгоритъм за изпълнениеСимплексен метод ZLP

Алгоритъмът на симплексния метод преминава от едно референтно решение на PLP към друго в посока на екстремума на целевата функция.

Нека ZLP е дадено в каноничната форма (1.2) и условието е изпълнено

b i ≥ 0, аз=1,2,…,м, (1.3)

съотношението (1.3) винаги може да бъде изпълнено чрез умножаване на съответното уравнение по „-1“ в случай на отрицателно bаз Ние също вярваме, че системата от уравнения в ограниченията на задача (1.2) е линейно независима и има ранг r = м. В този случай векторът на опорното решение има мненулеви координати.

Нека първоначалният проблем (1.2), (1.3) бъде намален до формата, където основните променливи х 1 , х 2 , ..., х m са изразени чрез свободни променливи х м + 1 , х м + 2 , ..., хн

(1.4)

Въз основа на тези отношения ще изградим таблица 1

Маса 1.

Таблица 1 се нарича симплексна таблица. Всички по-нататъшни трансформации са свързани с промени в съдържанието на тази таблица.

Алгоритъм скомплексен метод:

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

2. Изчислете отношението на свободните членове към положителните елементи на разделителната колона (симплексно съотношение). Намерете най-малката от тези симплексни релации; тя съответства на разделителния низ.

3. В пресечната точка на разрешаващия ред и разрешаващата колона има разделящ елемент.

4. Ако има няколко симплексни релации с еднакъв размер, тогава изберете някоя от тях. Същото важи и за положителните елементи на последния ред на симплексната таблица.

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

таблица 2

6. Елементът от таблица 2, съответстващ на разделящия елемент от таблица 1, е равен на реципрочната стойност на разделящия елемент.

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

8. Елементите на колоната на таблица 2, съответстващи на елементите на разделителната колона на таблица 1, се получават чрез разделяне на съответните елементи на таблица 1 на разделящия елемент и се вземат с обратен знак.

9. Останалите елементи се изчисляват по правоъгълно правило: Начертаваме мислено правоъгълник в таблица 1, единият връх на който съвпада с разрешаващия елемент (Re), а другият с елемента, който търсим; Нека означим елемента в новата таблица 2 с (Ne), а елемента на същото място в старата таблица 1 с (Se). Останалите два върха A и B допълват фигурата до правоъгълник. Тогава търсеният елемент He от таблица 2 е равен на He = Se – A*B/Re.

10. Критерий за оптималност. Щом се получи таблица, в която всички елементи на последния ред в задачата min са отрицателни (в задачата max всички елементи са положителни), се счита, че екстремумът е намерен. Оптималната стойност на целевата функция е равна на свободния член в реда Z, а оптималното решение се определя от свободните членове на базисните променливи. Всички свободни променливи са зададени на нула.

11.Ако всички елементи в колоната за резолюция са отрицателни, тогава проблемът няма решения (минимумът не е постигнат).

Метод на изкуствена основа за решаване на ЗЛП

Алгоритъмът на симплексния метод е приложим, ако е избрано всяко референтно решение на PLP, т.е. оригиналният PLP (1.2) се редуцира до формата (1.4). Методът на изкуствената основа предлага процедура за конструиране на такова еталонно решение.

Методът на изкуствената основа се основава на въвеждането на променливи на изкуствена основа г 1 , г 2 ,…, г m, с помощта на които системата за ограничения на PLP (2.2)

(1.5)

може да се преобразува във формата

(1.6)

Системите (1.5) и (1.6) ще бъдат еквивалентни, ако всички г аз ще бъде равно на нула. Както и преди, ние вярваме, че всичко b аз ≥ 0. За да при аз бяха равни на 0, трябва да преобразуваме проблема така, че всички променливи на изкуствена основа г аз премина към свободни променливи. Такъв преход може да бъде направен с помощта на алгоритъма на симплексния метод по отношение на допълнителна целева функция

Е(г) = г 1 + г 2 + ... + г m = д 0 – (д 1 х 1 +д 2 х 2 +…+дн хн). (2,7)

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

Първо, симплексната таблица се трансформира по отношение на целевата функция Е(г), докато се получи референтен разтвор. Еталонното решение се намира, когато е изпълнен следният критерий: Е(г) = 0 и всички изкуствени променливи при аз преведени в свободни променливи. След това се задрасква ред от симплексната таблица за Е(г) и колони за при аз и решаване на проблема за първоначалната целева функция З(х), докато се получи оптималното решение.

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

По този начин общата задача за линейно програмиране (GLP) може да бъде формулирана по следния начин.

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

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

Както е известно, подредена колекция от стойности нпроменливи , , … се представя от точка в n-мерното пространство. По-нататък ще обозначим тази точка х=( , , … ).

В матрична форма проблемът с линейното програмиране може да се формулира по следния начин:

, А– матрица на размера,

Точка х=( , , … ), отговарящ на всички условия, се извиква валидна точка . Множеството от всички допустими точки се нарича валидна площ .

Оптимално решение (оптимален план)проблем с линейно програмиране се нарича решение х=( , , … ), принадлежащи към допустимата област и за които линейната функция Qприема оптималната (максимална или минимална) стойност.

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

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

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

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

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

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

Базово решение на системата млинейни уравнения с n променливи е решение, в което всички н-мнеосновните променливи са нула. В задачите на линейното програмиране такива решения се наричат допустими принципни решения (опорни планове).

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


Важно следствие следва от горните теореми:

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

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