Xreferat.com » Рефераты по математике » Побудова математичної моделі задачі лінійного програмування

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

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

з дисципліни

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

Завдання 1


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

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

Діва вироби В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 і В2 відповідно х1 та х2.

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


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


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


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


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


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


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


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


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


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

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

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


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


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


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


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

за умов


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


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

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


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


за умов


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

Завдання 2


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


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


за умов


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


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

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

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

З креслення визначаємо: Побудова математичної моделі задачі лінійного програмування.

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


Завдання 3


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

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


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


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


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

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


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

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

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

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

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


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

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


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


Завдання 4


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

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

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

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

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

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

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


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


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

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


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

функція дорівнює нулю. У даному опорному плані базисними є додаткові змінні х3 та х4, а змінні х1 та х2 є вільними.

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


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


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


Базисні змінні х1 х2 х3 х4 B Базисний розв’язок
Х3 -1 3 1 0 6

(0;0;6;6)

Х4 3 -1 0 1 6
Z -1 -1 0 0 0

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


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

Базисні змінні х1 х2 х3 х4 B Базисний розв’язок
Х2

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

1

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

0 2

(0;2;0;8)

Х4

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

0

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

1 8
Z

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

0

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

0 2

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


Базисні змінні х1 х2 х3 х4 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 у кількостях х1 та х2 відповідно, використовуючи два види ресурсів Р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). Обидва види продукції є рентабельними (оскільки х1 >0 і х2 > 0).

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

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


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

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

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

4. Калихман И.А. Сборник задач по математическому программированию. – М.: Высш.шк., 1975.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: