Математическо програмиране

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

4.1.

Математическо програмиране

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

44.1. Математическо програмиране

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

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

сх
одство.
З
атова е необходимо

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

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

Пример 2.

(Задача на домакинята). Семейство от 5 члена живее със скромната заплата на глава
та на семейството. Постоянна задача е опред
еляне на ежеседмичното меню след съответно разглеждане на потребностите, вкусовете на семейството и цената на продуктите. Мъжът трябва да получава дневно по 3000 калории, жената – 1500 (с диета за отслабване), а децата се нуждаят съответно от 3000, 2700 и 2500 калории дневно. Съгласно предписанието на домашния лекар тези калории трябва да бъдат получавани от всеки член на семейството в резултат на консумирането на ограничено отгоре количество мазнини и ограничено отдолу количество въглехидрати и белтъчини. В посочената диета имат голямо значение белтъчините. Освен това всеки член на семейството трябва да задоволи своите потребности и от витамини. Задачата се свежда до това, като се изхожда от цените на продуктите, да се състави седмично меню, минимизиращо издръжката.

Тази задача е типична задача на линейното програмиране: допустимите процеси се състоят в закупуването на различните видове продукти; ограниченията в задачата са потребностите на членовете на семейството от калории и витамини, а също и предписанието на лекаря за горната и долната граница количествата мазнини, белтъчини и въглехидрати, които могат да се консумират от всеки член на семейството. Броят на комбинациите за хранене, удовлетворяващи тези ограничения, е голям. Обаче някой от тези допустими планове са свързани с по-високи разходи, отколкото други. Задачата се състои в намирането на комбинация, която има минимална пълна стойност.
Пример 3. (Обучение в процеса на работа).
Промишлено предприятие сключва договор за произвеждане на определена продукция. Предприятието разполага с по-малко количество работна сила, о
тколкото е необходимо
з
а произвеждане на определената продукция
в размерите, предвидени от изработения план за някол
ко седмици напред. Във връзка с това е
необходимо да се наемат допълнително работници, да ги обучат и използват
в работата. Нал
ичната в предприятието работна
ППример 2. (Задача на домакинята). Семе
йство от 5 члена
живее със скромната заплата на главата на семейството. Постоянна задача е определяне на ежеседмичн
ото меню
след съответно разглеждане на потребностите, вкусовете на семейството и цената на продуктите. Мъжът трябва да получава дневно по 3000 калории, жената – 1500 (с диета за отслабване), а децата се нуждаят съответно от 3000, 2700 и 2500 калории дневно. Съгласно предписанието на домашния лекар тези калории трябва да бъдат получавани от всеки член на семейството в резултат на консумиране
то
на

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

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

4.4. Е
тапи при построяване на математическите модели

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

н
а
м
одел се
о
казва затруднено п
о
ради богатството,
р
ВВсяка задача на линейното програмиране може да бъде приведена към каноничен модел, където се минимизира (максимизира) целева функция с линейни ограничения от тип равенства. Тъй като броя на променливите
n
в за
д
ачите на линейното програм
иране е по-голям от броя на ограниченията m (n > m), то за получаване на начално решение (n-m) на брой променливи могат да се приравнят
на 0 (свободни променливи)
. Останалите m на брой променливи се наричат базисни и лесно могат да бъдат определени от системата ограничения от тип равенства. Ако решението