Математическо описание на модела на линейно програмиране. Форми на линейни математически модели и тяхното преобразуване. Общ вид на модела на линейното програмиране

1.

2. указания за употреба мат. модели в икономиката.

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

Използва се в математическата статистика, методите за оптимизация, икономическите методи. кибернетика, експериментални проблеми.

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

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

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

Математическото програмиране включва редица раздели, основните от които са следните:

1. Линейно програмиране.Този раздел включва задачи, в които неизвестни променливи са включени в математически зависимости на първа степен.

2. Нелинейно програмиране.Този раздел включва задачи, при които целевата функция и (или) ограниченията може да са нелинейни.

3. Динамично програмиране.Този раздел включва задачи, при които процесът на решаване може да бъде разделен на отделни етапи.

4. Целочислено програмиране.Този раздел включва задачи, в които неизвестните променливи могат да приемат само цели числа.

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

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

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

3. Концепцията за математически модел, видове мат. модели

Математически моделе абстракция на реално явление или процес, написана с математически символи и изрази. Математическите модели на икономическите процеси и явления се наричат ​​икономико-математически модели

Моделите са разделени на:

1. линеен, в който всички зависимости се описват с линейни отношения,

2. нелинейни, в които има нелинейни връзки;

3. стохастичен, които отчитат случайния характер на изследваните процеси,

4. детерминистичен, които отчитат средните стойности на всички параметри.

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

6. статичен, при което факторът време не е отчетен.

7. оптимизациямодели, при които изборът се прави в зависимост от екстремизациянякакъв критерий,

8. неоптимизация, в които няма критерий за оптималност.

9. макромодели(за цялото домакинство)

10. микромодели(отделни връзки или процеси на икономиката).

Видове математически модели: линейни, нелинейни, квадратични, целочислени, дискретни, параметрични, линейни дробни, динамични, стохастични

4. Обща постановка на проблемите на математическото програмиране.

Помислете за общата постановка на проблема с математическото програмиране.

Общият проблем на математическото програмиране е да се определи оптималната стойност на целевата функция, а стойностите на променливите трябва да принадлежат към определен диапазон от допустими стойности. Математическа дефиниция оптимално решениеизразява се в намиране на екстремума (max или min) на функция на много променливи

Z = f(x1, x2, …, xn)

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

gi (x1, x2,…, xn) Риби (i = 1, 2,…, m),

където Ri е един от знаците ≥, =, ≤.

5. Проблемът за оптимизиране на производствения план. Икономическа постановка и конструиране на математически модел на задачи.

Икономическа обстановка:

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

Математическа настройка:

Нека j е индексът на вида продукт j = 1, n

i - индекс на вида ресурс i = 1, m

и ij са разходите за суровини аз-ти вид за производство на единица продукция й-ти тип;

Аi е зададена граница на наличния обем ресурси от i-ти вид;

Pj - печалбата, получена от продажбата на единица продукция от j-ти вид;

xj е обемът на продукцията от j-тия вид.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → макс

a11x 1 + a12x 2 +...+ a1nx n ≤ A1

a21x 1 + a22x 2 +...+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +...+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Задачата на диетата. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа обстановка

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

Математическа настройка:

j е индексът на вида на захранването, j = 1, n

i – индекс на вида на хранителното вещество, i = 1, m

Аi е необходимият дневен прием на i-тия вид хранително вещество;

Сj е себестойността на единица фураж от j-тия вид.

Нека въведем неизвестни променливи:

хj - дневен обем на хранене на животните j-ти изгледкърма.

По отношение на въведената нотация дадена задачаще бъде написано следващо

a11x1 + a12x2 +...+ a1nxn ≥ A1

a21x1 + a22x2 +...+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +...+ и mnxn ≥Am

xj ≥ 0, j = 1, n

7. Транспортна задача . Икономическа постановка и изграждане на математически модел на проблема.

Икономическа обстановка :

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

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

Математическа настройка :

Нека въведем обозначенията на дадените параметри:

j – потребителски индекс, j = 1, n

i – индекс на доставчика, i = 1, m

Аi е наличният обем продукти от i-тия доставчик;

Bj - обемът на търсенето на продуктите на j-ия потребител;

Cij е единичната цена за транспортиране на единица продукт от i-тия доставчик до j-тия потребител.

Нека въведем неизвестни променливи:

хij е обемът на транспортиране на продукти от i-тия доставчик до j-тия потребител.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → мин

Ограничения на задачите.

I. От всеки доставчик можете да изтеглите продукти не повече от наличното количество:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Потребността на всеки потребител от продукти трябва да бъде задоволена

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Условие за неотрицателност: xij ≥0, i = 1, m ; j = 1, n

Често е удобно да напишете математическото твърдение в сгъната форма:

, i = 1, m , j = 1, n

8. Проблемът с избора на задачи или задачи. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа обстановка :

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

Математическа настройка .

Нека въведем обозначенията за дадените параметри.

i – индекс на произведенията, i = 1, m

j е индексът на изпълнителите, j = 1, n

Cij е разходът за изпълнение на i-тата работа от j-тия изпълнител.

Нека въведем неизвестни променливи. В този проблем неизвестните променливи могат да приемат само две стойности, 0 или 1. Такива променливи се наричат ​​нулеви променливи.

1 - ако j-тият изпълнител е назначен на i-та работа;

0 - в противен случай.

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

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min

I група ограничения.

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

x11 + x12 +...+ x1n = 1

x21 + x22 +...+ x2n = 1

……………………..

xn1 + xn2 +...+ xnn = 1

II. рестрикционна група.

Всеки изпълнител може да изпълнява само една работа:

x11 + x21 +...+ xn1 = 1

x12 + x22 +...+ xn2 = 1

……………………..

x1n + x2n +...+ xnn = 1

x ij = (0,1) i = 1, n; j = 1, n

9. Проблемът с рязането на материали. Икономическа постановка и изграждане на математически модел на проблема.

Икономическа обстановка .

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

Математическа настройка .

Нека въведем обозначението:

i е индексът на празните места,

Аi - необходимият брой заготовки от i-тия вид;

j - индекс на опциите за рязане,

Cj е размерът на отпадъците при разкрояване на единица изходен материал по вариант j;

и ij е броят на заготовките от i-тия вид при разкрояване на единица изходен материал по вариант j.

Нека въведем обозначението на неизвестните променливи.

xj е количеството суровина, нарязано по вариант j.

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

z \u003d С1x1 + С2x2 + ... + Сnxn → мин

a11x1 + a12x2 +...+ a1nxn = A1

a21x1 + a22x2 +...+ a2nxn = A2

…………………………….

am1x1 + am2x2 +...+ amnxn =Am

xj ≥ 0, j = 1, n

Използването на математически модели ви позволява да спестите до 20% от суровините.

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

На първия етап се изграждат опциите за рязане, в резултат на което стойностите на броя на опциите n, броя на заготовките от всеки тип, получени от различни опциирязане (aij), както и стойността на отпадъците (Cj).

Изграждането на опции за рязане на единица изходен материал се извършва под формата на следната таблица:

номер на опцията

Празно i1

i2 празен

празно im

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

10. Общ вид на проблемния модел на ЛП и неговите характеристики

Общата форма на LLP е:

z \u003d С1x1 + ... + Сnxn max (мин.)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

В общ вид всеки символ R1 , R2 ,…, Rm означава един от знаците: ≥, = или ≤ .

Общата форма на проблемния модел на ЛП има следните характеристики.

1. Системата от ограничения се представя под формата на уравнения (твърди условия) и неравенства (нетвърди условия).

