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

от Българският сайт за математика

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

Общата задача на линейното програмиране се формулира математически така:

Да се намери оптималната (максималната или минимална) стойност на линейната функция $Z = c_1x_1 + c_2x_2 + ... + c_nx_n$ при следните ограничителни условия:

За да бъде системата от ограничителни условия съвместима, приемаме $m \le n$ . Ако това е нарушено, то определен брой уравнения могат да се отделят и останалите образуват линейно независима система.

Всички коефициенти $k_1, k_2, k_3,..., k_m$ трябва да са неотрицателни числа. Ако някое $k_t$ е отрицателно, то с умножаване на двете страни на уравнението с (-1) правим $k_t$ неотрицателно.

В системата от ограничителни условия едно или няколко условия могат да бъдат зададени като неравенства ( $\le$ или $\ge$ ). Но и в този случай чрез прибавяне или изваждане на фиктивни променливи те се превръщат в уравнения и системата приема КАНОНИЧЕН ВИД.

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

Да се намери оптимума на функцията: $Z = c_1x_1 + c_2x_2$ при условия:

Линейната функция обикновено е нарича ЦЕЛЕВА (ще приемем в изложението по-нататък това наименование). Целевата функция геометрически се представя чрез права, т. нар. ОПОРНА права, а системата от ограничителни условия се представя с изпъкнал многоъгълник.

Оптимумите на целевата функция се получават в точките, в които опорната права при успоредното си пренасяне има за първи или последен път обща точка с многоъгълника. В нашия общ случай това са точките $P_1$ и $P_2$ . В точката $P_1$ функцията има минимум, който се намира като заместим в целевата функция неизвестните с координатите на $P_1$ , а в точката $P_2$ - максимум.

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

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

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

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

Терминът "линейно програмиране" е от около 40-те години на XX век, но задача от линейно програмиране е била обобщена доста по-рано от Жан Батист Фурие. Добре е да се съобщи как се е родила тази първа по рода си задача.

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

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

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

След това може да се разгледа следната задача:

1. За производство на два вида продукция $P_1$ и $P_2$ са необходими четири вида суровини $C_1, C_2, C_3$ и $C_4$ , чийто запаси са ограничени. Количеството материал, необходим от всяка суровина за производството на всяка от продукциите, както и производствените цени на продукциите, са дадени в таблицата:

 Суровини               Запаси
            2       3       19
            2       1       13
            0       3       15
            3       0       18
   Цена        7       5

Какво количество от всяка продукция трябва да се произведе, за да бъде печалбата максимална?

Решение: Нека означим количеството от първата продукция $P_1$ с $x_1$ , а с $x_2$ от продулцията $P_2$ . При това означаване печалбата ще бъде: Z.

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

Математическият модел на задачата е:

Да се намери максимума на функцията $Z = 7x_1 + 5x_2$ при ограничителни условия, зададени от горната система.

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

Опорната права при успоредното пренасяне има за последен път обща точка с многоъгълника точка P (5, 3), следователно целевата фунцкия Z има максимум в тази точка.

$Z_{max} = 7.5 + 5.3 = 35 + 15 = 50$

От продукцията $P_1$ трябва да се произведе $x_1 = 5$ единици, а от $P_2 - x_2 = 3$ единици, като при тези количества печалбата ще бъде максимална.

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

Задачи:

1. Да се намери максимума на функцията: $Z = 4x_1 + 2x_2$ при следните условия:

2. Да се намери минимума на функция $Z = x_1 + 2x_2$ , ако:

3. Да се намери максимума на функцията $Z = x_1 + 3x_2$ , като се приведат към две променливи следните ограничителни условия:

Взето от „http://matematika.bg/wiki/%D0%9E%D0%B1%D1%89%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BD%D0%B0_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D1%82%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D0%BD%D0%B5_%D0%B8_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%B8_%D0%B7%D0%B0_%D1%80%D0%B5%D1%88%D0%B0%D0%B2%D0%B0%D0%BD%D0%B5%D1%82%D0%BE_%D0%B9“.

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

от Българският сайт за математика

Прегледи

Лични инструменти

Навигация

Търсене

Инструменти