Знайти графічним методоммаксимум цільової функції

F = 2x 1 + 3x 2 ® max

При обмеженнях

Рішенняза допомогою таблиць Excel

Спочатку збудуємо на аркуші Excel рішеннясистеми нерівностей.

Розглянемо першу нерівність.

Побудуємо граничну пряму за двома точками. Пряму позначимо (L1) (або Ряд1). Координати х 2 вважаємо за формулами:

Для побудови вибираємо точкову діаграму

Вибираємо дані для прямої

Змінюємо назву прямої:

Вибираємо макет діаграми. Змінюємо назву осей координат:

Пряма (L1) на графіку:

Вирішення суворої нерівності можна знайти за допомогою єдиної пробної точки, що не належить прямої (L1). Наприклад, за допомогою точки (0; 0)Ï(L1).

0 + 3×0< 18 или 0 < 18 .

Нерівність є правильним, отже рішенням нерівності (1) буде та напівплощина, в якій пробна точка розташована (на малюнку нижче прямої L1).

Потім розв'язуємо нерівність (2) .

Побудуємо граничну пряму 2 по двох точках. Пряму позначимо (L2).

Пряма (L2) на графіку:

Вирішення суворої нерівності 2 можна знайти за допомогою єдиної пробної точки, що не належить прямої (L2). Наприклад, за допомогою точки (0; 0)Ï(L2).

При підстановці координат точки (0; 0) отримуємо нерівність

2×0 + 0< 16 или 0 < 16 .

Нерівність є правильним, отже рішенням нерівності (2) буде та напівплощина, в якій пробна точка розташована (на малюнку нижче прямої L2).

Потім вирішуємо нерівність (3).

Побудуємо граничну пряму за двома точками. Пряму позначимо (L3).

Пряма (L3) на графіку:

Вирішення суворої нерівності 2 можна знайти за допомогою єдиної пробної точки, що не належить прямої (L3). Наприклад, за допомогою точки (0; 0)Ï(L3).

При підстановці координат точки (0; 0) отримуємо нерівність

Нерівність є вірною, отже рішенням нерівності (3) буде та напівплощина, в якій пробна точка розташована (на малюнку нижче прямої L3).

Потім вирішуємо нерівність (4).

Побудуємо граничну пряму за двома точками. Пряму позначимо (L4).

На аркуші Excel додаємо дані

Пряма (L4) на графіку:

Вирішення суворої нерівності 3 х 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

При підстановці координат точки (0; 0) отримуємо нерівність

Нерівність є вірним, отже, рішенням нерівності (4) буде та напівплощина, в якій пробна точка розташована (на малюнку лівіше за пряму L4).

Розв'язанням двох нерівностей (5) та (6)

є перша чверть, обмежена координатними прямими і .

Система нерівностей вирішена. Розв'язанням системи нерівностей (1) – (6) в даному прикладіє опуклий багатокутник у лівому нижньому куті малюнка, обмежений прямими L1, L2, L3, L4 та координатними прямими та . Переконайтеся, що багатокутник вибраний правильно, можна підстановкою пробної точки, наприклад (1; 1) у кожну нерівність вихідної системи. При підстановці точки (1; 1) отримуємо, що це нерівності, зокрема природні обмеження, правильні.

Розглянемо тепер цільову функцію

F = 2x 1 + 3x 2 .

Побудуємо лінії рівня для значень функції F = 0і F = 12 (числові значенняобрані довільно). На аркуші Excel додаємо дані

Лінії рівнів на графіку:

Побудуємо вектор напрямків (або градієнт) (2; 3). Координати вектора збігаються з коефіцієнтами цільової функції F.

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

Будуємо в системі координат х 1 ох 2 прямі

Знаходимо напівплощини, що визначаються системою. Так як нерівності системи виконується для будь-якої точки з відповідної напівплощини, їх достатньо перевірити для будь-якої однієї точки. Використовуємо точку (0; 0). Підставимо її координати у першу нерівність системи. Т.к. , то нерівність визначає напівплощину, що не містить точку (0; 0). Аналогічно визначаємо інші напівплощини. Знаходимо безліч допустимих рішень як загальну частинуотриманих напівплощин - це заштрихована область.

Будуємо вектор та перпендикулярно до нього пряму нульового рівня.

Переміщуючи пряму (5) у напрямку вектора і бачимо, що область максимальна точка буде в точці А перетину прямий (3) і прямий (2). Знаходимо розв'язання системи рівнянь:

Отже, отримали точку (13; 11) і.

Переміщуючи пряму (5) у напрямку вектора і бачимо, що область мінімальна точка буде в точці В перетину прямий (1) і прямий (4). Знаходимо розв'язання системи рівнянь:

Отже, отримали точку (6; 6) і.

2. Меблева фірма виробляє комбіновані шафи та комп'ютерні столики. Їх виробництво обмежене наявністю сировини (високоякісних дощок, фурнітури) і часом роботи верстатів, що їх обробляють. Для кожної шафи потрібно 5 м2 дощок, для столу – 2 м2. На одну шафу витрачається фурнітури на 10 $, на один столик також на 8 $. Фірма може отримувати від своїх постачальників до 600 м2 дощок на місяць та фурнітури на 2000 $. Для кожної шафи потрібно 7 годин роботи верстатів, для столу – 3 години. На місяць можна використовувати всього 840 годин роботи верстатів.

Скільки комбінованих шаф та комп'ютерних столиків фірмі слід випускати на місяць для отримання максимального прибутку, якщо одна шафа приносить 100 $ прибутку, а кожен стіл - 50 $?

• 1. Скласти математичну модельзадачі та вирішити її симплексним методом.
• 2. Скласти математичну модель двоїстих завданьі, записати її рішення з рішення вихідної.
• 3. Встановити ступінь дефіцитності використовуваних ресурсів та обґрунтувати рентабельність оптимального плану.
• 4. Дослідити можливості подальшого збільшення випуску продукції залежно від використання кожного виду ресурсів.
• 5. Оцінити доцільність запровадження нового виду продукції - книжкових полиць, якщо виготовлення однієї полиці витрачається 1 м 2 дошок і фурнітури на 5$,і потрібно витратити 0,25 години роботи верстатів і прибуток від однієї полиці становить 20$.
• 1. Побудуємо математичну модель для цієї задачі:

Позначимо через x 1 – обсяг виробництва шаф, а х 2 – обсяг виробництва столиків. Складемо систему обмежень та функцію мети:

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

Запишемо ці завдання у вигляді таблиці:

Таблиця 1

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

Вступ

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

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

1. Постановка задачі

мінімум цільова функція

Розв'язати задачу знаходження мінімуму цільової функції системи обмежень, заданої багатокутником рішень відповідно до варіантом №16 завдання. Багатокутник рішень представлений малюнку 1:

Малюнок 1 - Багатокутник розв'язання задачі

Система обмежень та цільова функція задачі представлені нижче:

Необхідно вирішити задачу, використовуючи такі методи:

Графічний метод розв'язання задач ЛП;

Алгебраїчний метод розв'язання задач ЛП;

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

Спосіб відшукання припустимого вирішення завдань ЛП;

Розв'язання двоїстої задачі ЛП;

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

Метод Гоморі вирішення цілих задач ЛП;

Метод Балаша розв'язання булевських завдань ЛП.

Порівняти результати рішення різними методами зробити відповідні висновки щодо роботи.

2. Графічне рішеннязадачі лінійного програмування

Графічний метод розв'язання задач лінійного програмування застосовується у випадках, коли кількість невідомих вбирається у трьох. Зручний для якісного дослідженнявластивостей рішень і застосовується разом з іншими методами (алгебраїчним, гілок та кордонів тощо). Ідея методу полягає в графічному розв'язанні системи лінійних нерівностей.

Рис. 2 Графічне розв'язання задачі ЛП

Точка мінімуму

Рівняння прямої через дві точки A1 і A2:

АВ: (0; 1); (3;3)

НД: (3;3); (4;1)

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

EА: (1; 0); (0;1)

ЦФ: (0; 1); (5;2)

при обмеженнях:

Розв'язання задачі лінійного програмування алгебраїчним симплекс-методом

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

Перетворити нерівності в такий спосіб, щоб зліва перебували змінні і вільні члени, а праворуч - 0 тобто. щоб ліва частина була більшою або рівною нулю;

Ввести додаткові змінні, число яких дорівнює числу нерівностей у системі обмежень;

Ввівши додаткові обмеженняна невід'ємність доданих змінних, замінити знаки нерівностей на знаки суворої рівності.

При розв'язанні задачі ЛП методом алгебридодається умова: цільова функція має прагнути до мінімуму. Якщо ця умова не виконується, необхідно відповідним чином перетворити цільову функцію (помножити на -1) та вирішувати задачу мінімізації. Після того, як рішення знайдено, підставити значення змінних у вихідну функцію та порахувати її значення.

Розв'язання задачі при використанні методу алгебри вважається оптимальним, коли значення всіх, базисних змінних - неотрицательно, і коефіцієнти при вільних змінних у рівнянні цільової функції також неотрицательны. Якщо ці умови не виконуються, необхідно перетворити систему нерівностей, висловлюючи одні змінні через інші (змінюючи вільні та базисні змінні), домогтися виконання вищенаведених обмежень. Значення всіх вільних змінних вважається рівним нулю.

Алгебраїчний метод вирішення задач лінійного програмування є одним із самих ефективних методівпід час вирішення завдань невеликий розмірності вручну т.к. не вимагає великої кількостіарифметичних обчислень. Машинна реалізація цього складніше, ніж, наприклад, для симплекс-метода, т.к. Алгоритм рішення алгебраїчним методом є певною мірою евристичним і ефективність рішення багато в чому залежить від особистого досвіду.

Вільних змінних

св.пер. - Дод. набір

Умови не негативності виконані, отже, знайдено оптимальне рішення.

3. Розв'язання задачі лінійного програмування з використанням симплекс-таблиці

Рішення: Наведемо завдання до стандартного виду для вирішення за допомогою симплекс-таблиці.

Усі рівняння системи наведемо до виду:

Будуємо симплекс-таблицю:

У верхній куткожної клітини таблиці вписуємо коефіцієнти із системи рівнянь;

Вибираємо максимальний позитивний елемент у рядку F, крім цього буде генеральний стовпець;

Для того, щоб знайти генеральний елемент, будуємо відношення для всіх позитивних. 3/3; 9/1; - мінімальне співвідношення у рядку x3. Отже – генеральний рядок і = 3 – генеральний елемент.

Знаходимо =1/=1/3. Вносимо у нижній кут клітини, де знаходиться генеральний елемент;

У всі незаповнені нижні кути генерального рядка вносимо добуток значення у верхньому куті клітини;

Виділяємо верхні кути генерального рядка;

У всі нижні кути генерального стовпця заносимо добуток значення у верхньому кутку на - і виділяємо отримані значення;

Інші клітини таблиці заповнюються як твори відповідних виділених елементів;

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

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

У верхній кут інших клітин записується сума значень верхнього та нижнього кута цих клітин у попередній таблиці

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

Нехай дана система лінійних рівнянь алгебри:

Можна припустити, що все, інакше множимо відповідне рівнянняна 1.

Вводимо допоміжні змінні:

Вводимо також допоміжну функцію

Мінімізуватимемо систему при обмеженнях (2) та умовах.

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

При вирішенні задачі симплекс-метод можуть виникнути два випадки:

min f=0, тоді все i повинні бути рівними нулю. А значення, що вийшло, xj будуть становити допустиме рішенняСистеми (1).

min f>0, тобто. вихідна система немає допустимого рішення.

Вихідна система:

Використовується умова завдання попередньої теми.

Внесемо додаткові змінні:

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

Аналізуючи побудовану симплекс-таблицю, бачимо, що оптимальне рішення для вихідної задачі вже знайдено (елементи у рядку, що відповідає цільовій функції, негативні). Таким чином, допустиме рішення, знайдене при вирішенні допоміжного завдання, збігається з оптимальним рішенням вихідного завдання:

6. Подвійне завдання лінійного програмування

Вихідна система обмежень та цільова функція задачі показані на малюнку нижче.

при обмеженнях:

Рішення: Наведемо систему обмежень до стандартного вигляду:

Завдання, двоїсте даної мати вигляд:

Розв'язання двоїстої задачі виконуватиметься простим симплекс-методом.

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

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

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

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

Побудуємо вихідну симплекс-таблицю на вирішення двоїстої завдання ЛП.