2. Условията за неотрицателност не се налагат на всички променливи

3. Целевата функция клони или към максимума, или към минимума.

11. Стандартна форма на проблемния модел на ЛП и неговите характеристики

Стандартната форма е както следва.

Намерете максимума или минимума на целевата функция z:

z = С1x1 + … + Сnxn → max (min) (1)

Предмет на следните ограничения:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

Характеристиките на стандартната форма на проблемния модел на LP са следните:

1. системата от ограничения е представена под формата на неравенства (нетвърди условия)

2. на всички променливи се налагат условия за неотрицателност

3. целевата функция клони към max или min

12. Канонична форма на проблемния модел на ЛП и нейните характеристики

Каноничната форма е:

Намерете минимума на целевата функция z:

z = С1x1 + … + Сnxn → min

Предмет на следните ограничения:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Характеристиките на каноничната форма са следните:

1. Системата от ограничения е представена под формата на уравнения (строги условия).

2. Условията за неотрицателност се прилагат за всички променливи

3. Целевата функция се стреми към

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

13.Възможен, допустим, оптимален основен план на задачите, ОДЗ на задачата на ЛП

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

Определение 2.Наборът от всички планове за проблем с линейно програмиране се нарича домейн на допустимите стойности на променливите ( ОДЗ ).

Определение 3.Планът на задачата за линейно програмиране, в който целевата функция приема минималната (или максималната) стойност на ODZ, се нарича оптимален .

14. Видове записи на задачи за ЛП: разгънати, сгънати, матрични, векторни.

Проблемните модели на LP могат да бъдат написани в различни форми.

1. Разширен изглед на записа на модела

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Свит изглед:

,

Xj ≥ 0, j = 1, n.

3. Модел на задачата LP в матрична форма:

X ≥ 0

Където

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Модел на задачата LP във векторна форма:

Където

X1 a11 a12 a1n a1

X2, a21, a22, a2n, a2

… … … … …

Хn am1 am2 am2 am

15. Преход от стандартната и обща форма на проблемите на LP към каноничната.Теорема за връзка

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

1. Преобразуване на променливи. Ако някоя променлива Xk е неположителна (Xk ≤ 0), тогава се въвежда нова променлива Xk ", така че Xk " = –Xk . Очевидно Xk " ≥ 0. След това във всяко ограничение и целева функция променливата Xk се заменя с [ – Xk "].

Ако някаква променлива Xt може да приема всякакви стойности, тогава тя се заменя с разликата на две неотрицателни променливи Xt' и Xt'', т.е. приема се, че xt = Xt' – Xt'', където Xt' 0 ≥ и Xt'' ≥ 0.

2. Трансформация на ограничения.Ако някое от ограниченията в модела има формата на неравенство, то се преобразува в равенство чрез добавяне (ако неравенството е от тип ≤) или изваждане (ако неравенството е от тип ≥) от лявата му страна. Тези променливи се наричат ​​балансови променливи. Балансовите променливи са включени в целевата функция с нулеви коефициенти. Балансовата променлива приема стойността на индекса последователно след вече съществуващите. Ако, например, системата от ограничения има 5 променливи, тогава първата балансова променлива ще бъде X6, а втората - X7 и т.н.

16. Преход от каноничната форма на модела ZLP към стандарта

Да се ​​премине от каноничната форма към стандартната форма, всяка от

уравнения, които трябва да бъдат заменени със система от неравенства:

Друг начин е системата от уравнения да се приведе в специална форма и допълнително да се елиминират някои променливи.

Използвайки метода на Йордан-Гаус, ние избираме основната променлива във всяко уравнение. Такъв подбор се извършва с помощта на еквивалентни (елементарни) трансформации на Гаус. Те включват:

а) умножение на всяко уравнение с константа, различна от нула;

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

Удобно е да напишете първоначалната система от линейни уравнения преди трансформацията под формата на матрица или таблица:

Записваме проблема в стандартна форма.

17. Понятието хиперравнина на полуравнина, опорна хиперравнина.

18. Геометричен. интерпретация на системата от ограничения и целевата функция в задачите на ЛП

19. Изпъкнало множество: крайни (ъглови) точки на множеството. Изпъкнал многостен

ОпределениеМножество M се нарича изпъкнало, ако заедно с произволни две точки от даденото множество съдържа и отсечка, която ги свързва.

изпъкнал набор

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

Теорема 1. Всяка точка от сегмента може да бъде представена като изпъкнала комбинация от неговите ъглови точки.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 изпъкнала комбинация от точки на ъглови точки A и B

λ1 + λ2 = 1

Теорема 2. Всяка точка от изпъкнало затворено множество може да бъде представена като изпъкнала комбинация от неговите ъглови точки.

20. Алгоритъм на графичния метод за решаване на задачи на ЛП

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

2. Броят на неизвестните променливи се проверява. Ако това число е повече от три, тогава проблемът не може да бъде решен чрез графичен метод (има други ефективни методи за решаване на такива задачи).

3. Областта на допустимите стойности на променливите за ZLP е в процес на изграждане.

4. Изгражда се водещ вектор ° С .

5. Първоначалният изоцел се изчертава през ODZ (перпендикулярно на вектора на посоката).

6. Извършва се менталното движение на началния изокоел по посока на вектора ° С, ако се определи максималната стойност на целевата функция, или в обратна посока, ако се определи нейната минимална стойност, докато изоголът стане референция към ОДЗ. Пресечните точки на еталонния изокоел и ODZ ще бъдат оптималните точки на проблема.

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

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

20. графичен алгоритъм. LP метод за решаване на проблеми

Алгоритъм на графичния метод.

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

2. Насочващият вектор C се изгражда от коефициентите за променливите на целевата функция.

3. Първоначалният изокоел се изчертава перпендикулярно на вектора на посоката през началото.

4. Първоначалната изогола се премества мислено в посока на нарастващи стойности на вектора C, ако се определи максималната стойност на целевата функция, или в обратна посока, ако се определи нейната минимална стойност, докато изоголът стане a справка в ОДЗ. Пресечните точки на еталонния изокоел и ODZ ще бъдат оптималните точки на проблема.

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

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

23. теореми за обхвата на допустимите стойности на проблема с LP и за целевата функция

Теоремата на ODZ.Областта на допустимите решения на задачата LP е изпъкнало множество (затворено и ограничено в n-мерно пространство)

Теорема 2. За целевата функция на задача от линейно програмиране.

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

24. Теоремата за ъгловата точка. Достатъчни и необходимо условие

25. Следствия от теоремата за свойствата на решенията на задачи на ЛП и изводи. Концепцията за базова линия.

Следствия от теореми.

Определение. Планирайте = (х1,х2,…,хn), чиито положителни координати съответстват на линейно независими вектори, се нарича основен план PLP .

Следствие 1. Референтният план има не повече от m положителни координати.

Ако има точно m положителни координати, тогава такъв опорен дизайн се нарича неизроден, в противен случай изроден.

Следствие 2. Всяка ъглова точка на ODZ е референтен план.

27. Алгоритъм на симплексния метод.

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

1. Проверява се дали задачата LP е в канонична форма. Ако не, тогава е необходимо оригиналният модел да се преобразува в канонична форма.

2. Първоначалният референтен план и стойността на целевата функция са избрани за този референтен план.

3. Построена е началната симплексна таблица.

4. Проверяват се стойностите на оценките за оптималност в индексния ред. Ако няма положителни оценки, тогава оптималното решение се изписва и алгоритъмът приключва работата си. В противен случай точка 5 е изпълнена.

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

