Въведение

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

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

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

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

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

Съдържание

  1. Какво е линейно програмиране?
    • Основни терминологии
    • Процесът за дефиниране на LP проблем
  2. Решаване на линейна програма по графичен метод
  3. Решаване на линейна програма с помощта на R
  4. Решаване на линейна програма с помощта на OpenSolver
  5. Симплекс метод
  6. Метод на северозападния ъгъл и метод на най-ниските разходи
  7. Приложения на линейното програмиране

1. Какво е линейно програмиране?

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

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

Пример за задача за линейно програмиране

Да приемем, че доставчикът на FedEx има 6 пакета за доставка на ден. Складът се намира в точка А. 6-те дестинации за доставка са дадени от U, V, W, X, Y и Z. Цифрите на линиите показват разстоянието между градовете. За да спести гориво и време, доставчикът иска да поеме по най-краткия път.

приложения

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

В този случай целта на доставчика е да достави колета навреме на всички 6 дестинации. Процесът на избор на най-добрия маршрут се нарича Operation Research. Оперативното изследване е подход към вземането на решения, който включва набор от методи за управление на системата. В горния пример моята система беше моделът за доставка.

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

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

Формулиране на проблем - Нека произведем няколко шоколада

Пример: Помислете за компания за производство на шоколад, която произвежда само два вида шоколад - А и В. И двата шоколада изискват само мляко и шоколад. За производството на всяка единица от А и В са необходими следните количества:

  • Всяка единица A изисква 1 единица мляко и 3 единици Choco
  • Всяка единица В изисква 1 единица мляко и 2 единици шоколад

Фирмената кухня има общо 5 единици мляко и 12 единици шоколад. При всяка продажба компанията печели от

  • Rs 6 за продадена единица A
  • Rs 5 за продадена единица B.

Сега компанията иска да увеличи печалбата си. Колко единици от А и В трябва да произведе съответно?

Решение: Първото нещо, което ще направя, е да представя проблема в таблична форма за по-добро разбиране.

Мляко Choco Печалба на единица
A 1 3 Rs 6
Б. 1 2 Rs 5
Обща сума 5 12

Нека общият брой единици, произведени от A, е = X

Нека общият брой единици, произведени от B, е = Y

Сега общата печалба се представя чрез Z

Общата печалба, която фирмата реализира, се дава чрез общия брой произведени единици A и B, умножен по нейната печалба за единица от Rs 6 и Rs 5 съответно.

Печалба: Max Z = 6X + 5Y

което означава, че трябва да максимизираме Z.

Компанията ще се опита да произведе толкова единици от A и B, за да увеличи печалбата. Но ресурсите Milk и Choco са на разположение в ограничен брой.

Съгласно горната таблица, всяка единица от A и B изисква 1 единица мляко. Общото количество налично мляко е 5 единици. Да представим това математически,

X + Y ≤ 5

Също така, всяка единица от A и B изисква съответно 3 единици и 2 единици Choco. Общото количество Choco на разположение е 12 единици. Да представим това математически,

3X + 2Y ≤ 12

Също така стойностите за единици от A могат да бъдат само цели числа.

Така че имаме още две ограничения, X ≥ 0 и Y ≥ 0

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

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

Общи терминологии, използвани в линейното програмиране

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

  • Променливи на решението: Променливите за решение са променливите, които ще решат резултата ми. Те представляват моето крайно решение. За да разрешим всеки проблем, първо трябва да идентифицираме променливите на решението. За горния пример общият брой единици за A и B, обозначени съответно с X & Y, са променливите на моето решение.
  • Целева функция: Определя се като цел на вземане на решения. В горния пример компанията иска да увеличи общата печалба, представена от Z. Така че печалбата е моята целева функция.
  • Ограничения: Ограниченията са ограниченията или ограниченията на променливите за вземане на решение. Те обикновено ограничават стойността на променливите за вземане на решение. В горния пример ограничението за достъпност на ресурси Milk и Choco са моите ограничения.
  • Ограничение за отрицание: За всички линейни програми променливите за вземане на решения винаги трябва да приемат неотрицателни стойности. Това означава, че стойностите за променливите на решението трябва да са по-големи или равни на 0.

Процесът за формулиране на проблем с линейно програмиране

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

  1. Идентифицирайте променливите за вземане на решение
  2. Напишете целевата функция
  3. Споменете ограниченията
  4. Изрично посочете ограничението за отрицание

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

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