Другий крок симплекс-методу

Отже, на третьому кроці симплекс-метода знайдено оптимальне рішення задачі мінімізації з наступними результатами: y2 = -7 /8, y1 = -11/8, Ф = 12. Для того, щоб знайти значення цільової функції двоїстої задачі, підставимо знайдені значення базисних та вільних змінних у функцію максимізації:

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

Так як значення цільової функції прямої та двоїстої задач збігаються, рішення прямої задачі знайдено і дорівнює 12.

Fmin = Фmax = -12

7. Розв'язання задачі цілісного лінійного програмування методом «гілок та кордонів»

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

Вихідний багатокутник розв'язання задачі цілісного програмування.

Для перетвореного багатокутника рішень збудуємо нову системуобмежень.

Запишемо систему обмежень як рівностей, на вирішення алгебраїчним методом.

В результаті рішення знайдено оптимальний план задачі: х1 = 9/4, х2 = 5/2, F = -41/4. Це рішення не відповідає умові цілісності, поставленої в задачі. Розіб'ємо вихідний багатокутник рішень на дві області, виключивши з нього область 3

Змінений багатокутник розв'язання задачі

Складемо нові системи обмежень для областей багатокутника рішень, що утворилися. Ліва область є чотирикутником (трапецією). Система обмежень для лівої області багатокутника рішень представлена ​​нижче.

Система обмежень для лівої області

Права область є точку З.

Система обмежень для правої галузі рішень представлена ​​нижче.

Нові системи обмежень являють собою дві допоміжні завдання, які необхідно вирішити незалежно одна від одної. Розв'яжемо задачу цілого програмування для лівої області багатокутника рішень.

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

Хід вирішення цілої задачі лінійного програмування методом Гоморі.

Багато практичних додатках представляє великий інтерес завдання цілісного програмування, у якій дана система лінійних нерівностей і лінійна форма

Потрібно знайти ціле рішення системи (1), яке мінімізує цільову функцію F, причому, всі коефіцієнти - цілі.

Один із методів розв'язання задачі цілісного програмування запропонований Гоморі. Ідея методу полягає у використанні методів безперервного лінійного програмування, зокрема симплекс-метода.

1) Визначається за допомогою симплекс-метода розв'язання задачі (1), (2), у якої знято вимогу цілісності розв'язання; якщо рішення виявляється цілою, то шукане рішення цілісної задачі буде також знайдено;

2) В іншому випадку, якщо деяка координата - не ціла, отримане рішення задачі перевіряється на можливість існування цілого рішення (наявність цілих точок у допустимому багатограннику):

якщо в будь-якому рядку з дробовим вільним членом, всі інші коефіцієнти виявляться цілими, то в допустимому багатограннику немає цілих, точок і завдання цілісного програмування рішення не має;

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

3) Для побудови додаткового лінійного обмеження, вибираємо l-ту рядок з дрібним вільним членом і записуємо додаткове обмеження

де і - відповідно дробові частини коефіцієнтів та вільного

члена. Введемо до обмеження (3) допоміжну змінну:

Визначимо коефіцієнти та, що входять в обмеження (4):

де і - найближчі цілі знизу для та відповідно.

Гоморі довів, що кінцева кількість подібних кроків призводить до такого завдання лінійного програмування, вирішення якого буде цілим і, отже, шуканим.

Рішення: Наведемо систему лінійних обмежень та функцію мети до канонічної форми:

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

Вирішення булевських завдань ЛП методом Балаша.

Скласти самостійно варіант для задачі цілочисельного лінійного програмування з булевськими змінними з урахуванням наступних правил: завдання використовується не менше 5 змінних, не менше 4 обмежень, коефіцієнти обмежень і цільової функції вибираються довільно, але таким чином, щоб система обмежень була спільна. Завдання полягає в тому, щоб вирішити ЗЦЛП з булевськими змінними, використовуючи алгоритм Балаша та визначити зниження трудомісткості обчислень щодо вирішення задачі методом повного перебору.

Виконання обмежень

Значення F

Фільтруюче обмеження:

Визначення зниження трудомісткості обчислень

Розв'язання задачі методом повного перебору становить 6*25=192 обчислені вирази. Розв'язання задачі методом Балаша становить 3*6+(25-3)=47 обчислених виразів. Разом зниження трудомісткості обчислень стосовно вирішення задачі методом повного перебору становить.

Висновок

Процес проектування інформаційних систем, що реалізують нову інформаційну технологію, постійно вдосконалюється. У центрі уваги інженерів-системотехніків виявляються все більш складні системи, що ускладнює використання фізичних моделей та підвищує значущість математичних моделей та машинного моделювання систем. Машинне моделювання стало ефективним інструментом дослідження та проектування складних систем. Актуальність математичних моделей безперервно зростає через їх гнучкість, адекватність реальним процесам, невисоку вартість реалізації з урахуванням сучасних ПЕОМ. Все більші можливості надаються користувачеві, тобто фахівця з моделювання систем засобами обчислювальної техніки. Особливо ефективним є застосування моделювання на ранніх етапах проектування автоматизованих систем, коли ціна помилкових рішень найбільша.

Сучасні обчислювальні засоби дозволили суттєво збільшити складність використовуваних моделей при вивченні систем, з'явилася можливість побудови комбінованих, аналітико-імітаційних моделей, що враховують усе різноманіття факторів, що мають місце в реальних системах, тобто використання моделей, адекватніших досліджуваним явищам.

Література:

1. Лященко І.М. Лінійне та нелінійне програмування / І.М.Лященко, Є.А.Карагодова, Н.В.Чернікова, Н.З.Шор. – К.: «Вища школа», 1975, 372 с.

2. Методичні вказівки для виконання курсового проекту з дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» денної та заочної форм навчання / Упоряд.: І.А.Балакірєва, А.В.Скатков- Севастополь: Вид-во СевНТУ , 2003. – 15 с.

3. Методичні вказівки щодо вивчення дисципліни «Прикладна математика», розділ «Методи глобального пошуку та одновимірної мінімізації» / Упоряд. А.В.Скатков, І.А.Балакірєва, Л.А.Литвинова - Севастополь: Вид-во ПівнГТУ, 2000. - 31с.