6. От основата се извлича вектор, който съответства на симплексното отношение, изчислено по формулата 0< Ө ≤ . Данная строка называется разрешающей строкой.

7. Изгражда се нова симплексна таблица. Колони B и C B се променят съответно.Останалата част от таблицата се попълва от предишната с помощта на трансформации на Гаус, като индексният ред се счита за m+1 реда и също се трансформира с помощта на трансформации на Гаус. Пристъпваме към изпълнението на параграф 4 от този алгоритъм.

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

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

29. Симплексни таблици, тяхното попълване. Формули за изчисляване на коефициентите на индексните редове.

30 . Теоремата за оптималност за плана на задача за линейно програмиране е следствие от теоремата за оценка на оптималността за решаване на задачи по симплексния метод.

Теорема 1: Ако за някакъв вектор Ā j в системата

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Отношението Z j – c j > 0 е изпълнено, тогава планът X B0 не е оптимален и е възможно да се премине към план X B1 така, че Z (X B1) ≤ Z (X B0).

Тук Z j = (С, Ā j) е скаларното произведение на векторите.

C е вектор, състоящ се от коефициенти при основните променливи на целевата функция Z

Ā j е вектор, състоящ се от коефициентите на разширение на съответния вектор по отношение на базисни вектори.

c j е коефициентът на целевата функция Z с променлива X j

Последица от теореми: Ако за всички вектори Ā 1 , Ā 2 , …, Ā n на някакъв референтен план Х отношението Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

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

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

31. Избор на вектор, влизащ в базиса и произлизащ от базиса. Симплексна релация.

За да преминете към нов референтен план, е необходим един от свободните вектори въведете в основата и изведете някои от базисните вектори. За въвеждане в основата избираме вектор, който има поне една положителна координата. Нека векторът A m+1 е такъв вектор.

разлагане -

респ. вектор, кат. ще бъде референтен план, ако неговите координати са неотрицателни, а броят на положителните координати ще бъде равен на m.

Координатите на вектора X1 трябва да са неотрицателни, т.е. .

Ако , тогава тази координата ще бъде неотрицателна.

Нека минимумът във връзка (5) се получи при i =1, тогава ако вземем

тогава първата координата на вектора 1 хще стане нула.

Релакция (6) се нарича симплексна релация. Така се преместихме от първоначалната базова линия 0 х(основни вектори A1, A2, ... Am) към референтния план 1 х(базисни вектори А2,А3,…,Аm, Am+1).

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

33. Четириъгълно правило за преизчисляване на симплексна таблица

34. Знак за уникалността на оптималния план, множеството от оптимални планове и отсъствието на оптимален план при решаване на проблема с ЛП по симплексния метод.

При решаване на задачи по симплексния метод са възможни следните видове оптимални решения:

1. Уникалност . Ако оценките на всички свободни вектори са строго отрицателни, тогава полученият опорен дизайн е оптимален и уникален. (вижте примера в предишния параграф).

2. Алтернативен оптимум (набор от оптимални решения).

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

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

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

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

35. Кога се използва методът на изкуствената основа?

изкуствени.

36. Построяване на М-проблема в метода на изкуствената основа

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

Трябва да се добави изкуствена променлива към целевата функция с много голямо положително число (тъй като целевата функция е да се намери минимумът). Това число се обозначава с латинската буква M. Може да се счита за равно на +∞. В тази връзка понякога методът на изкуствената основа се нарича М-метод. Такава трансформация на първоначалния проблем се нарича конструиране на разширения проблем. Ако решавате проблем с целева функция, за да намерите изкуствена променлива, трябва да добавите към целевата функция с много голямо положително число (тъй като целевата функция е да намерите минимума). Това число се обозначава с латинската буква M. Може да се счита за равно на +∞. В тази връзка понякога методът на изкуствената основа се нарича М-метод. Такава трансформация на първоначалния проблем се нарича конструиране на разширения проблем. Ако даден проблем се решава с целева функция за намиране на максимума, тогава изкуствените променливи влизат в целевата функция с коефициент -M.

Така в разширения проблем имаме базова линия (въпреки че някои от базовите променливи са изкуствени).

Изгражда се началната симплексна таблица.

37. изграждане на индексна линия при метода на изкуствената основа

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

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

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

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

39. Алгоритъм на дуалния симплекс метод

Алгоритъм на двойния симплекс метод:

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

2. Изберете водещата линия по най-големия абсолютен отрицателен елемент от колоната със свободни членове A0

3. Водещата колона се избира според най-малката абсолютна стойност на отношението на елементите на индексната линия към отрицателните елементи на водещата линия.

4. Преизчислете симплексната таблица според правилото за пълни елиминации на Йордан

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

6. Знак за получаване на оптимално решение чрез двойния симплексен метод е критерият за оптималност за обикновения симплексен метод.

41. Отворени и затворени транспортни модели. Преход от отворен транспортен модел към затворен.

Видове транспортни задачи.

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

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

(т.е. ако ∑ Ai = ∑ Bj), в противен случай транспортната задача се нарича отворен. За да се реши транспортният проблем, е необходимо той да бъде затворен.

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

Нека ∑Ai > ∑Bj. В този случай е необходимо да се въведе фиктивен n + 1 потребител с обем на нуждите ∑Ai – ∑Bj Единичните разходи за транспортиране от доставчици до фиктивен потребител се приемат за 0, тъй като в действителност такъв транспорт няма да бъде и част от продуктите ще останат при доставчиците.

Ако ∑Bj > ∑Ai . В този случай е необходимо да се въведе фиктивен m + 1 доставчик с обем на запасите ∑Bj – ∑Ai . Единичните разходи за транспортиране от фиктивен доставчик до потребителите се приемат за равни на 0, тъй като в действителност такъв транспорт няма да бъде извършен и потребителите няма да получат някои от продуктите.

42. Методи за конструиране на първоначалното разпределение в транспортната задача: методът на северозападния ъгъл и методът на най-малкия елемент в матрицата.

Северозападна техника за изграждане на референтен план. Според тази техника формирането на стойностите на трафика започва с s.-z. ъгъл на масата, т.е. от клетка x11. По този метод първо се разпределят стоките на първия доставчик. Нещо повече, първият доставчик първо удовлетворява максимално първия потребител. Тогава, ако доставчикът все още разполага със стоките,

Методът на най-малкия елемент в матрицата.

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

Първо, правим маркировки (например със знака ▼) в тези клетки на линиите, в които се наблюдава най-ниската цена за линията. След това обикаляме таблицата по колони и правим същите бележки в клетките, в които е най-малката цена по колони.

По-нататъшното разпределение първо се прави, доколкото е възможно, върху клетки с две маркировки, след това - с една, след което проблемът се балансира отново до (m + n - 1) запълвания. Организираме пълнежи при преминаване на масата отляво надясно и отгоре надолу.

43. Свойства на транспортните задачи

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

Теорема 1. Затворен транспортен проблем винаги има решение.

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

Теорема 3. системата от ограничения на затворен транспортен проблем винаги е линейно зависима.

От тази теорема следва, че разпределението на затворена транспортна задача винаги има m + n – 1 основни променливи и (m – 1) (n – 1) променливи за свободно време.

44. Дегенеративно разпределение в транспортни проблеми, премахване на дегенерацията. Зачеркната комбинация.

Разпределението се нарича изродено, ако броят на клетките е по-малък от m + n - 1.

45. Теореми за оптималност на транспортната задача.

Теорема.Ако за някакво разпределение на транспортната задача вие

са изпълнени условията:

А). ui+vj = cij за заети клетки