2. Решаване на линейни програми по графичен метод

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

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

Нека разберем това с помощта на пример.

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

Разнообразие Разходи (цена/хек) Нетна печалба (цена/хец) Човекодни/Hec
Пшеница 100 50 10
Ечемик 200 120 30

Фермерът има бюджет от 10 000 щатски долара и разполага с 1200 човекодни дни по време на хоризонта на планиране. Намерете оптималното решение и оптималната стойност.

Решение: За да разрешим този проблем, първо ще формулираме нашата линейна програма.

Формулиране на линеен проблем

Стъпка 1: Идентифицирайте променливите за вземане на решение

Общата площ за отглеждане на пшеница = X (в хектари)

Общата площ за отглеждане на ечемик = Y (в хектари)

X и Y са моите променливи за решение.

Стъпка 2: Напишете целевата функция

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

Нашата целева функция (дадена от Z) е, Макс Z = 50X + 120Y

Стъпка 3: Писане на ограниченията

1. Дадено е, че фермерът има общ бюджет от 10 000 щатски долара. Разходите за производство на пшеница и ечемик на хектар също ни се дават. Имаме горна граница на общите разходи, похарчени от фермера. Така че нашето уравнение става:

100X + 200Y ≤ 10 000

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

10X + 30Y ≤ 1200

3. Третото ограничение е общата площ, налична за насаждение. Общата налична площ е 110 хектара. Така уравнението става,

X + Y ≤ 110

Стъпка 4: Ограничението за отрицание

Стойностите на X и Y ще бъдат по-големи или равни на 0. Това се подразбира.

X ≥ 0, Y ≥ 0

Ние сме формулирали нашата линейна програма. Време е да го решим.

Решаване на LP чрез графичен метод

Тъй като знаем, че X, Y ≥ 0. Ще разгледаме само първия квадрант.

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

100X + 200Y ≤ 10000 може да бъде опростено до X + 2Y ≤ 100 чрез разделяне на 100.

10X + 30Y ≤ 1200 може да бъде опростено до X + 3Y ≤ 120 чрез разделяне на 10.

Третото уравнение е в опростената си форма, X + Y ≤ 110.

Начертайте първите 2 реда на графика в първия квадрант (както е показано по-долу)

Оптималното осъществимо решение се постига в точката на пресичане, където са активни ограниченията на бюджета и човеко-дните. Това означава, че точката, в която се пресичат уравненията X + 2Y ≤ 100 и X + 3Y ≤ 120, ни дава оптималното решение.

Стойностите за X и Y, което дава оптималното решение, са при (60,20).

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

Максималната печалба, която компанията ще спечели, е,

Макс Z = 50 * (60) + 120 * (20)

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

3. Решаване на линейна програма с помощта на R

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

Пример: Организация за производство на играчки произвежда два вида играчки A и B. И двете играчки се продават съответно на Rs.25 и Rs.20. Всеки ден има 2000 налични ресурсни единици, от които играчката А изисква 20 единици, докато играчка Б изисква 12 единици. И двете играчки изискват време за производство от 5 минути. Общото работно време е 9 часа на ден. Какво трябва да бъде производственото количество за всяка от тръбите, за да се максимизират печалбите?

Целевата функция е:
Макс. Z = 25x + 20y

където x са единиците на тръба A

y са единиците на тръба B

Ограничения:
20x + 12y опции-> добавки-> изберете решаване-> кликнете върху управление-> изберете решаване-> щракнете върху Ok. Сега вашият решател е добавен в Excel. Можете да го проверите в раздела Данни.

Първото нещо, което ще направя, е да въведа данните си в Excel. След въвеждане на данните в Excel, изчислих общата сума C3: F3. По същия начин и за другите. Това се прави, за да се вземе общото търсене от Silo 1 и други.

След това ще разбия модела си на две. Първата таблица ми дава доставените единици, а втората таблица ми дава себестойността.

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

Сега ще използвам Solver за изчисляване на моя модел. Подобно на горния метод. Добавете целевата функция, променливи клетки, ограничения.

Сега вашият модел е готов за решаване. Кликнете върху решаване и ще получите оптималните си разходи. Минималните разходи за транспорт са $ 435.

7. Приложения на линейно програмиране

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

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

Крайни бележки

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

Обясних всяка концепция с пример от реалния живот. Искам да ги изпробвате в края си и да получите практически опит. Кажи ми какво мислиш!