Оптималната стойност на целевата функция се нарича. Тестове за текущ контрол на знанията

Разделете третия ред на ключовия елемент, равен на 5, получаваме третия ред на новата таблица.

Основните колони съответстват на единичните колони.

Изчисляване на други стойности на таблицата:

„BP – Основен план“:

; ;

"x1": ; ;

"x5": ; .

Стойностите на индексния низ са неотрицателни, следователно получаваме оптималното решение: , ; .

Отговор:максималната печалба от продажбата на произведени продукти, равна на 160/3 единици, се осигурява от производството само на продукти от втори тип в размер на 80/9 единици.

Задача No2

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

защото последната цифра на шифъра е 8, тогава A=2; B=5.

защото предпоследната цифра на шифъра е 1, тогава трябва да изберете задача №1.

Решение:

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

Тази област е триъгълник ABC с координати на върха: A(0; 2); B(4; 6) и C(16/3; 14/3).

Нивата на целевата функция са окръжности с център в точката (2; 5). Квадратите на радиусите ще бъдат стойностите на целевата функция. Тогава фигурата показва, че минималната стойност на целевата функция се постига в точка Н, максималната - или в точка А, или в точка С.

Стойността на целевата функция в точка А: ;

Стойността на целевата функция в точка C: ;

Това означава, че максималната стойност на функцията се постига в точка A(0; 2) и е равна на 13.

Нека намерим координатите на точка H.

За да направите това, помислете за системата:

ó

ó

Една права е допирателна към окръжност, ако уравнението има единствено решение. Квадратно уравнение има уникално решение, ако дискриминантът е 0.

Тогава ; ; - минимална стойност на функцията.

2) Нека съставим функцията на Лагранж, за да намерим минималното решение:

При х 1 =2.5; х 2 =4.5 получаваме:

ó

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

Нека съставим функцията на Лагранж, за да намерим максималното решение:

Достатъчни условия за екстремум:

При х 1 =0; х 2 =2 получаваме:

ó ó

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

Отговор:минимумът на целевата функция се постига, когато ; ; максимумът на целевата функция се постига при ; .

Задача No3

На две предприятия са отпуснати средства в размер дединици. При разпределяне на първото предприятие за година хпарични единици осигурява доход к 1 хединици, а когато са разпределени към второ предприятие гпарични единици, той осигурява доход к 1 гединици. Салдото на средствата в края на годината за първото предприятие е равно на nx, а за второто моя. Как да разпределим всички средства за 4 години, така че общият доход да е най-голям? Решете проблема, като използвате метода на динамично програмиране.

i=8, k=1.

А=2200; k 1 =6; k 2 =1; п=0,2; m=0,5.

Решение:

Разделяме целия период от 4 години на 4 етапа, всеки от които е равен на една година. Нека номерираме етапите, започвайки от първата година. Нека X k и Y k са средствата, разпределени съответно на предприятия A и B на k-тия етап. Тогава сумата X k + Y k = a k е общата сума на средствата, използвани на k – този етап и остатъка от предишния етап k – 1. на първия етап се използват всички разпределени средства и a 1 = 2200 единици . доходът, който ще бъде получен на k – този етап, с разпределението на X k и Y k единици ще бъде 6X k + 1Y k. нека максималният доход, получен на последните етапи, започвайки от k – този етап е f k (a k) единици. Нека запишем функционалното уравнение на Белман, изразяващо принципа на оптималност: каквото и да е първоначалното състояние и първоначалното решение, следващото решение трябва да бъде оптимално по отношение на състоянието, получено в резултат на първоначалното състояние:

За всеки етап трябва да изберете стойността X k и стойността Y k=ак- Хк. Като вземем това предвид, ще намерим дохода на k-тия етап:

Функционалното уравнение на Белман ще бъде:

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

(тъй като максимумът на линейната функция се постига в края на сегмента при x 4 = a 4);

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

