Реферати українською » Математика » Побудова математичної Моделі Задачі лінійного програмування


Реферат Побудова математичної Моделі Задачі лінійного програмування

>КОНТРОЛЬНАРОБОТА

іздисципліни

„>Математичнепрограмування”


>Завдання 1

 

1)Побудуватиматематичну модельзадачілінійногопрограмування.

2)Звестидану завдання доканонічноговигляду.

>Дівавироби В1 й В2обробляютьсяпослідовно натрьохверстатах.Кожнийвиріб типу В1 >потребує 1 рік. дляобробки напершомуверстаті, 2 рік. – наІІ-му й А рік. – натретьому.

>Кожнийвиріб В2 >потребує дляобробки 2 рік, А рік. й 3 рік.відповідно наІ-му,ІІ-му йІІІ-муверстатах.

Час роботи напершомуверстаті не виненперевищувати10N рік., наІІ-му –15N рік., наІІІ-му – 50 рік.

>Скласти планвиробництва при максимальномуприбутку,якщовідомо, що продажів одноговиробу типу В1 приноситиприбуток 5 грн., а типу В2 – 3 грн.

>Примітка: А=,тобто А=.

>Розв’язання.

 

>Типи

>верстатів

>Затрати години, рік

Час роботи,

 рік

В1 В2
І в 1 2 60
ІІ в 2 А 90
ІІІ в А 3 50
>Прибуток, грн 5 3

1)Математична модельзадачі.

>Позначимокількістьвиробів В1 й В2відповідно x1 та x2.

>Цільовафункція (величинаприбутку), якоїпотрібномаксимізувати


>Спеціальніобмеженнязадачівизначаютьсяобмеженнями години роботиверстатів й нормативами годиниобробкивиробів наверстатах. Приобсягувипускувиробів В1 й В2відповідно x1 та x2 йзаданих нормативи годиниобробки годину роботи Першоговерстатудорівнює

годину роботи іншоговерстату

годину роботитретьоговерстату

>Спеціальніобмеженняєнаступними:

>Загальніобмеженнязадачівитікають ізприродиекономічнихзмінних йполягають у бо смердоті неможуть матірвід’ємнізначення,тобто

Отже маємоматематичну модельзадачі:

за умів

>Словесно завданняформулюється таким чином:знайтизначеннязмінних x1 та x2, котрізадовольняютьзаданійсистеміобмежень йдоставляютьмаксимальнезначенняцільовійфункції Z.

2) Уканонічнійформізадачілінійногопрограмуванняспеціальніобмеженняподаютьсярівностями.Перехід доканонічноїформиздійснюється шляхомвведеннядодаткових (>фіктивних)змінних, котріперетворюютьнерівності нарівності. Уданомувипадку до Першогообмеження вводитисязмінна x3, до іншого – x4, дотретього – x5. >Додатковізміннівводятьсязі знаками „+”,оскількиобмеженнямають тип „”.Математична модельзадачі уканонічнійформі:

за умів


>Завдання 2

>Розв’язати завданнялінійногопрограмуванняграфічним методом

за умів

 

>Розв’язання.

Удекартовійсистемі координат x1Ой2будуємопрямі, котрівизначаютьсянерівностямисистемиобмежень. Цепрямі ; ; . Кожна прямаділитьплощину x1Ой2 надвіполовини, водній із яківиконуєтьсявідповіднанерівністьсистемиобмежень, аіншій невиконується.Півплощини, в яківиконуютьсянерівностісистемиобмеженьпозначеніштриховоюбіляпрямих.Перерізцихпівплощинявляє собою областьприпустимихпланівзадачі. Це –чотирикутникОАВС.

>Цільовафункціявизначаєсімействопаралельнихпрямихліній ізрізнимизначеннями параметра >z. При >z=0 маємопряму , що проходити через вухо координат.Збільшеннюзначення параметра >zвідповідаєпереміщенняпрямоїцільовоїфункції у напрямі,позначеному вектором n+.Безпосередньо ізкреслення видно, що максимальномузначенню параметра >z (максимумуцільовоїфункції призаданихобмеженнях)відповідає точкаприпустимоїобласті, Якаєвершиною УчотирикутникаОАВС (>цеостання точкаприпустимоїобласті, Яканалежитьпрямійцільовоїфункції >z приїїпереміщенні у напрямі збільшення параметра >z).Координати (x1, x2)цієї точкиєшуканимоптимальним планомзадачі.