4. Методичні вказівки для вивчення дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» Розділ «Рішення завдань цілочисельного лінійного програмування» денної та заочної форм навчання / Упоряд.: І.А.Балакірєва, А.В.Скатков – Севастополь : Вид-во СевНТУ, 2000. – 13 с.

5. Акуліч І.Л. Математичне програмування в прикладах та задачах:

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

7. Андронов С.А. Методи оптимального проектування: Текст лекцій / СПбГУАП. СПб., 2001. 169 с.: іл.

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

Алгоритм розв'язання задач лінійного програмування симплекс-методом. Побудова математичної моделі задачі лінійного програмування. Розв'язання задачі лінійного програмування в Excel. Знаходження прибутку та оптимального плану випуску продукції.

курсова робота , доданий 21.03.2012


Графічний розв'язок задач. Складання математичної моделі. Визначення максимального значення цільової функції. Рішення симплексним методом зі штучним базисом канонічного завдання лінійного програмування. Перевіряє оптимальність рішення.

контрольна робота , доданий 05.04.2016


Теоретична основа лінійного програмування. Завдання лінійного програмування, методи розв'язання. Аналіз раціонального рішення. Вирішення одноіндексної задачі лінійного програмування. Постановка задачі та введення даних. Побудова моделі та етапи рішення.

курсова робота , доданий 09.12.2008


Побудова математичної моделі. Вибір, обґрунтування та опис методу рішень прямого завдання лінійного програмування симплекс-методом, з використанням симплексної таблиці. Складання та розв'язання двоїстої задачі. Аналіз моделі на чутливість.

курсова робота , доданий 31.10.2014


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

курсова робота , доданий 17.12.2014


Математичне програмування. Лінійне програмування. Завдання лінійного програмування. Графічний метод розв'язання задачі лінійного програмування. Економічна постановка задачі лінійного програмування. Побудова математичної моделі.

курсова робота , доданий 13.10.2008


Розв'язання задачі лінійного програмування графічним методом, його перевірка у MS Excel. Аналіз внутрішньої структури розв'язання задачі у програмі. Оптимізація плану виробництва. Розв'язання задачі симплекс-методом. Багатоканальна система масового обслуговування.

контрольна робота , доданий 02.05.2012


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

контрольна робота , доданий 11.04.2012


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

курсова робота , доданий 17.12.2012


Аналіз розв'язання задачі лінійного програмування. Симплексний метод із використанням симплекс-таблиць. Моделювання та розв'язання завдань ЛП на ЕОМ. Економічна інтерпретація оптимального розв'язання задачі. Математичне формулювання транспортного завдання.

ТЕМА: ЛІНІЙНЕ ПРОГРАМУВАННЯ

ЗАВДАННЯ 2.А. Розв'язання задачі лінійного програмування графічним методом

Увага!

Це ОЗНАКОМНА ВЕРСІЯ роботи №2073, ціна оригіналу 200 рублів. Оформлена у програмі Microsoft Word.

Оплата. Контакти.

Варіант 7. Знайти максимальне та мінімальне значеннялінійної функціїФ = 2x 1 - 2 · x 2при обмеженнях: x 1 + х 2 ≥ 4;

- х 1 + 2 · х 2 ≤ 2;

x 1 + 2 · х 2 ≤ 10;

х i ≥ 0, i = 1,2.

Рішення:

Замінивши умовно знаки нерівностей на знаки рівностей, отримаємо систему рівнянь x1 + x2 = 4;

- Х1 + 2 · х2 = 2;

x1 + 2 · х2 = 10.

Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їхню загальну частину – область допустимих рішень ОДР – чотирикутник MNPQ.

Мінімальне значення функці-

ції - у точці М(2; 2)

Ф min = 2 · 2 - 2 · 2 = 0.

Максимальне значення досягається в точці N (10; 0),

Ф max = 2 · 10 - 2 · 0 = 20.

Варіант 8. Знайти максимальне та мінімальне значення

лінійної функції Ф = х 1 + х 2

при обмеженнях: x 1 - 4 · х 2 - 4 ≤ 0;

3 · х 1 - х 2 ≥ 0;

x 1 + х 2 - 4 ≥ 0;

х i ≥ 0, i = 1,2.

Рішення:

Замінивши умовно знаки нерівностей на знаки рівностей, отримаємо систему рівнянь x1 - 4 · х2 = 4;

3 · х1 - х2 = 0;

Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їхню загальну частину – область допустимих рішень ОДР – необмежений багатокутник MNPQ.

Мінімальне значення функці-

ції – на прямій NP, наприклад

у точці Р(4; 0)

Ф min = 4 + 0 = 4.

ОДР зверху не обмежена, отже, Ф max = + ∞.

Варіант 10. Знайти максимальне та мінімальне значення

лінійної функції Ф = 2 · x 1 - 3 · x 2

при обмеженнях: x 1 + 3 x 2 ≤ 18;

2 · х 1 + х 2 ≤ 16;

х 2 ≤ 5;

х i ≥ 0, i = 1,2.

Замінивши умовно знаки нерівностей знаками рівностей, отримаємо систему рівнянь

x 1 + 3 · x 2 = 18 (1);

2 · х 1 + х 2 = 16 (2);

3 · х 1 = 21 (4).

Побудуємо за цими рівняннями прямі, потім відповідно до знаків нерівностей виділимо напівплощини та отримаємо їхню загальну частину — область допустимих рішень ОДР – багатокутник MNPQRS.

Побудуємо вектор Г(2; -3) і через початок координат проведемо лінію рівня- Пряму.

Переміщуємо лінію рівня у напрямі, значення Ф у своїй зростає. У точці S(7; 0) цільова функція досягає максимуму Ф max =2·7–3·0= = 14. Переміщуємо лінію рівня у напрямку, значення Ф при цьому зменшується. Мінімальне значення функції - у точці N(0; 5)

Ф min = 2 · 0 - 3 · 5 = -15.

ЗАВДАННЯ 2.B. Розв'язання задачі лінійного програмування

аналітичним симплексним методом

Варіант 7. Мінімізувати цільову функцію Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

при обмеженнях: x 1 + x 4 +6 x 6 = 9,

3 · x 1 + x 2 - 4 · x 3 + 2 · x 6 = 2,

x 1 + 2 · x 3 + x 5 + 2 · x 6 = 6.

Рішення:

Кількість невідомих n=6, кількість рівнянь m=3. Отже, r = n-m = 3 невідомих можна прийняти як вільні. Виберемо x 1 , x 3 та x 6 .

Базисні змінні x 2 x 4 і x 5 виразимо через вільні і приведемо систему до одиничного базису

х 2 = 2 - 3 · x 1 + 4 · x 3 - 2 · x 6

x 4 = 9 - x 1 - 6 · x 6 (*)

x 5 = 6 - x 1 - 2 · x 3 - 2 · x 6

Цільова функція матиме вигляд:

Ф = x 1 - 2 + 3 · x 1 - 4 · x 3 + 2 · x 6 + x 3 + 9 - x 1 - 6 · x 6 +6 - x 1 - 2 · x 3 - 2 · x 6 - x 6 =

13 + 2 · x 1 - 5 · x 3 - 7 · x 6

Покладемо x 1 = x 3 = x 6 = 0, причому базисні змінні приймуть значення x 2 = 2; x4 = 9; x 5 = 6, тобто перше допустиме рішення (0; 2; 0; 9; 6; 0), цільова функція Ф 1 = 13.

Змінні х 3 і х 6 входять до цільової функції з негативними коефіцієнтами, отже, зі збільшенням їх значень величина Ф буде зменшуватися. Візьмемо, наприклад, х 6 . З одного рівняння системи (*) видно, що збільшення значення x 6 можливе до x 6 = 1 (поки x 2 ³ 0). При цьому x 1 і x 3 зберігають значення, що дорівнюють нулю. Тепер в якості базисних змінних прийомів х 4, х 5, х 6, як вільні - х 1, х 2, х 3. Висловимо нові базисні змінні через нові вільні. Отримаємо

х 6 = 1 – 3/2·x 1 – 1/2·x 2 + 2·x 3

x 4 = 3 + 8 · x 1 + 3 · x 2 - 12 · x 3

x 5 = 4 + 2 · x 1 + x 2 - 6 · x 3

Ф = 6 + 25/2 · x 1 + 7/2 · x 2 - 19 · x 3

Надамо вільним змінним нульові значення, тобто x 1 = x 2 = x 3 = 0, при цьому х 6 = 1, x 4 = 3, x 5 = 4, тобто, третє допустиме рішення (0; 0; 0; 3; 4; 1). У цьому Ф 3 = 6.

Змінна x 3 входить до цільової функції з негативним коефіцієнтом, отже збільшення x 3 щодо нульового значення призведе до зниження Ф. З 2-го рівняння видно, що x 3 може зростати до 1/4, з 3-го рівняння – до 2/3 . Друге рівняння критичніше. Змінну x 3 переведемо до базисних, x 4 — до числа вільних.

Тепер як нові вільні змінні приймемо x 1 , x 2 і x 4 . Виразимо через них нові базисні змінні x3, x5, x6. Отримаємо систему

х 3 = 1/4 + 2/3 · x 1 + 1/4 · x 2 - 1/12 · x 4

x 5 = 5/2 - 2 · x 1 - 1 / 2 · x 2 + 1 / 2 · x 4

x 6 = 3/2 - 1/6 · x 1 - 1/6 · x 4

Цільова функція набуде вигляду

Ф = 5/4 - 1/6 · x 1 - 5/4 · x 2 + 19/12 · x 4

Змінні х 1 і х 2 входять до цільової функції з негативними коефіцієнтами, отже, зі збільшенням їх значень величина Ф буде зменшуватися. Візьмемо, наприклад, х2. З 2-го рівняння системи видно, що збільшення значення x 2 можливе до x 2 = 5 (поки x 5 ³ 0). При цьому x 1 та x 4 зберігають нульові значення, значення інших змінних дорівнюють x 3 = 3/2; x 5 = 0, x 6 = 3/2, тобто четверте допустиме рішення (0; 5; 3/2; 0; 0; 3/2). У цьому Ф 4 = 5/4.

Тепер як нові вільні змінні приймемо x 1 , x 4 і x 5 . Виразимо через них нові базисні змінні x2, x3, x6. Отримаємо систему

х 2 = 5 - 4 · x 1 + x 4 - 2 · x 5

x 3 = 3/2 - 1/3 · x 1 + 1/6 · x 4 - 1/2 · x 5

x 6 = 3/2 - 1/6 · x 1 - 1/6 · x 4

Цільова функція набуде вигляду

Ф = - 5 + 29/6 · x 1 + 1/3 · x 4 + 5/2 · x 5

Коефіцієнти при обох змінних у вираженні для Ф позитивні, отже, подальше зменшення величини Ф неможливе.

Тобто мінімальне значення Ф min = - 5, останнє допустиме рішення (0; 5; 3/2; 0; 0; 3/2) є оптимальним.

Варіант 8. Максимізувати цільову функцію Ф = 4 x 5 + 2 x 6

при обмеженнях: x1+x5+x6=12;

x 2 + 5 · x 5 - x 6 = 30;

x 3 + x 5 - 2 · x 6 = 6;

2 · x 4 + 3 · x 5 - 2 · x 6 = 18;

Рішення:

Кількість рівнянь дорівнює 4, кількість невідомих - 6. Отже r = n - m = 6 - 4 = 2 змінних можемо вибрати як вільні, 4 змінні - як базисні. Як вільні виберемо x 5 і x 6 , як базисні - x 1 , x 2 , x 3 , x 4 . Висловимо базисні змінні через вільні та наведемо систему рівнянь до одиничного базису

x 1 = 12 - x 5 - x 6;

x 2 = 30 - 5 · x 5 + x 6;

x 3 = 6 - x 5 + 2 · x 6;

x 4 = 9 - 3/2 · x 5 + x 6;

Цільову функцію запишемо у вигляді Ф = 4 x 5 + 2 x 6 . Надамо вільним змінним нульові значення x 5 = x 6 = 0. При цьому базисні змінні приймуть значення x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9, тобто, отримаємо перше допустиме рішення (12, 30 , 6, 9, 0,) та Ф 1 = 0.

У цільову функцію обидві вільні змінні входять з позитивними коефіцієнтами, тобто, можливо подальше збільшення Ф. Переведемо, наприклад, x 6 до базисних. З рівняння (1) видно, що x 1 = 0 при x 5 = 12, (2) ÷ (4) x 6 входить з позитивними коефіцієнтами. Перейдемо до нового базису: базисні змінні - x 6, x 2, x 3, x 4, вільні - x 1, x 5. Виразимо нові базисні змінні через нові вільні