Изграждаме прави линии в координатната система x 1 x 2

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

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

Премествайки права линия (5) в посока на вектора, виждаме, че максималната точка на областта ще бъде в точка А на пресечната точка на права линия (3) и права линия (2). Намираме решението на системата от уравнения:

Това означава, че получихме точката (13;11) и.

Премествайки правата линия (5) в посока на вектора, виждаме, че минималната точка на областта ще бъде в точка B на пресечната точка на права линия (1) и права линия (4). Намираме решението на системата от уравнения:

Това означава, че получихме точката (6;6) и.

2. Мебелна фирма произвежда комбинирани шкафове и компютърни маси. Производството им е ограничено от наличието на суровини (висококачествени плоскости, обков) и времето на работа на машините, които ги обработват. За всеки шкаф са необходими 5 м2 дъски, за маса - 2 м2. Фитингите струват $10 за един шкаф и $8 за една маса. Компанията може да получи от своите доставчици до 600 m2 плоскости на месец и аксесоари на стойност $2000. Всеки шкаф изисква 7 часа работа на машината, а масата изисква 3 часа. Месечно могат да се използват общо 840 работни часа на машината.

Колко комбинирани шкафове и компютърни маси трябва да произвежда една компания на месец, за да увеличи максимално печалбите, ако един шкаф носи $100 печалба и всяко бюро носи $50?

• 1. Създайте математически модел на задачата и я решете с помощта на симплексния метод.
• 2. Създайте математически модел на двойствения проблем, запишете решението му въз основа на решението на оригиналния.
• 3. Установете степента на недостиг на използваните ресурси и обосновете рентабилността на оптималния план.
• 4. Проучете възможностите за по-нататъшно увеличаване на производствената продукция в зависимост от използването на всеки вид ресурс.
• 5. Оценете осъществимостта на въвеждането на нов вид продукт - рафтове за книги, ако производството на един рафт струва 1 m 2 дъски и аксесоари на стойност $5 и е необходимо да се изразходват 0,25 часа работа на машината и печалбата от продажбата на един рафт е $20.
• 1. Нека изградим математически модел за този проблем:

Нека обозначим с x 1 обема на производството на шкафове и x 2 обема на производството на маси. Нека създадем система от ограничения и целева функция:

Решаваме задачата с помощта на симплексния метод. Нека го напишем в канонична форма:

Нека напишем данните за задачата под формата на таблица:

маса 1

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

Въведение

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

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

1. Постановка на проблема

минимална целева функция

Решете задачата за намиране на минимума на целевата функция за системата от ограничения, зададена от многоъгълника на решение в съответствие с опция № 16 на задачата. Многоъгълникът на решението е показан на фигура 1:

Фигура 1 - Многоъгълник на решенията на проблема

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

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

Графичен метод за решаване на задачи на ЛП;

Алгебричен метод за решаване на задачи на ЛП;

Симплексен метод за решаване на задачи на ЛП;

Метод за намиране на допустимо решение на задачи на ЛП;

Решение на двойствената LP задача;

Метод на разклонения и граници за решаване на цели задачи на ЛП;

Метод на Gomori за решаване на задачи с целочислени LP;

Метод на Балаш за решаване на булеви LP задачи.

Сравнете резултатите от решението, като използвате различни методи и направете подходящи заключения за работата.

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

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

Ориз. 2 Графично решение на задачата LP

Минимална точка

Уравнение на права, минаваща през две точки A1 и A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

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

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

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

Преобразувайте неравенствата така, че отляво да има променливи и свободни членове, а отдясно 0, т.е. така че лявата страна да е по-голяма или равна на нула;

Въведете допълнителни променливи, чийто брой е равен на броя на неравенствата в системата от ограничения;

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

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

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

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

Свободни променливи

св. платно - допълнителен комплект

Условията за неотрицателност са изпълнени, следователно е намерено оптималното решение.

