Задача за линейно програмиране: методи за решаване и формиране

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

Характеристики на проблемите на линейното програмиране

Разграничават се следните характеристики на LP:

1. Оптимизация. Основата на линейното програмиране и оптимизационните задачи е максимизирането или минимизирането на някаква база данни, която е предмет на. Това е често срещано явление в икономиката, бизнеса, рекламата и много други области, които изискват ефективност, за да се пестят ресурси. Това включва въпроси, свързани с генерирането на печалба, придобиването на ресурси, времето за производство и други важни икономически показатели.
2. Линейност. Както подсказва името, всички задачи на LP имат характеристика на линейност. Понякога обаче тя е подвеждаща, тъй като линейността се отнася само за променливи от степен 1, като не включва мощни функции, квадратни корени и други нелинейни връзки. Това не означава, че функциите на задачата LP имат само една променлива. Той се отнася до променливите като координати на точки върху права линия, без да се включва кривина.
3. Функция на целта. В основата на задачите за линейно програмиране и формулирането на обективни задачи са променливи, които могат да се променят по желание, например време, прекарано в работа, произведени единици. Целевата функция се изписва с главна буква "Z".
4. Ограничения. Всички LP са ограничени до променливи в рамките на функцията. Тези ограничения са под формата на неравенства, например "b<3", където b може да представлява единици книги, написани от даден автор на месец. Тези неравенства определят начина, по който целевата функция може да бъде максимизирана/минимализирана, тъй като заедно те определят областите на вземане на решения.

Определяне на цел

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

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

1. Ограничения или ограничени ресурси, напр. ограничен брой служители, максимален брой клиенти или ограничение на производствените загуби.
2. Цел: Увеличаване на приходите или минимизиране на разходите.
3. Пропорционална линейност. Уравненията, които генерират променливите на решението, трябва да са линейни.
4. Хомогенност: характеристиките на променливите и ресурсите на решението са едни и същи. Например човешките часове са еднакво продуктивни или стоките, произведени от една машина, са идентични.
5. Делимост: продуктите и ресурсите могат да се представят като дроби.
6. Липса на отрицателност: решенията трябва да са положителни или равни на нула.

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

Това се представя чрез уравнение с променливо решение, където: X 1, X 2, X 3, ..., X n - променливи на решението; C 1, C 2, C 3, ..., C n - константи.

Всяко ограничение се изразява математически с някой от тези атрибути:

1. По-малко от или равно на (≤). Когато има горна граница, например извънредният труд не може да бъде повече от 2 часа на ден.
2. Равно (=). Посочва обвързваща връзка, например крайният запас е равен на началния запас плюс производството минус продажбите.
3. По-голямо от или равно на (≥). Например, когато е налице долна граница, производството на даден продукт трябва да бъде по-високо от прогнозираното търсене.
4. Общата формулировка на задачата за линейно програмиране започва със задаване на ограниченията.
5. Всяка LP-проблема трябва да има едно или повече ограничения.
6. Положителните променливи на решението трябва да се разглеждат в рамките на ограниченията.

Етапи на определяне на проблема

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

Стъпките на задаване на целочислена задача за линейно програмиране:

1. Определяне на число, което разкрива поведението на целевата функция за оптимизация.
2. Намерете набор от ограничения и ги изразете като линейни уравнения или неравенства. Така се създава област в n-мерното пространство на оптимизираните функции.
3. Необходимо е да се наложи условие за неотрицателност на променливите на задачата, т.е. всички те трябва да са положителни.
4. Изразете функцията под формата на линейно уравнение.
5. Оптимизиране на функция по графичен или математически начин при решаване на задача за линейно програмиране.

Графичен начин

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

Стандартната задача за максимизиране на неизвестните на задача LP, в която функцията е нарастваща, подлежи на ограничения от вида

x ≥ 0, y ≥ 0, z ≥ 0 и допълнителни ограничения от вида:

Ax + By + C z +. , ≤ N,

където A, B, C и N са неотрицателни числа.

Неравенството трябва да е "≤", а не "=" или "≥".

Графичният метод на LP с две неизвестни е следният:

1. Определяне на възможните области на графиката.
2. Изчисляване на ъгловите координати на точките.
3. Извадете ги, за да видите оптималната стойност. Тази точка дава решението на LP.
4. Минимизиране на функция и ако коефициентите ѝ са неотрицателни, съществува решение.

Идентифициране на съществуващи решения:

1. Ограничете областта, като добавите вертикална линия вдясно от най-дясната ъглова точка и хоризонтална линия над най-високата ъглова точка.
2. Изчисляване на новите координати на ъгловата точка.
3. Намиране на ъглова точка с оптимална стойност.
4. Ако това се случва в началната точка на неограничената област, тогава задачата за LP има решение в тази точка. Ако не, тя няма оптимално решение.

Скициране на набор от решения

Изберете референтна точка и маркирайте зоната, която ще бъде блокирана.

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

1. Начертайте линия, получена чрез замяна на неравенство с равенство.
2. Изберете контролната точка, (0,0). Добър избор, ако линията минава през началото.
3. Ако контролната точка удовлетворява неравенство, тогава множеството на решенията е цялата област от същата страна на линията, от която е контролната точка. В противен случай е от другата страна на линията.
4. Допустимата област се определя чрез набор от линейни неравенства и представлява набор от точки, които удовлетворяват всички неравенства.
5. За да я начертаете, определена от набор линейни неравенства с две променливи, изпълнете областите, представени от всяко неравенство, върху същата графика, като не забравяте да засенчите частите на равнината, които не са необходими.

Simplex метод за максимизиране

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

1. Конвертиране на данни в система от уравнения, въвеждане на слаби променливи, за да се превърнат ограниченията в уравнения, и пренаписване на функцията в стандартна форма.
2. Запишете първоначалната таблица.
3. Изберете колоната на спреда, отрицателното число с най-висока стойност в долния ред, с изключение на най-дясната позиция. колоната му е кумулативна. Ако има двама кандидати, изберете един. Ако всички числа в долния ред са нула или положителни, с изключение на най-дясната позиция, всичко е готово и базовото решение максимизира целевата функция.
4. Изберете лентата в колоната. Оста винаги трябва да е положително число. За всеки положителен запис "b" в колоната с обобщени данни изчислете съотношението "a/b", където "a" е отговорът в този ред. От тестовите коефициенти изберете минималния, след което съответното число "b" ще бъде оста.
5. Използвайте пръчка, за да изчистите колоната по обичайния начин, като се уверите, че спазвате точно предписанията за формулиране на операции върху редове, както е описано в насоките за Метод на Гаус-Жордан, и след това разменете колоната с етикета от колоната.
6. Променливата, която първоначално обозначава реда на обобщението, е изходящата променлива, а променливата, която обозначава колоната, е входящата променлива.

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

Нестандартни ограничения

За решаване на задача от тип LP с ограничения от вида (Ax + By +. , .≥ N) с положително N, извадете допълнителната променлива от лявата страна (вместо да добавяте слабата променлива). Основното решение, съответстващо на първоначалната таблица, няма да бъде изпълнимо, тъй като някои от активните променливи ще бъдат отрицателни. Поради това правилата за първоначалния оборот са различни от тези, посочени по-горе.

След това се маркират всички редове, които дават отрицателна стойност за свързаната активна променлива, с изключение на целевата променлива. Ако има отбелязани редове, трябва да започнете от етап I.

Етап I. Намерете най-голямото положително число в първия ред. Използвайте тестовите коефициенти, както в предишния раздел, за да намерите обобщението в тази колона и след това разширете този запис. Повторете, докато не останат маркирани редове, след което преминете към стъпка II.

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

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

Онлайн инструмент PHPSimplex

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

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

WanerMath: приложения без граници

Warneth предоставя 2 инструмента за решаване на задачи за линейно програмиране:

1. Графично линейно програмиране (две променливи).
2. Симплекс метод.

За разлика от други инструменти, които публикуват само коефициенти, тук са включени всички функции с променливи. Това представлява малка трудност за Начинаещи потребители, тъй като уебсайтът на профила има инструкции за употреба. Освен това сайтът разполага с функция "Примери", която автоматично създава задачи, така че потребителят да може да оцени нейната ефективност, например при задаване на задача за транспортно линейно програмиране.

JSimplex - друг онлайн инструмент. Тя ви позволява да решавате задачи за LP без ограничение на броя на променливите. Има прост интерфейс за управление, в който трябва да посочите цел и брой променливи. Потребителят записва коефициентите на целевата функция, ограниченията и щраква върху "реши". Интегриране, изчисляване на най-добрия вариант и резултати за всяка променлива ще бъдат показани.

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

Прост пример за LP

Компанията произвежда ръчни и научни калкулатори. Дългосрочните прогнози сочат, че се очаква ежедневно да са необходими 150 научни и 100 преносими калкулатора. Daily производствен капацитет Всеки ден можете да произвеждате не повече от 250 научни и 200 ръчни калкулатора.

Трябва да бъдат произведени минимум 250 калкулатора, за да се изпълни договорът за доставка. Реализацията на един от тях води до загуба от 20 рубли, но всеки ръчен калкулатор носи печалба от 50 рубли. Трябва да направите изчисление, за да получите максималната нетна печалба.

Алгоритъм за изпълнение на пример за задача на линейното програмиране:

1. Променливи решения. Тъй като е даден оптимален брой калкулатори, това ще бъдат променливите I в тази задача: x - брой научни калкулатори, y - брой ръчни калкулатори.
2. Задайте ограничение, тъй като компанията не може да произвежда отрицателен брой калкулатори на ден, естественото ограничение би било: x ≥ 0, y ≥ 0.
3. Долна граница: x ≥ 150, y ≥ 100.
4. Определете горна граница за тези променливи поради производствените ограничения на компанията: x ≤ 250, y ≤ 200.
5. Съвместно ограничение върху стойностите "x" и "y" поради минималната поръчка за превоз на товари: x + y ≥ 250
6. Оптимизиране на функцията на нетната печалба: P = -20x + 50y.
7. Решение на задачата: максимизирайте P = -20x + 50y, при условие че 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.

Приложения

Сред приложенията на линейното програмиране най-често срещаните са:

1. Кумулативно планиране на продажбите и операциите. Целта е да се сведат до минимум производствените разходи в краткосрочен план, например за три и шест месеца, като се задоволи очакваното търсене.
2. Продуктово планиране: намиране на оптималния набор от продукти, тъй като те изискват различни ресурси и имат различни разходи. Например, намерете оптималната смес от химични елементи за бензин, бои, храна за хора и храна за животни.
3. Производствен поток: определяне на оптималния поток за производството на продукт, който трябва да премине последователно през няколко работни потока, като всеки от тях има свои собствени разходи и производствени характеристики.
4. Задаване на задача за линейно програмиране в областта на транспорта, разписание. Методът се използва за програмиране на няколко маршрута на даден брой превозни средства за обслужване на клиенти или получаване на материали, които трябва да бъдат транспортирани между различни места. всяко превозно средство може да има различен капацитет и производителност.
5. Управление на запасите: определяне на оптималната комбинация от продукти, които трябва да се съхраняват в търговската мрежа.
6. Програмиране на персонала: създаване на план за работната сила, който позволява очакваното променливо търсене на умения да бъде задоволено с възможно най-малък брой служители.
7. Контрол на отпадъците: с помощта на линейно програмиране може да се изчисли как да се намалят отпадъците до минимум.

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