б) ui+vj ≤ сij, за свободни клетки,

тогава това разпределение е оптимално.

Стойностите ui се наричат ​​потенциали на редове, а стойностите vj се наричат ​​потенциали на колони.

46. ​​​​Потенциали и методи за тяхното изчисляване.

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

Броят на уравненията, базирани на това условие, е m + n – 1, а броят на неизвестните ui и vj е m + n. Че. броят на променливите е по-голям от броя на уравненията и всички уравнения са линейно независими. Решението на такава система от линейни уравнения е неопределено, така че на един от потенциалите трябва да бъде приписана произволна стойност. На практика ui = 0. получава се система от m + n – 1 уравнения с m + n – 1 неизвестни променливи. Тази система може да бъде решена по всеки метод. На практика за изчисляване на потенциали се разглеждат заети клетки, за които е известен един от потенциалите им, и въз основа на условие а) на теоремата се изчисляват стойностите на останалите неизвестни потенциали.

47. Изчисляване на оценките на оптималността на разпределението на транспортните задачи и критерия за оптималност.

Въз основа на съотношението b) на теоремата можем да напишем следната формула за изчисляване на оценките: δ ij= ui + vj – сij. За да не се бъркат оценките с обемите на трафика, те (оценките) са оградени в кръгове.

Оценките за оптималност в свободните TK клетки са критерий за оптималност, който проверява разпределението за оптималност. Ако оценките на всички свободни клетки са по-малки или равни на нула, тогава това разпределение е оптимално.

48. преразпределение на доставките в транспортния проблем

Ако разпределението не е оптимално, тогава е необходимо да се преразпределят доставките.

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

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

49. преразпределителни вериги, техните видове.

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

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

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

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

50. Избор на обем на преразпределение.

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

а) след преобразуване в клетките на таблицата не трябва да се получават отрицателни числа;

б) една от заетите клетки трябва да стане свободна.

За да бъдат изпълнени тези условия, е необходимо да се избере обемът на транспортираните продукти, както следва: θ=min (хij) -, където (хij) е обемът на транспортиране от клетките на цикъла на преизчисляване, отбелязани с „ -" знак.

θ = min(20;30)=20

θ се добавя към стойностите на клетките, маркирани със знак "+". θ се изважда от стойностите на клетките, маркирани със знака „-“. Стойността на доставката на останалите клетки се презаписва без промени. В резултат на това получаваме следната таблица.

53. Алгоритъм на метода на потенциалите.

Алгоритъм:

1. Проверете дали уравнението е изпълнено за задачата ако не, в задачата се въвежда фиктивен доставчик или потребител

2. Условието на задачата се записва под формата на транспортна.таблица

3. Изгражда се първоначална базова линия

4. Определят се потенциалите на доставките и потребителите

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

6. Заредете клетка с перспектива. Подгответе нов основен план под формата на транспортна маса. Отидете на точка 4.

54. Счетоводно отчитане на себестойността на производството и транспорта на продукцията. Транспортна задача със забрани за доставка.

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

Където Cij ' е намалената цена за производство на една единица продукция.

Cij “- разходите за транспортиране на една единица продукция.

Задачи със забрани за доставка.

В някои ситуации не е възможно да се транспортират продукти по никакъв маршрут.

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

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

отчитане на ограниченията върху пропускателната способност на маршрутите.

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

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

В някои случаи задачата изисква, например, по маршрута Ak Bs да се извърши доставка в единици обем А. В този случай задължителната доставка се изважда от обема на производството на точка А и обема S Bs и проблемът се решава по отношение на незадължителната доставка. След получаване на оптималното решение запасът задължително се добавя към обема, стоящ в клетката Ak Bs.

56. Възможни изводи с икономически. интерпретация на оптималното разпределение за отворени транспортни проблеми.

При получаване на оптималното разпределение е необходимо да се върнете към първоначалния проблем и да направите подходящото икономично. заключения. Те са следните:

1. Ако се въведе точка на потребление, това означава, че в анализираната система има прекомерни производствени обеми и е възможно, без да се засяга разглежданата система, да се намалят капацитетите на тези точки на производство с количеството на свързване които са обвързани с фиктивната точка на потребление.

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

57. Концепцията за дуалност. Икономическа формулировка на двойни проблеми на примера на проблема за оптимизиране на производствения план.

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

Нека има задача за оптимизиране на производствения план. Изглежда така:

Първоначална задача:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | на 2

……………….. |.. (1)

А T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤v 1 | при T

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - броят на суровините от i-тия вид, изразходвани за производството на j-ия вид продукт

Двоен проблем

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

i - цената на i-тия вид суровина, налична в предприятието.

a 11 y 1 + a 21 y 2 + ... + a T 1 г T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥s 2

……………….. (1’)

А 1стр y 1 +a 2т y 2 +...+ a tpпри T≥s П

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Съответствие между структурните елементи на правата и двойствената задача

Всеки проблем на линейното програмиране може да бъде свързан

двойна задача по следните правила:

1. Във всички ограничения на първоначалния проблем свободните условия трябва

бъде отдясно, а термините с неизвестни отляво.

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

насочени в една посока.

3. Ако целевата функция в първоначалния проблем е минимизирана, ограниченията на неравенството трябва да бъдат записани със знака "≤", тогава в двойствения проблем целевата функция ще бъде минимизирана и знаците на ограниченията на неравенството ще бъдат "≥".

4. Всяко ограничение на първоначалния проблем съответства на променлива в

двойна задача. Ако една променлива съответства на неравенство, тя е неотрицателна, ако съответства на равенство, тогава променливата е без ограничения на знака („произволна“).

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

коефициенти за променливите на първоначалния проблем.

6. Свободните членове на първоначалната задача са коефициентите при

променливи в целевата функция на двойствения проблем и безплатно

термините в двойния проблем са коефициентите на променливите в

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

59. Конструиране на двойствени задачи към оригинални задачи, написани в стандартната, канонична и обща форма на модела (конструиране на симетрични и асиметрични двойствени задачи)

Стандартен формуляр (оригинал)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Двоен стандарт

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Оригиналният проблем в канонична форма:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Двойно каноничен

Σ a ij y i ≤ c j , j=1,n(1)

y i - всякакви (2)

F = Σ b i y i ->max(3)

Нека дадем икономическа интерпретация на двойка двойни проблеми. Помислете за проблема с рационалното използване на ресурсите. Нека предприятието разполага с ресурси b1,b2,…bm, които могат да бъдат използвани за производство на n-видове продукти. Нека са известни също цената на единица от j-тип продукт cj (j=1,n) и нормата на потребление на i-тия ресурс (i=1,m) за производството на единица j-та продукция– aij Необходимо е да се определи обемът на производството на всеки тип xj (j=1,n), като се максимизират общите разходи

f= c1x1+...+cnxn (1)

В същото време потреблението на ресурси не трябва да надвишава тяхната наличност:

a11x1+...+a1nxn<=b1 }

…………………….. } (2)

am1x1+...+amnxn<=bm }

Всички известни в техния икономически смисъл са неотрицателни:

Xj>=0 (j=1,n). (3)

Обърнете внимание, че този проблем представлява симетричен двоен проблем.

Асиметрични двойствени проблеми.

Нека вземем ZLP максимално в каноничната форма:

Макс Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Основна и втора теорема за дуалността (посочете теоремите и обяснете)

Първата теорема за двойствеността.