х 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 · x 5;

x 3 = 30 - 2 · x 1 - 3 · x 5;

x 4 = 21 - x 1 - 5/2 · x 5;

Цільова функція набуде вигляду Ф = 24 - 2 · x 1 + 2 · x 5;

Надамо вільним змінним нульові значення x 1 = x 5 = 0. При цьому базисні змінні приймуть значення x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21, тобто, отримаємо друге допустиме рішення (0, 42 , 30, 21, 0, 12) та Ф 2 = 24.

У цільову функцію x 5 входить з позитивним коефіцієнтом, тобто, можливо подальше збільшення Ф. Перейдемо до нового базису: базисні змінні - x 6 x 5 x 3 x 4 вільні x 1 x 2. Виразимо нові базисні змінні через нові вільні

х 6 = 5 - 5/6 · x 1 + 1/6 · x 2;

x 5 = 7 - 1/6 · x 1 - 1/6 · x 2;

x 3 = 9 - 3/2 · x 1 + 1/2 · x 2;

x 4 = 7/2 - 7/12 · x 1 + 5/12 · x 5;

Цільова функція набуде вигляду Ф = 38 – 7/2·x 1 – 1/3·x 2 ;

Надамо вільним змінним нульові значення x 1 = x 2 = 0. При цьому базисні змінні приймуть значення x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/2, тобто отримаємо третє допустиме рішення Х 3 = (0, 0, 9, 7/2, 7, 5) та Ф 3 = 38.

У цільову функцію обидві змінні входять з негативними коефіцієнтами, тобто подальше збільшення Ф неможливе.

Отже, останнє допустиме рішення є оптимальним, тобто Х опт = (0, 0, 9, 7/2, 7, 5) та Ф max = 38.

Варіант 10. Максимізувати цільову функцію Ф = х 2 + х 3

при обмеженнях: x 1 - x 2 + x 3 = 1,

x 2 - 2 · х 3 + х 4 = 2.

Рішення:

Система рівнянь - обмежень спільна, тому що ранги матриці системи рівнянь і розширеної матриці однакові і рівні 2. Отже, дві змінні можна прийняти як вільні, дві інші змінні - базисні - виразити лінійно через дві вільні.

Приймемо за вільні змінні x 2 і х 3. Тоді базисними будуть змінні х 1 і х 2, які виразимо через вільні

x 1 = 1 + x 2 - x 3; (*)

x 4 = 2 - x 2 + 2 · x 3;

Цільова функція вже виражена через x 2 і x 3 тобто Ф = x 2 + x 3 .

При х 2 =0 і х 3 =0 базисні змінні дорівнюватимуть х 1 = 1, х 4 = 2.

Маємо перше допустиме рішення Х 1 = (1, 0, 0, 2), причому Ф 1 = 0.

Збільшення Ф можливе при збільшенні, наприклад, значення х 3 який входить у вираз для Ф з позитивним коефіцієнтом (x 2 при цьому залишається рівним нулю). У перше рівняння системи (*) видно, що х 3 можна збільшувати до 1 (з умови х 1 0), тобто це рівняння накладає обмеження на збільшення значення х 3 . Перше рівняння системи (*) є вирішальним. На основі цього рівняння переходимо до нового базису, помінявши х 1 і 3 місцями. Тепер базовими змінними будуть х 3 і х 4, вільними - х 1 і х 2 . Виразимо тепер х 3 і х 4 через х 1 і х 2 .

Отримаємо: x 3 = 1 - x 1 + x 2; (**)

x 4 = 4 - 2 · x 1 + x 2;

Ф = х 2 + 1 - х 1 + х 2 = 1 - x 1 + 2 · x 2

Прирівнявши нулю вільні змінні, отримаємо друге допустиме базисне рішення Х 2 = (0; 0; 1; 4), у якому Ф 2 =1.

Збільшення Ф можливе зі збільшенням х 2 . Збільшення ж х 2 , судячи з останньої системи рівнянь (**), не обмежена. Отже, Ф прийматиме все більші позитивні значення, тобто Ф мах = + ¥.

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

ЗАВДАННЯ 2.D. Скласти завдання, подвійне до наведеного

вихідної задачі.

Варіант 7. Максимізувати цільову функцію Ф = 2× х 1 - х 4

при обмеженнях: х 1 + х 2 = 20,

х 2 + 2× х 4 ≥ 5,

х 1 + х 2 + х 3 ≤ 8,

х i ≥ 0 (i = 1, 2, 3, 4)

Рішення:

Наведемо систему обмежень до єдиного, наприклад, канонічного виду, ввівши додаткові змінні у 2-е та 3-е рівняння

х 1 + х 2 = 20,

х 2 + 2 × х 4 - х 5 = 5,

- х 1 + х 2 + х 3 + х 6 = 8.

Отримали несиметричне завдання 2 типу. Подвійне завдання матиме вигляд:

Мінімізувати цільову функцію F = 20 × у 1 + 5 × y 2 + 8 × y 3

при y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y 2 ≥ 0,

y 3 ≥ 0.

Варіант 8. Максимізувати цільову функцію Ф = х 2 - х 4 - 3× х 5

при обмеженнях: х 1+2× х 2 - х 4 + х 5 = 1,

— 4 × х 2 + х 3 + 2× х 4 - х 5 = 2,

3 × х 2 + х 5 + х 6 = 5,

x i ≥ 0, (i = 1, 6)

Рішення:

Маємо вихідне завдання на максимізацію із системою обмежень у вигляді рівнянь, тобто пара двоїстих завдань має несиметричний вигляд 2-го типу, математична модель яких у матричній формі має вигляд:

Вихідне завдання: Подвійне завдання:

Ф = С × Х max F = B Т × Y min

при А × Х = В при A Т × Y ≥ С Т

У вихідному завданні матриця-рядок коефіцієнтів при змінних у цільовій функції має вигляд С = (0; 1; 0; -1; -3; 0),

матриця-стовпець вільних членів та матриця коефіцієнтів при змінних у системі обмежень мають вигляд

В = 2, А = 0 - 4 1 2 -1 0

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

0 1 0 0 В Т = (1; 2; 5)

A T = -1 2 0 С Т = -1

Подвійне завдання запишеться у такому вигляді:

знайти мінімальне значення цільової функції F = y 1 + 2 × y 2 + 5 × y 3

при обмеженнях y 1 ≥ 0,

2× y 1 - 4 × y 2 + 3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Варіант 10. Мінімізувати функцію Ф = х1+х2+х3

при обмеженнях: 3× х 1 + 9× х 2 + 7× х 3 ≥ 2,

6 × х 1 + 4 · х 2 + 5× х 3 ≥ 3,

8 × х 1 + 2 · х 2 + 4× х 3 ≥ 4,

Рішення:

Маємо вихідне завдання на мінімізацію із системою обмежень у вигляді нерівностей, тобто пара двоїстих завдань має симетричний вигляд 3-го типу, математична модель яких у матричній формі має вигляд:

Вихідне завдання Подвійне завдання

Ф = С × Х min F = B Т × Y max

при А × Х ≥ В при A Т × Y ≤ З Т

Х ≥ 0 Y ≥ 0

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

С = (1; 1; 1), В = 3, А = 6 4 5

Знайдемо матриці двоїстої задачі

T = (2; 3; 4) T = 3 A T = 9 4 2

Подвійне завдання формулюється у вигляді:

Максимізувати цільову функцію F = 2y 1 + 3y 2 + 4y 3

при обмеженнях 3 × y 1 + 6 × y 2 + 8 × y 3 ≤ 1,

9× y 1 + 4 × y 2 + 2 × y 3 ≤ 1,

7× y 1 + 5 × y 2 + 4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ЗАВДАННЯ 2.С. Розв'язання задачі лінійного програмування за допомогою симплексних таблиць.

Варіант 7. Максимізувати цільову функцію Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

при обмеженнях: 2 · x 1 + 3 · x 2 - x 3 + 2 · x 4 ≤ 4,

x 1 - 2 · x 2 + 5 · x 3 - 3 · x 4 ≥ 1,

4 · x 1 + 10 · x 2 +3 · x 3 + x 4 ≤ 8.

Рішення:

Наведемо систему обмежень до канонічного виду

2 · x 1 + 3 · x 2 - x 3 + 2 · x 4 + z 1 = 4, (1)

x 1 - 2 · x 2 + 5 · x 3 - 3 · x 4 - z 2 = 1, (2)

4 · x 1 + 10 · x 2 +3 · x 3 + x 4 + z 3 = 8. (3)

Маємо систему 3-х рівнянь із 7-ма невідомими. Виберемо в якості базисних 3 змінних x 1, z 1, z 3, як вільні - x 2, x 3, x 4, z 2, виразимо через них базисні змінні.

З (2) маємо x 1 = 1 + 2 · x 2 - 5 · x 3 + 3 · x 4 + x 6

Підставимо в (1) та (3), отримаємо

x 1 - 2 · x 2 + 5 · x 3 - 3 · x 4 - z 2 = 1,

z 1 + 7 · x 2 - 11 · x 3 + 8 · x 4 + 2 · z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 · x 2 + 7 · x 3 - 8 · x 4 - 2 · z 2 = 2.

Складемо симплекс-таблицю

I ітерація Таблиця 1

Базисн. перем.	Свобод. перем.
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
Ф	2	0	— 3	7	— 8	0	— 2	0		1

Х 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

ІІ ітерація Таблиця 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Ф	4	0	4	— 4	0	1	0	0		32/7

Х 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

ІІІ ітерація Таблиця 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Ф	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

Х 3 = (1; 0; 6/7; 10/7; 0; 0; 0) Ф 3 = 52/7.

IV ітерація Таблиця 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Ф	149/14	45/14	15	0	0	0	3/14	19/14

Х 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) Ф 4 = 149/14.

В індексному рядку останньої таблиці немає негативних чисел, тобто, у виразі для цільової функції все Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Відповідь: Ф m ax = 149/14,

оптимальне рішення (0; 0; 25/14; 37/14; 1/2; 0; 0)

Варіант 8. Мінімізувати цільову функцію Ф = 5 x 1 - x 3

при обмеженнях: x 1 + x 2 + 2 · x 3 - x 4 = 3,

x 2 + 2 · x 4 = 1,

Рішення:

Кількість змінних дорівнює 4, ранг матриці - 2, отже кількість вільних змінних дорівнює r = 4 - 2 = 2, кількість базисних теж 2. Як вільні змінні прийоми х 3 , х 4 , базисні змінні x 1 , x 2 виразимо через вільні і наведемо систему до одиничного базису:

x 2 = 1 - 2 · x 4 ,

x 1 = 3 - x 2 - 2 · x 3 + x 4 = 3 - 1 + 2 · x 4 - 2 · x 3 + x 4 = 2 - 2 · x 3 + 3 · x 4

Ф = 5 · x 1 - x 3 = 5 · (2 ​​- 2 · x 3 + 3 · x 4) - x 3 = 10 - 10 · x 3 + 15 · x 4 - x 3 = 10 - 11 · x 3 + 15 · x 4

Запишемо систему рівнянь і цільову функцію в зручному для симплекс-таблиці вигляді, тобто x 2 + 2 x 4 = 1,

x 1 +2 · x 3 - 3 · x 4 = 2

Ф + 11 · x 3 - 15 · x 4 = 10

Складемо таблицю

I ітерація Таблиця 1

Базисн. перем.	Свобод. перем.
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
Ф	10	0	0	11	— 15		— 11/2

Х 1 = (2; 1; 0; 0) Ф 1 = 10.

ІІ ітерація Таблиця 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
Ф	— 1	— 11/2	0	0	3/2		— 3/4

Х 2 = (0; 1; 1; 0) Ф 2 = -1.

ІІІ ітерація Таблиця 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
Ф	— 7/4	— 11/2	— 3/4	0	0

Х 3 = (0; 0; 7/4; 1/2) Ф 3 = -7/4.

У індексному рядку останньої таблиці немає позитивних чисел, тобто, у виразі для цільової функції все Г i > 0. Маємо випадок I, отже, останнє базисне рішення є оптимальним.

Відповідь: Ф min = -7/4, оптимальне рішення (0; 0; 7/4; 1/2)