Зкресленнявизначаємо: .

Отже,оптимальним планомданоїзадачіє ,цільовафункція при цьомунабуває максимальногозначення .

 

>Завдання 3

>Розв’язати системулінійнихрівнянь методомповноговиключення

 >змінних ізвикористаннямрозрахунковихтаблиць.

>Будуєморозрахунковутаблицю йобираємо заведучийелемент а21=1 (утаблицівиділений):

x1

x2

x3

B
3 -2 2 -3
1 4 -1 0
4 -1 4 6

>Перераховуючиелементитаблиці,виключаємо із Першого йтретьогорівнянь (>перший йтретій рядкитаблиці)змінну x1,отримуємо

x1

x2

x3

B
0 -14 5 -3
1 4 -1 0
0 -17 8 6

>Обираємо заведучийелемент а12=-14 (утаблицівиділений) й,виконавшиперерахунок,виключаємозмінну x2 із іншого йтретьогорівнянь.


>Отримуємотаблицю

x1

x2

x3

B
0 1 -5/14 3/14
1 0 3/7 -6/7
0 0 27/14 135/14

>Обираємо заведучийелемент а33=-27/14 (утаблицівиділений) й,виконавшиперерахунок,виключаємозмінну x3 із Першого й іншогорівнянь.Отримуємотаблицю

x1

x2

x3

B
0 1 0 2
1 0 0 -3
0 0 1 5

Зостанньоїтаблиці, Якавідповідаєсистемірівнянь ізповністювиключенимизмінними,знаходиморозв’язоксистемирівнянь:

>Завдання 4

 

1)Розв’язатисимплекс-методом завданнялінійногопрограмування, котра представлена у >Завданні 2.

2)Побудуватидвоїсту завдання дозаданоїзадачілінійногопрограмування.

3)Знайтирозв’язокдвоїстоїзадачі тадатиекономічнуінтерпретаціюотриманогорозв’язку.

>Розв’язання.

1) Завданнялінійногопрограмування:


а)Зводимо завдання доканонічноїформивведеннямдодатковихзмінних x3 та x4.

б) Дана завданнямаєпочатковийопорний план (0;0;6;6;), приякомуцільова

 >функціядорівнює нулю. Уданому опорномупланібазиснимиєдодатковізмінні x3 та x4, азмінні x1 та x2 >євільними.

 в)Запишемоцільовуфункцію увигляді,виразившиїї черезнебазиснізмінні,

р)Будуємосимплекс-таблицю, в якоїзаносимопочатковийопорний план:

>Базиснізмінні

x1

x2

x3

x4

B >Базиснийрозв’язок

Х3

-1 3 1 0 6 (0;0;6;6)

Х4

3 -1 0 1 6
Z -1 -1 0 0 0

>Данийопорний план неєоптимальним,оскільки рядцільовоїфункціїміститьвід’ємнізначення (>коефіцієнти призмінних).Перехід до нового опорного плану,виконуємо шляхомзамінизмінної x3 назмінну x2. >Вибірзмінних длязаміни базисуобумовлюється тім, що узаписізмінної x3 черезнебазиснізмінні (x1 та x2)коефіцієнт призмінній x2маєнайбільшенегативнезначення (-3). Отже,ведучимелементомобираємо а12=3 (утаблицівиділений).

Урезультатіперехункутаблиці,отримуємо другутаблицю:

>Базиснізмінні

x1

x2

x3

x4

B >Базиснийрозв’язок

Х2

1

0 2 (0;2;0;8)

Х4

0

1 8
Z

0

0 2

>Отриманийопорний план неєоптимальним,оскільки рядцільовоїфункціїміститьвід’ємнезначення (а31=). Для переходу до нового базису й,відповідно нового опорного плану,обираємоведучимелементом а21= (>вінлежить устовпчику, дезнаходитьсянегативнийкоефіцієнт увиразіцільовоїфункції, йєпозитивним). Урезультатіперехунку,отримуємонаступнутаблицю:

>Базиснізмінні

x1

x2

x3

x4

B >Базиснийрозв’язок

Х2

0 1

3 (3;3;0;0)

Х1

1 0

3
Z 0 0

6

>Отриманийопорний планєоптимальним,оскільки у рядкуцільовоїфункціїмістять ся лишепозитивнізначення.

Отже,оптимальний планє ,цільовафункція при цьомунабуває максимальногозначення .

>2)Двоїста завданнялінійногопрограмуванняформулюєтьсявідноснодвоїстихзмінних у1, у2 йутворюється шляхомтранспонуванняматрицікоефіцієнтівобмежень,взаємноїзаміникоефіцієнтівцільовоїфункції йвільнихчленівсистемиобмежень йзміни типунерівностей (>= на <= йнавпаки), атакожзміникритеріяоптимізаціяцільовоїфункції напротилежний (>максимізація намінімізацію йнавпаки).

>Двоїста завдання:

>2)Розв’язаннядвоїстоїзадачівиконуємо задопомогоюпроцесораелектроннихтаблиць MS Excel.

>Створюєморобочий лист ізматематичноюмоделлюзадачі,який наведено намалюнку:

>Розв’язанняздійснюється задопомогоюнадбудови Пошук рішення. >Вікнопошукурозв’язку,налаштоване дляданоїзадачіпоказане намалюнку:


>Розв’язокзадачі (>оптимальний пландвоїстоїзадачі)міститься укомірках В2 (>змінна у1),С2 (>змінна у2):

у1 = 0,5; у2:= 0,5

>Вікно MS Excel ізрозв’язкомзадачі:

 

>Економічнаінтерпретаціязадачі.

>Будеморозглядатипряму завдання як завдання прооптимальневикористанняобмеженихресурсів.Підприємствовиготовляє двавидипродукціїП1 йП2 укількостях x1 та x2 >відповідно,використовуючи двавидиресурсівР1 таР2,запаси якіобмежені йстановлять 6одиниць шкірного;норматививитратресурсів наодиницюпродукціїзаданітаблицею

>П1 >П2
>Р1 -1 3
>Р2 3 -1

>Цінареалізаціїодиниці шкірного продуктустановить 1грошовуодиницю.Потрібноскластивиробничий план,якиймаксимізуєдохід підприємства.

>Математична модельпрямоїзадачі:

за умів

>Математична модельдвоїстоїзадачі:

 

>Економічнаінтерпретаціядвоїстоїзадачі:двоїстізмінні у1 та у2 –цеціниресурсівР1 таР2відповідно, й, таким чином, завданняполягає такимцінвикористовуванихресурсів, при якізагальнавартість їхнього якщомінімальною.

>Отриманийоптимальний пландвоїстоїзадачіпоказує, щооптимальноюціноюресурсівР1 таР2є у1 =0,5 та у2 = 0,5грошовиходиниць.

>Обидваресурсивикористовуютьсяповністю йєдефіцитними (>оскільки їхнідвоїстіоцінкибільші нуля у1 >0, у2 > 0).Обидвавидипродукціїєрентабельними (>оскільки x1 >0 й x2 > 0).

>Двоїстіоцінки у1 =0,5 та у2 = 0,5показують, що величина прибутку підприємства (>значенняцільовоїфункціїпрямоїзадачі)збільшиться на 0,5 призбільшеннівеличини наодиницювеличини запасу шкірного ізресурсів.


Списоквикористаноїлітератури

1.АкуличИ.Л. Математичне програмування в прикладах та військово-політичні завдання. – М.:Висш.шк., 1986.

2.Вітлінський В.В.,НаконечнийС.І., Терещенко Т.А.Математичнепрограмування:Навч.–метод.посіб. длясамост.вивч.дисц. – До.:КНЕУ, 2001.

3.КабакЛ.Ф., Суворовський А.А. Математичне програмування. – До.:ИМКВО, 1992.

4.Калихман І.А. Збірник завдань із математичного програмування. – М.:Висш.шк., 1975.

5. Савчук М. В.Лінійнепрограмування:Навч.посібник. – До.:ІПКДСЗУ, 2006.


Схожі реферати:

Навігація