3. Решаване на задача от линейно програмиране с помощта на симплексна таблица

Решение: Нека приведем проблема в стандартна форма за решение, използвайки симплексна таблица.

Нека сведем всички уравнения на системата до формата:

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

В горния ъгъл на всяка клетка от таблицата въвеждаме коефициентите от системата уравнения;

Избираме максималния положителен елемент в ред F, с изключение на това, че това ще бъде общата колона;

За да намерим общия елемент, изграждаме връзка за всички положителни. 3/3; 9/1;- минимално съотношение в ред x3. Следователно – генералният низ и =3 – генералният елемент.

Намираме =1/=1/3. Вкарваме го в долния ъгъл на клетката, където се намира общият елемент;

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

Изберете горните ъгли на общата линия;

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

Останалите клетки от таблицата се попълват като произведение на съответните избрани елементи;

След това изграждаме нова таблица, в която се разменят обозначенията на клетките на елементите на общата колона и ред (x2 и x3);

Стойностите, които преди са били в долния ъгъл, се записват в горния ъгъл на предишния общ ред и колона;

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

4. Решаване на задача от линейно програмиране чрез намиране на допустимо решение

Нека е дадена система от линейни алгебрични уравнения:

Можем да приемем, че всичко е така, в противен случай умножаваме съответното уравнение по -1.

Въвеждаме спомагателни променливи:

Въвеждаме и спомагателна функция

Ние ще минимизираме системата при ограничения (2) и условия.

ПРАВИЛО ЗА НАМИРАНЕ НА ДОПУСТИМО РЕШЕНИЕ: За да намерим допустимо решение на система (1), минимизираме формата (3) при ограничения (2), като xj приемаме за свободни неизвестни и вземаме xj за базисни.

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

min f=0, тогава всички i трябва да са равни на нула. И получените стойности на xj ще представляват допустимо решение на система (1).

min f>0, т.е. оригиналната система няма осъществимо решение.

Изходна система:

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

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

Намерено е допустимо решение на първоначалната задача: x1 = 3, x2 = 3, F = -12. Въз основа на полученото допустимо решение ще намерим оптималното решение на първоначалния проблем, използвайки симплексния метод. За да направим това, ще изградим нова симплексна таблица от таблицата, получена по-горе, като премахнем реда и реда с целевата функция на спомагателния проблем:

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

6. Задача за двойно линейно програмиране

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

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

Решение: Нека приведем системата от ограничения в стандартна форма:

Проблемът, двоен на този, ще има формата:

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

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

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

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

Втора стъпка на симплексния метод

И така, на третата стъпка на симплексния метод беше намерено оптимално решение на задачата за минимизиране със следните резултати: y2 = -7 /8, y1 = -11/8, Ф = 12. За да се намери стойността на целевата функция на двойния проблем, ние заместваме намерените стойности на основните и свободните променливи във функцията за максимизиране:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

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

Fmin = Фmax = -12

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

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

Начален многоъгълник от решения на целочислена програмна задача.

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

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

В резултат на решението беше намерен оптималният план за задачата: x1 = 9/4, x2 = 5/2, F = -41/4. Това решение не отговаря на условието за цяло число, зададено в проблема. Нека разделим полигона на първоначалното решение на две области, като изключим област 3 от него

Модифициран полигон за решение на задача

Нека създадем нови системи от ограничения за получените области на полигона на решението. Лявата област е четириъгълник (трапец). Системата от ограничения за лявата област на многоъгълника на решението е представена по-долу.

Ограничителна система за лявата зона

Дясната област представлява точка С.

Системата от ограничения за района на правилното решение е представена по-долу.

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

В резултат на решението беше намерен оптималният план за задачата: x1 = 3, x2 = 3, F = -12. Този план отговаря на условието, че променливите в проблема са цели числа и може да се приеме като оптимален референтен план за първоначалния проблем с целочислено линейно програмиране. Няма смисъл да търсите правилния регион на решение. Фигурата по-долу показва напредъка на решаването на задача за целочислено линейно програмиране под формата на дърво.

Напредък на решаването на задача с целочислено линейно програмиране с помощта на метода Gomori.

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

Необходимо е да се намери целочислено решение на система (1), което минимизира целевата функция F, като всички коефициенти са цели числа.

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

1) Чрез симплексния метод се определя решението на задача (1), (2), за което отпада изискването за целочислено решение; ако решението се окаже цяло число, тогава ще бъде намерено и желаното решение на целочислената задача;

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

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

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

3) За да конструирате допълнително линейно ограничение, изберете l-тия ред с дробен свободен член и напишете допълнителното ограничение

където и са съответно дробни части от коефициентите и свободни

член. Нека въведем спомагателна променлива в ограничението (3):

Нека определим коефициентите и включени в ограничението (4):

където и са най-близките цели числа отдолу за и съответно.

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

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

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

Решаване на булеви LP задачи по метода на Balazs.

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

Изпълнение на ограниченията

F стойност

Ограничение за филтриране:

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

Решението на проблема с помощта на метода за изчерпателно търсене е 6*25=192 изчислени израза. Решението на задачата с помощта на метода на Балаш е 3*6+(25-3)=47 изчислени израза. Общото намаление на сложността на изчисленията във връзка с решаването на проблема чрез метода на изчерпателно търсене е:

Заключение

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

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

Литература:

1. Ляшченко И.Н. Линейно и нелинейно програмиране / И. Н. Лященко, Е. А. Карагодова, Н. В. Черникова, Н. З. Шор. - К.: “Висше училище”, 1975, 372 с.

2. Указания за попълване на курсов проект по дисциплината „Приложна математика“ за студенти от специалност „Компютърни системи и мрежи“ на редовна и задочна форма на обучение / Съставител: И. А. Балакирева, А. В. Скатков - Севастопол: SevNTU Издателство, 2003. - 15 с.

3. Ръководство за изучаване на дисциплината „Приложна математика”, раздел „Методи за глобално търсене и едномерна минимизация” / Comp. А. В. Скатков, И. А. Балакирева, Л. А. Литвинова - Севастопол: Издателство СевГТУ, 2000. - 31 с.

4. Ръководство за изучаване на дисциплината „Приложна математика” за студенти от специалност „Компютърни системи и мрежи” Секция „Решаване на задачи за целочислено линейно програмиране” за редовна и задочна форма на обучение / Съставители: И. А. Балакирева, А. В. Скатков - Севастопол : Издателство на SevNTU, 2000. - 13 с.

5. Акулич И.Л. Математическо програмиране в примери и задачи:

6. Учебник помощ за студенти по икономика. специалист. университети.-М.: Висш. училище, 1986.- 319 с., ил.

7. Андронов С.А. Оптимални методи за проектиране: Текстове на лекции / SPbSUAP. СПб., 2001. 169 с.: ил.

Подобни документи

Алгоритъм за решаване на задачи от линейното програмиране по симплексния метод. Построяване на математически модел на задача от линейно програмиране. Решаване на задача от линейно програмиране в Excel. Намиране на печалба и оптимален производствен план.

курсова работа, добавена на 21.03.2012 г


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

тест, добавен на 04/05/2016


Теоретични основи на линейното програмиране. Задачи на линейно програмиране, методи за решаване. Анализ на оптималното решение. Решение на задача с едноиндексно линейно програмиране. Постановка на проблема и въвеждане на данни. Изграждане на модел и етапи на решение.

курсова работа, добавена на 12/09/2008


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

курсова работа, добавена на 31.10.2014 г


Изграждане на математически модел с цел получаване на максимална печалба за предприятието, графично решение на проблема. Решаване на проблема с помощта на добавката SOLVER. Анализ на промените в ресурсните запаси. Определяне на границите за изменение на коефициентите на целевата функция.

курсова работа, добавена на 17.12.2014 г


Математическо програмиране. Линейно програмиране. Проблеми с линейно програмиране. Графичен метод за решаване на задачи по линейно програмиране. Икономическа постановка на задачата за линейно програмиране. Изграждане на математически модел.

курсова работа, добавена на 13.10.2008 г


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

тест, добавен на 05/02/2012


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

тест, добавен на 04/11/2012


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

курсова работа, добавена на 17.12.2012 г


Анализ на решението на задача от линейното програмиране. Симплексен метод с използване на симплексни таблици. Моделиране и решаване на LP задачи на компютър. Икономическа интерпретация на оптималното решение на проблема. Математическа постановка на транспортната задача.

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

Помислете за проблем с линейно програмиране с две променливи и:
(1.1) ;
(1.2)
Тук има произволни числа. Задачата може да бъде или да се намери максимумът (max), или да се намери минимумът (min). Системата от ограничения може да съдържа както знаци, така и знаци.

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

Графичният метод за решаване на задача (1) е следният.
Първо начертаваме координатните оси и избираме мащаба. Всяко от неравенствата на системата от ограничения (1.2) определя полуравнина, ограничена от съответната права линия.

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

Правим същото и за останалите неравенства от системата (1.2). По този начин получаваме засенчени полуравнини. Точките от областта на допустимите решения удовлетворяват всички неравенства (1.2). Следователно, графично, областта на възможните решения (ADA) е пресечната точка на всички построени полуравнини. Засенчване на ODR. Това е изпъкнал многоъгълник, чиито лица принадлежат на построените прави. Също така ODF може да бъде неограничена изпъкнала фигура, сегмент, лъч или права линия.

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

Методът може да бъде опростен. Не е нужно да засенчвате всяка полуравнина, но първо изградете всички прави линии
(2)
След това изберете произволна точка, която не принадлежи на нито една от тези линии. Заместете координатите на тази точка в системата от неравенства (1.2). Ако всички неравенства са изпълнени, тогава областта на допустимите решения е ограничена от построените прави линии и включва избраната точка. Засенчваме областта на възможните решения по границите на линиите, така че да включва избраната точка.

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

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

И така, имаме защрихована област на изпълними решения (ADA). Тя е ограничена от начупена линия, състояща се от сегменти и лъчи, принадлежащи на построените прави (2). ODS винаги е изпъкнало множество. То може да бъде или ограничено множество, или неограничено по някои посоки.

Сега можем да търсим екстремума на целевата функция
(1.1) .

За да направите това, изберете произволно число и изградете права линия
(3) .
За удобство на по-нататъшното представяне приемаме, че тази права линия минава през ODR. На този ред целевата функция е постоянна и равна на . такава права линия се нарича линия на функционално ниво. Тази права разделя равнината на две полуравнини. На една полуравнина
.
На друга полуравнина
.
Тоест от едната страна на правата (3) целевата функция нараства. И колкото по-далеч преместваме точката от правата линия (3), толкова по-голяма ще бъде стойността. От другата страна на правата (3) целевата функция намалява. И колкото повече преместваме точката от права линия (3) на другата страна, толкова по-малка ще бъде стойността. Ако начертаем права линия, успоредна на права (3), тогава новата права също ще бъде линия на нивото на целевата функция, но с различна стойност.

По този начин, за да се намери максималната стойност на целевата функция, е необходимо да се начертае права линия, успоредна на права линия (3), колкото е възможно по-далеч от нея в посока на нарастващи стойности и минаваща през поне една точка на ООД. За да се намери минималната стойност на целевата функция, е необходимо да се начертае права линия, успоредна на права линия (3) и колкото е възможно по-далеч от нея в посока на намаляване на стойностите и минаваща през поне една точка от ODD.

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

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

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

Пример за решаване на задача за линейно програмиране с помощта на графичния метод

Задачата

Фирмата произвежда рокли от два модела А и Б. Използват се три вида плат. За изработването на една рокля от модел А са необходими 2 м плат от първи тип, 1 м плат от втори вид, 2 м плат от трети вид. За изработването на една рокля от модел Б са необходими 3 м плат от първи тип, 1 м плат от втори вид, 2 м плат от трети вид. Запасите от плат от първи вид са 21 млн., от втори вид - 10 млн., от трети вид - 16 млн. Пускането на един продукт от тип А носи приход от 400 дена. единици, един продукт тип В - 300 ден. единици

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

Решение

Нека променливите и означават броя на произведените рокли, модели A и B, съответно. Тогава количеството консумирана тъкан от първия тип ще бъде:
(м)
Консумираното количество плат от втория тип ще бъде:
(м)
Консумираното количество плат от третия тип ще бъде:
(м)
Тъй като броят на произведените рокли не може да бъде отрицателен, тогава
И .
Приходите от произведените рокли ще бъдат:
(ден. единици)

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

Решаваме го графично.
Начертаваме координатните оси и .

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 7) и (10.5; 0).

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 10) и (10; 0).

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 8) и (8; 0).

Засенчваме зоната, така че точката (2; 2) да попадне в защрихованата част. Получаваме четириъгълника OABC.

(A1.1) .
В .
В .
Начертайте права линия през точките (0; 4) и (3; 0).

Освен това отбелязваме, че тъй като коефициентите на и на целевата функция са положителни (400 и 300), тя нараства с и нараства. Начертаваме права, успоредна на права (A1.1), доколкото е възможно от нея в посока на нарастване и минаваща през поне една точка от четириъгълника OABC. Такава права минава през точка C. От конструкцията определяме нейните координати.
.

Решението на проблема: ;

Отговор

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

Пример 2

Задачата

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

Решение

Решаваме го графично.
Начертаваме координатните оси и .

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 6) и (6; 0).

Изграждаме права линия.
Оттук.
В .
В .
Начертайте права линия през точки (3; 0) и (7; 2).

Изграждаме права линия.
Изграждаме права линия (ос на абсцисата).

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

Засенчваме зоната по границите на построените линии, така че точка (4; 1) да попадне в защрихованата част. Получаваме триъгълник ABC.

Изграждаме произволна линия на нивото на целевата функция, например,
.
В .
В .
Начертайте права линия през точки (0; 6) и (4; 0).
Тъй като целевата функция нараства с нарастване на и , начертаваме права линия, успоредна на линията на нивото и възможно най-далеч от нея в посока на нарастване и минаваща през поне една точка от триъгълника ABC. Такава права минава през точка C. От конструкцията определяме нейните координати.
.

Решението на проблема: ;

Отговор

Пример без решение

Задачата

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

Решение

Решаваме задачата графично.
Начертаваме координатните оси и .

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 8) и (2.667; 0).

Изграждаме права линия.
В .
В .
Начертайте права линия през точките (0; 3) и (6; 0).

Изграждаме права линия.
В .
В .
Начертайте права линия през точки (3; 0) и (6; 3).

Правите линии са координатните оси.

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

Засенчваме зоната, така че точката (3; 3) да попадне в защрихованата част. Получаваме неограничена област, ограничена от начупената линия ABCDE.

Изграждаме произволна линия на нивото на целевата функция, например,
(A3.1) .
В .
В .
Начертайте права линия през точките (0; 7) и (7; 0).
Тъй като коефициентите на и са положителни, той нараства с увеличаване на и .

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

Търсим минимума. Начертаваме права линия, успоредна на права линия (A3.1) и доколкото е възможно от нея в посока на намаляване и минаваща през поне една точка от областта ABCDE. Такава права минава през точка C. От конструкцията определяме нейните координати.
.
Минимална стойност на целевата функция:

Отговор

Няма максимална стойност.
Минимална стойност
.