Теорема: ако една от дуалните задачи има оптимален план, то другата е разрешима, т.е. има опт.план. В този случай екстремните стойности на целевите функции съвпадат (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* ако е в оригинала. проблем целевата функция е неограничена върху множеството от планове, тогава в двойствения проблем системата от ограничения е непоследователна.

Втора теорема за дуалност и нейната икономическа интерпретация.

За да валидни решениядвойки двойни задачи са били оптимални, е необходимо и достатъчно да се изпълни условието: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до м. Това са условия на допълнителна отпуснатост. От тях следва: ако всяко ограничение на двойствения проблем се преобразува от оптималния план в строго равенство, тогава съответният компонент на опт. план на двойствения проблем трябва да е равен на 0. Ако някой компонент опт. plan е равно на нула, тогава съответното ограничение на двойствения проблем се преобразува от opt.plan в строго равенство xj*>0, следователно (i= от 1 до m)Σaij yi*=cj opt.plan, тогава ако разходи>цени, производствен обем=0 Σaij yi* >cj следователно xj*=0

yi*>0 следователно (j=от 1 до n) Σaij xj*=bi (състезания за ресурси = запас от ресурси).

(j=1 до n) Σaij xj*

Значението на теоремата е следното:

Ако оценката на разходите за потреблението на ресурси за производство на единица продукт-ii \u003d цена, тогава този тип продукт-ii е включен в оптималния план;

Ако разходите надвишават цената, тогава продукцията не трябва да се произвежда;

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

Ако ресурсът не е изразходван напълно, тогава неговата оценка на разходите е = 0.

61. Изграждане на оптимален опорен план за дуалната задача от симплексната таблица на първоначалната задача

Информация от колоните на обратната матрица на линейните трансформации, довели до оптималния резултат. Колоните на матрица D-1 предоставят много полезна информация.

Колона A3: "сенчестата" цена на ресурс S2 е y01=0, колоната остава

единичен и от първия ред се чете, че x3=9, т.е. при изпълнение на намерения оптимален план първият ресурс ще бъде в излишък и този излишък (недоизползване) ще възлиза само на 9 условни единици.

Колона A4: "сенчестата" цена на ресурса S2 е равна на y02=1, ресурсът ще бъде използван напълно и евентуалното му увеличение ще доведе до увеличаване на целевата функция (т.е. доход). И защото y02=1, тогава увеличението на ресурса S2 с 1 c.u. ще даде добавка по отношение на дохода от.Z = y02· .w2 = = 1,1 = 1 (хиляда UAH) (тук.w2 е увеличението на ресурса S2 и .Z е съответното увеличение на дохода). С такова увеличение на ресурса S2 максималният доход вече ще бъде Zmax=58 хил. UAH. + 1 хил. UAH = 59 хил. UAH. На фиг. 6.2 илюстрира тази ситуация, чийто коментар ще бъде даден по-долу. От колона A4 също следва, че с увеличаване на ресурса S2 с 1 c.u. за новата оптимална точка производството на стоки T1 ще намалее с ½ тона (в пресечната точка на реда на основната променлива x1 и колона A4 е "-1/2"), а производството на стоки T2 ще се увеличи с 3 /2 тона (защото в реда с основната променлива x2 в колона A4 имаме "3/2". Казаното за колона A4 ще бъде коментирано по-долу с помощта на графични конструкции (фиг. 6.2). Колона A5: "сянката" " цената на ресурса S3 е равна на y03=2. Това означава, че увеличение на ресурса S3 с 1 у.е. ще донесе добавка в Z към.Z = y03 · .v3 = 2.1 =2(хиляда гривни) и ще бъде Zmax=58 хиляди гривна. + 2 хиляди UAH = 60 хиляди UAH. В същото време, както следва от колона А5 на табл. 3, производството на T1 ще се увеличи с ½ тон и T2 ще намалее с ½ тон. Запасът от суровини S1 (виж ред 1) ще се увеличи с 3/2 c.u.

62. Идеята за метода на динамичното програмиране и неговата геометрична интерпретация. Принцип на оптималност на Белман.

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

За да го дефинирате, трябва:

1. запишете функционалното уравнение за последното състояние на процеса (съответства на l \u003d n-1)

fn-1(Sl-1)=оптимум(Rn(Sn-1,Un)+f0(Sn))

2. намерете Rn(Sn-1,Un) от дискретен набор от неговите стойности за някои фиксирани Sn-1 и Un от съответните допустими области (тъй като f0(Sn)=0, тогава f1(Sn-1)= оптимален (Rn( Sn-1,Un)

В резултат след първата стъпка решението Un и съответната стойност на функцията f1(Sn-1) са известни.

3. Намалете стойността на l с единица и запишете съответното функционално уравнение. За l=n-k (k= 2,n) изглежда така

fk(Sn-k)=оптимум(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. намерете условно оптимално решение въз основа на израз (2)

5. Проверете на какво е равна стойността на l. Ако l=0, изчисляването на условно оптималните решения е завършено и се намира оптималното решение на задачата за първото състояние на процеса. Ако l не е равно на 0, преминете към стъпка 3.

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

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

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

Математически се записва като израз на формата:

fn-1(Sl)=оптимум(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1) Оптимално в израза означава максимума или минимума в зависимост от условието на проблема.

63. Изисквания към задачи, решени по метода на ДП

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

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

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

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

64. Икономическа формулировка и изграждане на математически модел на проблема, решен чрез метода на ДП (на примера на проблема за разпределението на капиталовите инвестиции). Рекурентна връзка на Белман.

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

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

разделяне на цялата партида на отделни стъпки (етапи). А при военна операция за преследване на една ракета срещу друга, целият непрекъснат процес трябва да бъде изкуствено разделен на етапи, например всяка секунда наблюдение. Динамичният метод на програмиране позволява оптимизирането на целия комплексен процес да бъде заменено с условна оптимизация за всеки един от етапите

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

Всички изчисления, които позволяват да се намери оптималната стойност на ефекта, постигнат в n стъпки, fn(S0), се извършват съгласно формула (1), която се нарича основно функционално уравнение на Белман или рекурентна връзка. При изчисляване на следващата стойност на функцията fn-1 се използва стойността на функцията fn-(l+1), получена на предишната стъпка, и директната стойност на ефекта Rl+1(Sl,Ul+1), постигнато в резултат на избор на решение Ul+1 за дадено състояние Sl системи. Процесът на изчисляване на стойността на функцията fn-1(l=0,n-1)

Провежда се при естествено начално условие f0(Sn)=0, което означава, че извън крайното състояние на системата ефектът е нулев.

65. Проблемът за разпределението на капиталовите инвестиции (пример).

За да решим проблема за оптималното разпределение на капиталовите инвестиции, ще използваме функционалното уравнение на Белман. Първо, използвайки най-простата ситуация, ще илюстрираме извеждането на функционалното уравнение на Белман и след това, използвайки пример, ще докажем как да използваме това уравнение за решаване на проблема, който ни интересува.

Да започнем с оптималното разпределение на разпределените капиталови инвестиции в размер на K между две предприятия. Плановите отдели на предприятията въз основа на своите изчисления формираха функциите на дохода q(x) за предприятието P1 и h(x) за предприятието P2. Тези функции означават, че ако първото или второто предприятие получи инвестиция в размер на x, тогава първото предприятие

ще бъде получен доходът q(x), а вторият h(x), а стойността на x може да приеме непрекъснати или известни дискретни стойности от 0 до K.

И така, нека компанията P1 е разпределила капиталови инвестиции в размер на x, тогава на компанията P2 е разпределена сумата K - x. В този случай доходът q(x) ще бъде получен от първото предприятие, а h(K - x) от второто. Ако инвестициите K са разпределени за един период на планиране, тогава общият доход от двете предприятия ще бъде R(K, x) = q(x) + h(K - x). Очевидно x и съответно K - x трябва да бъдат избрани така, че R(K, x) да приеме максималната си стойност, която обозначаваме с F(K):

Този запис е като скелет за по-пълни записи.

функционално уравнение на Белман. Усложнете нашата задача, като разпределите капиталовите инвестиции в два планови периода (два етапа) . Нека първоначално бъде решено да се разпредели сумата x на първото предприятие P1 и x на второто предприятие P1. Като цяло доходът ще бъде равен на R(K, x) = q(x) +

h(K - x). Ако имаме предвид, че инвестициите са разпределени в 2 периода (2 етапа), тогава в първото предприятие балансът на инвестициите ще бъде x, където , а във второто - .(K - x), където Съответно доходът за вторият период ще бъде q( .x) - според първото съоръжение и h[.(K - x)] - според второто. Оптимизацията на динамичното програмиране, като правило, започва от крайния етап. Затова започваме от втория етап, като с F1 обозначаваме максималния възможен доход от две предприятия във втория

сцена. Вземете

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

По същия начин за n етапа получаваме

където Fn-1 е целевата функция, която дава най-добър резултат за последните (n - 1) етапи. Полученото функционално уравнение на Белман е рекурентно, т.е. свързва стойността Fn със стойността Fn-1.

По-общо, уравнението на Белман има формата

където , Fn-1 - максимален доход за (n - 1) последните етапи, Fn -

максимален доход за всички n етапа.

66. Концепцията за решаване на проблеми на нелинейното програмиране

Нека проблемът на нелинейното програмиране бъде поставен в следната обща форма: намерете такива стойности на променливите x1, x2, ..., xn, които отговарят на условията:

и довеждат необходимия екстремум (максимум или минимум) на целевата функция

f = f(x1, x2,…, xn), (13.2)

където f(х1, …, хn) и qi(х1, …, хn) (m , 1 i =) са реални нелинейни,

регулярни функции на n реални променливи.

Според техните общи свойства задачите за нелинейно програмиране могат

значително различни от линейните. Например областта на допустимите решения може вече да не е изпъкнала и екстремумът на целевата функция може да се наблюдава във всяка точка от допустимата област. Методите за решаване на нелинейни проблеми също се различават значително. Нека разгледаме само някои подходи за решаване на тези проблеми.

На първо място, графичният подход е валиден и при решаването на най-простите задачи на нелинейното програмиране. Така че, ако променливите x1 и x2 са аргументите на проблема, тогава първо областта на възможните решения се изгражда върху равнината на тези променливи и след това оптималната точка в областта се определя с помощта на нивата на целевата функция f(x1,x2).

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

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

Освен това първо се прави преход по градиента на целевата функция и след това връщане към областта. по протежение на градиента до нарушената граница на областта O2 O3. 13.3 е показано така, че Ai с нечетни индекси принадлежат към областта., а точките Ai с четни индекси не принадлежат.При приближаване до оптималната точка Q посоките на работните градиенти се сближават. Следователно идеалният критерий за спиране на процеса ще бъде колинеарността на целевия градиент и прекъснатия граничен градиент.

67. Концепцията за параметрично и целочислено програмиране .

Постановка и математически модел на ZCLP.

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

f=(n,j=1)∑CjXi макс

(n,j=1)∑AijXj=bi, i=1,m

xi-цяло число,j=1,n

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

1. Методи за изрязване

2.Комбинаторни

3.Приблизителни методи..

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

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

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

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

Най-общо математическият модел на задача за линейно програмиране (LP) се записва като

с ограничения:

Където x j- неизвестен; aij, b i, cjса дадени константи.

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

Математическият модел в по-кратка нотация има формата

с ограничения:

Определение.Възможно решение (план) на проблем с линейно програмиране е вектор = ( х 1 , х 2 ,..., x p),задоволяване на системата от ограничения.

Множеството от допустимите решения образува областта на допустимите решения (ODD).

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

Основно допустимо решение (Х 1 , х 2 ,...,х r , 0, …, 0) е референтно решение, където р-ранга на системата за ограничения.

Математическият модел на задачата LP може да бъде каноничен и неканоничен.

7. Решаване на задачи от линейно програмиране по графичен метод. Графики на ограничителни функции. Линии на ниво.

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

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

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

За намиране на екстремната стойност на целевата функция в графичното решение на задачите на ЛП се използва векторът Л() на повърхността х 1 ОХ 2 , които обозначаваме . Този вектор показва посоката на най-бързата промяна на целевата функция. С други думи, векторът е нормалата на линията на нивото Л()

Където д 1 и д 2 - единични вектори по осите ОХ 1 и ОХ 2 съответно; по този начин = (∂L/∂x 1 , ∂L/∂х 2 ). Координатите на вектора са коефициентите на целевата функция L().Конструкцията на линията на нивото ще бъде разгледана подробно при решаване на практически задачи.

Алгоритъм за решаване на проблеми

1. Намираме областта на възможните решения за системата от ограничения на проблема.

2. Изграждане на вектор .

3. Начертайте равна линия Л 0 , който е перпендикулярен .

4. Преместваме линията на нивото по посока на вектора за задачи до максимум и в обратна посока , за минимум задачи.

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

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

Където 0 ≤ T≤ 1, 1 и 2 - оптимални решения в ъгловите точки на ODS.

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

5. Намираме координатите на екстремалната точка и стойността на целевата функция в нея.

Пример 3Избор на най-добрата опция за пускане на продукт

Фирмата произвежда 2 вида сладолед: сметанов и шоколадов. За производството на сладолед се използват два изходни продукта: мляко и пълнители, чиито разходи за 1 кг сладолед и дневни доставки са дадени в таблицата.

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

Освен това беше установено, че търсенето на шоколадов сладолед не надвишава 350 кг на ден. Цената на дребно на 1 кг кремообразен сладолед е 16 рубли, шоколад - 14 рубли.

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

Решение.Означават: х 1 - дневен обем на производство на кремообразен сладолед, kg; х 2 - дневно производство на шоколадов сладолед, кг.

Нека направим математически модел на проблема.

Цените за сладолед са известни: съответно 16 рубли и 14 рубли, така че целевата функция ще изглежда така:

Поставете ограничения за млякото за сладолед. Разходът му за кремообразен сладолед е 0,8 кг, за шоколадов сладолед - 0,5 кг. Запас от мляко 400кг. Следователно първото неравенство ще изглежда така:

0,8x 1 + 0,5x 2 ≤400 - първото неравенство е ограничение. По подобен начин се съставят и останалите неравенства.

Резултатът е система от неравенства. каква е областта на решение на всяко неравенство. Това може да стане чрез заместване на координатите на точката O(0:0) във всяко от неравенствата. В резултат на това получаваме:

Фигура OABDEF-област на допустимите решения. Изграждаме вектора (16; 14). линия на ниво Л 0 се дава от уравнението 16x 1 +14x 2 = Const. Избираме произволно число, например числото 0, след това 16x 1 +14x 2 =0. На фигурата за правата L 0 е избрано положително число, различно от нула. Всички линии на ниво са успоредни една на друга. Нормалният вектор на линията на нивото.

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

Решавайки системата, получаваме координатите на точката д(312.5; 300), в който ще има оптимално решение, т.е.

Така компанията трябва да произвежда 312,5 кг маслен сладолед и 300 кг шоколадов сладолед на ден, а приходите от продажби ще бъдат 9200 рубли.

8. Свеждане на произволна задача от линейно програмиране до основната задача.Преобразуване на ограничения, дадени от неравенства, в съответни уравнения.

9.Симплексен метод. Характеристики и алгоритъм на метода, неговата приложимост.

За да се реши задачата по симплексния метод, е необходимо:

1. Посочете метод за намиране на оптималното еталонно решение

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

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

Алгоритъм на симплексния метод за решаване на задачи от линейното програмиране

1. Приведете проблема в каноничната форма

2. Намерете първоначалното решение за поддръжка с "единична основа" (ако няма решение за поддръжка, тогава проблемът няма решение, поради несъвместимостта на системата от ограничения)

3. Изчислете оценките на векторните разширения по отношение на базата на еталонното решение и попълнете таблицата на симплексния метод

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

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

10. Транспортна задача.Определение, видове, методи за намиране на първоначалното решение на транспортната задача.

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

1. Намиране на първоначалното еталонно решение;

2. Проверка на това решение за оптималност;

3. Преход от едно основно решение към друго.

Т10. Постановка на задачата за линейно програмиране

математически моделИкономическият проблем е набор от математически зависимости, които описват икономическия процес.

За съставяне на математически модел е необходимо:

1. изберете променливи на задачата;

2. изготвя система от ограничения;

3. задайте целевата функция.

Променливи на задачитесе наричат ​​величините x 1 , x 2 ,…, x n, които напълно характеризират икономическия процес. Те обикновено се записват като вектор X \u003d (x 1, x 2, ..., x n).

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

Целевата функция се наричафункция F(X) = f(x 1 , x 2 ,…, x n) на променливите на задачата, която характеризира качеството на задачата и чийто екстремум трябва да бъде намерен.

Общ проблем на математическото програмиранесе формулира по следния начин: намерете променливите на задачата x 1 , x 2 ,…, x n, които осигуряват екстремума на целевата функция

F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)

и удовлетворяват системата от ограничения (1).

Ако целевата функция (2) и ограничителната система (1) са линейни, тогава проблемът на математическото програмиране се нарича проблем с линейно програмиране (LPP).

Извиква се векторът X (набор от променливи на задачата). приемливо решение, или плана PLP, ако удовлетворява системата от ограничения (1). Извиква се осъществим план X, който осигурява екстремум на целевата функция оптимално решениеЗЛП.

2. Примери за съставяне на математически модели на икономически проблеми

Изследването на конкретни производствени ситуации води до ZLP, които се интерпретират като проблеми на оптималното използване на ограничените ресурси.

1.Проблемът с оптималния производствен план

За производството на два вида продукти T 1 и T 2 се използват три вида ресурси S 1 , S 2 , S 3 . Запасите от ресурси, броят на единиците ресурси, изразходвани за производството на единица продукция, както и печалбата от продажбата на единица продукция са показани в таблицата:

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

Решение.

Нека обозначим x 1, x 2 - броят на единиците продукция, съответно T 1 и T 2, планирани за производство. За производството им ще са необходими (x 1 + x 2) единици ресурс S 1, (x 1 + 4x 2) единици ресурс S 2, (x 1) единици ресурс S 3. Разходът на ресурси S 1 , S 2 , S 3 не трябва да надвишава техните запаси, съответно 8, 20 и 5 единици.

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

Намерете производствен план X \u003d (x 1, x 2), който удовлетворява системата от ограничения:

и състоянието

при които функцията приема максимална стойност.

Проблемът може лесно да се обобщи за случая на производство на n вида продукти с използване на m вида ресурси.

2.Проблемът с оптималната диета

Има два вида храни K1 и K2, съдържащи хранителни вещества S1, S2 и S3. Съдържанието на броя на хранителните единици в 1 kg от всеки вид фураж, необходимия минимум хранителни вещества, както и цената на 1 kg фураж са показани в таблицата:

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

Решение.

Нека обозначим x 1, x 2 - количеството фураж K 1 и K 2, включени в дневната диета. Тогава тази диета ще включва (3x 1 + x 2) единици хранително вещество S 1, (x 1 + 2x 2) единици вещество S 2, (x 1 + 6x 2) единици хранително вещество S 3. Тъй като съдържанието на хранителни вещества S 1 , S 2 и S 3 в храната трябва да бъде съответно 9, 8 и 12 единици, икономико-математическият модел на проблема може да се формулира по следния начин:

Съставете дневна диета X \u003d (x 1, x 2), отговаряща на системата от ограничения:

и състоянието

при които функцията приема минималната стойност.

PLP формуляри за запис

В LLP се изисква да се намери екстремумът на линейната целева функция:

с ограничения:

и условието за неотрицателност

където a ij , b i , c j ( , ) са дадени константи.

Така е записано в ЗЛП общформа. Ако системата за ограничения съдържа само неравенства, тогава LLP е представена в стандартенформа. Каноничен (основен)формата на нотацията ZLP е нотацията, когато системата от ограничения съдържа само равенства. Така че горните LLP са написани в стандартна форма.

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

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

Ограничение за неравенство (£) може да бъде преобразувано в ограничение за равенство чрез добавяне на допълнителна неотрицателна променлива към лявата му страна, а ограничение за неравенство (³) може да бъде преобразувано в ограничение за равенство чрез изваждане на допълнителна неотрицателна променлива от неговата лява страна. Броят на въведените допълнителни неотрицателни променливи е равен на броя на трансформираните ограничения на неравенството.

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

Пример 1. Напишете в каноничната форма ZLP:

с ограничения:

Решение.

Целевата функция остава непроменена:

Системата от неравенства се трансформира в система от равенства:

При решаване на LLP чрез графичен метод е необходим преход от каноничната форма към стандартната форма.

За да приведете LLP в стандартна форма, използвайте Метод на Джордан-Гаус SLAU решения. За разлика от метода на Гаус, при който разширената матрица на системата се свежда до стъпкова форма, при метода на Джордан-Гаус матрицата на идентичност се формира като част от разширената матрица. Следователно тук не се изисква обратно движение.

За да конвертирате оригиналния каноничен LLP в еквивалентен стандартен LLP:

а) в разширената матрица на ограничителната система е избран ненулев елемент a qp. Този елемент се нарича разрешителен, и q - i ред и p-та колона наречен активиране на ред и активиране на колона.

б) разрешаващият низ се пренаписва без промяна и всички елементи на разрешаващата колона, с изключение на разрешаващата колона, се заменят с нули. Останалите елементи на разширената матрица се определят с помощта на "правилото на правоъгълника":

Разгледайте четири елемента от разширената матрица: елементът a ij, който трябва да бъде трансформиран, разделящият елемент a qp и елементите a i p и a qj. За да се намери елемент a ij, следва от елемента a ij да се извади произведението на елементите a i p и a qj, разположени в противоположните върхове на правоъгълника, разделено на разделящия елемент a qp:

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

Пример 2. Промяна към стандартна форма:

Решение.

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

Числото -9, получено в последната колона на последния ред, трябва да бъде записано в целевата функция с обратен знак. В резултат на трансформациите LLP приема формата:

защото променливите x 2 и x 3 са неотрицателни, след което ги отхвърляме, можем да напишем ZLP в симетрична форма:

В каноничната форма на LLP целевата функция може да бъде както минимизирана, така и максимизирана. Да преминете от намиране на максимума към намиране на минимума или обратно, достатъчно е да промените знаците на коефициентите на целевата функция: F 1 = - F. Полученият проблем и оригиналният LLP имат едно и също оптимално решение, а стойностите на целевите функции на това решение се различават само в знак.

Свойства на ЗЛП

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

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

Според тази дефиниция многоъгълникът на фиг. 1а е изпъкнало множество, докато многоъгълникът на фиг. 1b не е, тъй като отсечката MN между двете си точки M и N не принадлежи изцяло на този многоъгълник.

Изпъкналите множества могат да бъдат не само многоъгълници. Примери за изпъкнали множества са кръг, сектор, сегмент, куб, пирамида и др.

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

Точка X се нарича изпъкнала линейна комбинацияточки X 1 , X 2 ,…, X n, ако са изпълнени следните условия:

X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,

αj ≥ 0, Σαj = 1.

Очевидно е, че в специалния случай за n = 2 изпъкнала линейна комбинация от две точки е отсечка, която ги свързва.

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

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

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

Лекция 2

IN канонична форма

допустимо решение на ПРЗ(приемлив план).

оптимално решение на LLP.

Необходимост

Пример.

Нека напишем проблема канонична форма

Особени ситуации на графичното решение на ЗЛП

Освен когато задачата е единственото оптимално решениеза и , може да бъде специални ситуации:

1. задача има безкраен брой оптимални решения – екстремумът на функцията е достигнат на отсечката ( алтернативен оптимум)- Фигура 2;

2. задача не е разрешимо поради неограничеността на ODR, или - Фигура 3;

3. ODR - единична точка А, тогава;

4. задача не е разрешимо ако ODR има празна област.

А

Фигура 2 Фигура 3

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

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

Пример. Решете графично задачата за линейно програмиране ( алтернативен оптимум):

Въпроси за самоконтрол

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

2. Запишете задачата за линейно програмиране в канонична и стандартна форма.

3. Какви трансформации могат да се използват за преминаване от обща или стандартна форма на задача за линейно програмиране към канонична?

4. Дайте дефиниция на възможни и оптимални решения на проблема с линейното програмиране.

5. Кое от решенията е „най-доброто“ за задачата за минимизиране на функцията if ?

6. Кое от решенията е „най-доброто“ за задачата за максимизиране на функцията if ?

7. Запишете стандартната форма на математическия модел на задача от линейно програмиране с две променливи.

8. Как да построим полуравнина, зададена от линейно неравенство с две променливи ?

9. Какво се нарича решение на система от линейни неравенства с две променливи? Конструирайте в равнината областта на възможните решения на такава система от линейни неравенства, която:

1) има уникално решение;

2) има безкраен набор от решения;

3) няма решение.

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

11. Формулирайте алгоритъм за графичен метод за решаване на стандартен LLP с две променливи.

12. Как да намерим координатите и стойностите на решението, ?

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

1) се достига в една точка и - на ODR сегмента;

2) се достига в една точка на ODS и .

14. Дайте геометрична илюстрация на LLP, ако:

1) има уникални оптимални решения за и ;

2) има набор от оптимални решения за .

Лекция 2

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

1. Форми на линейни математически модели и тяхното преобразуване

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

3. СПЕЦИАЛНИ СИТУАЦИИ НА ГРАФИЧНОТО РЕШЕНИЕ НА LLP

4. Графично решение на икономически задачи на линейното програмиране

Форми на линейни математически модели и тяхното преобразуване

Математическият модел на задача за линейно програмиране (LPP) може да бъде написан в една от трите форми.

IN обща форма на математическия моделизисква се намиране на максимума или минимума на целевата функция; системата от ограничения съдържа неравенства и уравнения; не всички променливи могат да бъдат неотрицателни.

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

В стандартната форма на математически модел се изисква да се намери максимумът или минимумът на функция; всички ограничения са неравенства; всички променливи са неотрицателни.

Решението на системата от ограничения, което удовлетворява условията за неотрицателност на променливите, се нарича допустимо решение на ПРЗ(приемлив план).

