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

Цільова функція визначає сімейство паралельних прямих ліній з різними значеннями параметра z. При z=0 маємо пряму , що проходить через

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

Контрольная работа

Математика и статистика

Другие контрольные работы по предмету

Математика и статистика

Сдать работу со 100% гаранией

 

 

 

 

 

 

 

 

 

 

 

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

з дисципліни

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

Завдання 1

 

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

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

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

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

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

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

Розвязання.

 

Типи

верстатівЗатрати часу, годЧас роботи,

годВ1В2І в1260ІІ в2А90ІІІ вА350Прибуток, грн53

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

Позначимо кількість виробів В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х3B3-22-314-104-146

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

 

х1х2х3B0-145-314-100-1786

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

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

х1х2х3B01-5/143/14103/7-6/70027/14135/14

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

 

х1х2х3B0102100-30015

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

 

 

Завдання 4

 

  1. Розвязати симплекс-методом задачу лінійного програмування, яка представлена у Завданні 2.
  2. Побудувати двоїсту задачу до заданої задачі лінійного програмування.
  3. Знайти розвязок двоїстої задачі та дати економічну інтерпретацію отриманого розвязку.

Розвязання.

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

 

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

 

 

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

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

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

 

 

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

 

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

(0;0;6;6)Х43-1016Z-1-1000

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

 

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

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

 

(0;2;0;8)Х4018Z002

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

 

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

 

(3;3;0;0)Х1103Z006

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

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

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

Двоїста задача:

 

 

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

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

 

 

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

 

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

 

у1 = 0,5; у

Похожие работы

1 2 >