ЛИНЕЙНО ПРОГРАМИРАНЕ: ЗА КАКВО Е, МОДЕЛИ, ОГРАНИЧЕНИЯ, ПРИЛОЖЕНИЯ - МАТЕМАТИКА - 2025

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

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

Фигура 1. Линейното програмиране се използва широко за оптимизиране на печалбите. Източник: Piqsels.

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

Z = k ₁ x + k ₂ y

С k ₁ и k ₂ константа. Тази функция е известна като обективна функция. Разбира се, има ситуации, които заслужават повече от две променливи за изследване, които са по-сложни:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

И ограниченията са математически моделирани от система от уравнения или неравенства, еднакво линейни в x и y.

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

Линейното програмиране е разработено независимо от американския физик и математик Джордж Данциг (1914-2005) и руския математик и икономист Леонид Канторович (1912-1986), малко след Втората световна война.

Методът за решаване на проблеми, известен като симплексния метод, е създаването на Данциг, който е работил за ВВС на САЩ, университета в Беркли и университета в Станфорд.

Фигура 2. Математиците Джордж Данциг (вляво) и Леонид Канторович (вдясно). Източник: Ф. Сапата.

Модели на линейно програмиране

Елементите, необходими за създаване на линеен модел на програмиране, подходящ за практическа ситуация, са:

-Обективна функция

-Променливи за определяне

-Restrictions

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

В математически план тази функция може да бъде изразена съкратено с помощта на обобщението за сумиране:

Z = ∑k _i x _i

В това уравнение k _i са коефициенти, а x _i са променливите на решението.

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

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

Видове ограничения

Можете да имате число M ограничения, като се започне от j = 1 до j = M. Математически ограниченията са от три типа:

1. A _j = ∑ a _ij. x _i
2. B _j ≥ ∑ b _ij. x _i
3. C _j ≤ ∑ c _ij. x _i

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

Двете останали ограничения са линейни неравенства и това означава, че известните стойности B _j и C _j могат да се спазват или надвишават, когато символът, който се появява, е ≥ (по-голям или равен на) или се спазва или не надвишава, ако символът е ≤ (по-малко или равно на).

Пример за модел

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

Местната сладкарница е известна с два специалитета: черна горска торта и торта жертва.

При приготвянето им те изискват яйца и захар. За черната гора ви трябват 9 яйца и 500 г захар, докато за сарпантина са ви нужни 8 яйца и 800 г захар. Съответните продажни цени са 8 и 10 долара.

Проблемът е: Колко торти от всеки вид трябва да направи пекарната, за да увеличи максимално печалбата си, като знае, че има 10 килограма захар и 144 яйца?

Променливи на решение

Променливите на решението са "x" и "y", които приемат реални стойности:

-x: броят на черните горски питки

-y: торти от тип жертва.

Ограничения

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

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

1. x ≥ 0
2. и ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Ограничения 1 и 2 съставляват условието за неотрицателност, изложена по-рано, и всички повдигнати неравенства са линейни. В ограничения 3 и 4 са стойностите, които не трябва да се надвишават: 144 яйца и 10 кг захар.

Обективна функция

И накрая, обективната функция е печалбата, получена при производството на "х" количество черни горски питки плюс "у" количество сарпантини. Той се изгражда чрез умножаване на цената по количеството на направените торти и добавяне за всеки вид. Това е линейна функция, която ще наречем G (x, y):

G = 8x + 10y

Методи за решение

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

- Графичен или геометричен метод

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

Фигура 3. Изпълнима област, в която се намира решението на оптимизационния проблем. Източник: Wikimedia Commons.

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

В случая на пекарната, която иска да оптимизира печалбите, ограниченията са:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

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

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

Фигура 4. Възможният регион на проблема със сладкишите. Линията с печалба 0 пресича началото. Източник: Ф. Сапата с Геогебра.

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

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

С тази линия получаваме всички двойки (x, y), които осигуряват дадено усилване G, така че има семейство от линии според стойността на G, но всички със същия наклон -k ₁ / k ₂, така че те са паралелни линии.

Оптималното решение

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

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

За нашия сладкиш кандидатските върхове са A, B и C.

- симплексния метод на Данциг

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

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

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

Приложения

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

Ето някои полета:

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

-За възлагане на адекватни задачи на персонала на фирма или фабрика или графици към тях.

-В подбора на най-хранителната храна и с най-ниски разходи в животновъдството и птицевъдството.

Решени упражнения

- Упражнение 1

Графично решаване на модела на линейно програмиране, повдигнат в предходните раздели.

Решение

Необходимо е да се графира набора от стойности, определени от системата от ограничения, посочени в проблема:

1. x ≥ 0
2. и ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Регионът, даден от неравенства 1 и 2, съответства на първия квадрант на декартовата равнина. Относно неравенствата 3 и 4, започваме с намирането на рестрикционните линии:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Възможният регион е четириъгълник, чиито върхове са точки A, B, C и D.

Минималната печалба е 0, следователно линия 8x + 10y = 0 е долната граница, а линиите за изобилие имат наклон -8/10 = - 0.8.

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

Фигура 5. Графично решение на упражнение 1, показващо възможна област и точка на разтвор С в една от върховете на споменатия регион. Източник: Ф. Сапата.

Това решение съответства на линия на наклон -0.8, която преминава през някоя от точките A, B или C, чиито координати са:

A (11; 5.625)

B (0; 12.5)

C (16, 0)

Оптимално решение

Изчисляваме стойността на G за всяка от тези точки:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

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

- Упражнение 2

Проверете резултата от предишното упражнение, като използвате функцията Solver, налична в повечето електронни таблици като Excel или LibreOffice Calc, които включват алгоритъма Simplex за оптимизация в линейното програмиране.

Решение

Фигура 6. Подробности за разтвора от упражнение 1 през електронната таблица Libre Office Calc. Източник: Ф. Сапата.

Фигура 7. Подробности за разтвора от упражнение 1 през електронната таблица Libre Office Calc. Източник: Ф. Сапата.

Препратки

1. Брилянтно. Линейно програмиране. Възстановено от: bril.org.
2. Епен, Г. 2000. Оперативни изследвания в административната наука. 5-ти. Edition. Prentice Hall.
3. Haeussler, E. 1992. Математика за управление и икономика. 2-ри. Edition. Grupo Редакция Iberoamericana.
4. Hiru.eus. Линейно програмиране. Възстановено от: hiru.eus.
5. Wikipedia. Линейно програмиране. Възстановени от: es. wikipedia.org.