Множеството от възможни решения се нарича областта на осъществимите решения на LLP.

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

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

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

Преход към каноничната нотация ZLP.

Пример.

Нека напишем проблема канонична форма, въвеждайки допълнителна (балансова) променлива със знака "+" в лявата страна на първото неравенство на системата за ограничения и допълнителна променлива със знака "минус" в лявата страна на второто неравенство.

Икономическото значение на различни допълнителни променливи може да не е едно и също: зависи от икономическото значение на ограниченията, в които тези променливи са включени.

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

Основата за решаване на икономически проблеми са математическите модели.

математически моделпроблемът е набор от математически зависимости, които описват същността на проблема.

Изготвянето на математически модел включва:

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

Променливи на задачитесе наричат ​​величини X1, X2, Xn, които характеризират напълно икономическия процес. Обикновено те се записват като вектор: X=(X 1 , X 2 ,...,X n).

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

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

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

Този запис означава следното: намерете екстремума на целевата функция (1) и съответните променливи X=(X 1 , X 2 ,...,X n), при условие че тези променливи отговарят на системата от ограничения (2) и не -условия за отрицателност (3) .

Приемливо решение(план) на проблем с линейно програмиране е всеки n-мерен вектор X=(X 1 , X 2 ,...,X n), който удовлетворява системата от ограничения и условия за неотрицателност.

Съвкупността от възможни решения (планове) на проблема формира набор от възможни решения(ODR).

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

Пример за съставяне на математически модел

Задачата за използване на ресурси (суровини)

Състояние:За производството на n вида продукти се използват m вида ресурси. Направете математически модел.

Известен:

• b i (i = 1,2,3,...,m) са запасите на всеки i-ти вид ресурс;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) са разходите за всеки i-ти вид ресурс за производството на единица обем от j-тият вид продукт;
• c j (j = 1,2,3,...,n) е печалбата от продажбата на единица обем от j-тия вид продукт.

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

Решение:

Въвеждаме вектор от променливи X=(X 1 , X 2 ,...,X n), където x j (j = 1,2,...,n) е обемът на производството от j-тия вид на продукт.

Разходите на i-тия вид ресурс за производството на даден обем x j продукти са равни на a ij x j, следователно ограничението за използване на ресурси за производството на всички видове продукти има формата:
Печалбата от продажбата на j-тия вид продукт е равна на c j x j, така че целевата функция е равна на:

Отговор- Математическият модел изглежда така:

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

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

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

Тя може да бъде представена в координатна, векторна и матрична нотация.

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

Проблемът с каноничното линейно програмиране в матрична нотация има формата:

• A е матрицата на коефициентите на системата от уравнения
• X е колонна матрица от променливи на задачата
• Ao е матрицата-колона на десните части на ограничителната система

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

Привеждане на обща задача за линейно програмиране до канонична форма

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

Това може да стане по следния начин:

Вземете линейно неравенство a 1 x 1 +a 2 x 2 +...+a n x n ≤b и добавете към лявата му страна някаква стойност x n+1, така че неравенството да стане равенството a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Освен това тази стойност x n+1 е неотрицателна.

Нека разгледаме всичко с пример.

Пример 26.1

Намалете проблема с линейното програмиране до канонична форма:

Решение:
Нека преминем към задачата за намиране на максимума на целевата функция.
За да направим това, променяме знаците на коефициентите на целевата функция.
За да преобразуваме второто и третото неравенство на ограничителната система в уравнения, въвеждаме неотрицателни допълнителни променливи x 4 x 5 (тази операция е отбелязана с буквата D на математическия модел).
Променливата x 4 се въвежда от лявата страна на второто неравенство със знак "+", тъй като неравенството има формата "≤".
Променливата x 5 се въвежда от лявата страна на третото неравенство със знака "-", тъй като неравенството има формата "≥".
Променливите x 4 x 5 се въвеждат в целевата функция с коефициент. равно на нула.
Записваме проблема в канонична форма.