********************

Варіант 10. Мінімізувати цільову функцію Ф = x1 + x2,

при обмеженнях: x 1 -2 · x 3 + x 4 = 2,

x 2 - x 3 + 2 · x 4 = 1,

Рішення:

Кількість змінних дорівнює 5, ранг матриці - 3, отже кількість вільних змінних дорівнює r = 6-3 = 2. Як вільні змінні прийоми х 3 і х 4, як базові - x 1 , x 2 , x 5 . Всі рівняння системи вже приведені до одиничного базису (базисні змінні виражені через вільні), але записані у вигляді, не зручному для застосування симплекс-таблиць. Запишемо систему рівнянь у вигляді

x 1 - 2 · x 3 + x 4 = 2

x 2 - x 3 +2 · x 4 = 1

x 5 + x 3 - x 4 . = 5

Цільову функцію виразимо через вільні змінні і запишемо у вигляді Ф - 3 x 3 +3 x 4 = 3

Складемо таблицю

I ітерація Таблиця 1

Базисн. перем.	Свобод. перем.
х 1	2	1	0	-2	1	0	2	-1/2
х 2	1	0	1	-1		0	1/2	1/2
х 5	5	0	0	1	-1	1		1/2
Ф	3	0	0	-3	3	0		-3/2

Х 1 = (2; 3; 0; 0; 5) Ф 1 = 3.

Таблиця 2

х 1	3/2	1	-1/2	-3/2	0	0
х 4	1/2	0	1/2	-1/2	1	0
х 5	11/2	0	1/2	1/2	0	1
Ф	3/2	0	-3/2	-3/2	0	0

Х 2 = (3/2; 0; 0; 1/2; 11/2) Ф 2 = 3/2.

У індексному рядку останньої таблиці немає позитивних чисел, тобто у виразі для цільової функції все Гi > 0. Маємо випадок 1, отже, останнє базисне рішення є оптимальним.

Відповідь: Ф min = 3/2, оптимальне рішення (3/2; 0; 0; 1/2; 11/2).

Розділимо третій рядок на ключовий елемент, що дорівнює 5, отримаємо третій рядок нової таблиці.

Базовим стовпцям відповідають поодинокі стовпці.

Розрахунок інших значень таблиці:

«БП – Базовий План»:

; ;

«х1»: ; ;

«х5»: ; .

Значення індексного рядка невід'ємні, отже отримуємо оптимальне рішення: ; .

Відповідь:максимальний прибуток від виготовленої продукції, рівну 160/3 од., забезпечує випуск лише продукції другого типу у кількості 80/9 одиниць.

Завдання №2

Дано завдання нелінійного програмування. Знайти максимум та мінімум цільової функції графоаналітичним методом. Скласти функцію Лагранжа та показати, що в точках екстремуму виконуються достатні умовимінімуму (максимуму).

Т.к. остання цифра шифру дорівнює 8, то А = 2; В=5.

Т.к. передостання цифра шифру дорівнює 1, слід вибрати завдання № 1.

Рішення:

1) Накреслимо область, яку задає система нерівностей.

Ця область – трикутник АВС із координатами вершин: А(0; 2); В(4; 6) та С(16/3; 14/3).

Рівні цільової функції є кола з центром у точці (2; 5). Квадрати радіусів будуть значеннями цільової функції. Тоді малюнку видно, що мінімальне значення цільової функції досягається у точці Н, максимальне – або у точці А, або у точці З.

Значення цільової функції у точці А: ;

Значення цільової функції у точці З: ;

Значить, найбільше значення функції досягається в точці А (0; 2) і 13.

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

Для цього розглянемо систему:

ó

ó

Пряма є дотичною до кола, якщо рівняння має єдине рішення. Квадратне рівняннямає єдине рішення, якщо дискримінант дорівнює 0.

Тоді ; ; - Мінімальне значення функції.

2) Складемо функцію Лагранжа для знаходження мінімального рішення:

При x 1 =2.5; x 2 =4.5 отримаємо:

ó

Система має рішення за , тобто. достатні умови екстремуму виконуються.

Складемо функцію Лагранжа для знаходження максимального рішення:

Достатні умови екстремуму:

При x 1 =0; x 2 =2 отримаємо:

ó ó

Система також має рішення, тобто. достатні умови екстремуму виконуються.

Відповідь:мінімум цільової функції досягається при ; ; максимум цільової функції досягається при ; .

Завдання №3

Двом підприємствам виділяються кошти у кількості dодиниць. При виділенні першому підприємству на рік xодиниць коштів воно забезпечує дохід k 1 xодиниць, а при виділенні другому підприємству yодиниць коштів, воно забезпечує дохід k 1 yодиниць. Залишок коштів до кінця року для першого підприємства дорівнює nx, а для другого my. Як розподілити всі кошти протягом 4-х років, щоби загальний дохід був найбільшим? Завдання вирішити шляхом динамічного програмування.

i=8, k=1.

A=2200; k 1 =6; k 2 = 1; n=0.2; m=0.5.

Рішення:

Весь період тривалістю 4 роки розбиваємо на 4 етапи, кожен із яких дорівнює одному року. Пронумеруємо етапи, починаючи з першого року. Нехай Х k та Y k – кошти, виділені відповідно підприємствам А та В на k – тому етапі. Тоді сума Х k + Y k = а k є загальною кількістю коштів, що використовуються на k - тому етапі і залишилися від попереднього етапу k - 1. На першому етапі використовуються всі виділені кошти та а 1 = 2200 од. дохід, який буде отримано на k – тому етапі, при виділенні Х k та Y k одиниць становитиме 6Х k + 1Y k . нехай максимальний дохід, отриманий останніх етапах починаючи з k – того етапу становить f k (а k) од. запишемо функціональне рівняння Беллмана, що виражає принцип оптимальності: який би не був початковий стан і початкове рішеннянаступне рішення має бути оптимальним по відношенню до стану, що отримується в результаті початкового стану:

Для кожного етапу потрібно вибрати значення Х k , а значення Y k=аk- хk. З огляду на це знайдемо дохід на k – тому етапі:

Функціональне рівняння Беллмана матиме вигляд:

Розглянемо всі етапи, починаючи з останнього.

(бо максимум лінійної функції досягається в кінці відрізка при х 4 = а 4);