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

Будуємо в системі координат х 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. Розв'язання задач лінійного програмування

Мета роботиОтримання навички розв'язання задач лінійного програмуванняграфічним, симплексним методом та засобами Excel.

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

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

приклад. Знайти максимальне значення цільової функції L=2x 1 +2x 2 при заданих обмеженнях

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

l 1: 3x 1 -2x 2 +6=0,

l 2: 3x 1 +x 2 -3=0,

l 3:x 1 -3=0.

DЗ

2 0 1 3 х 1

(l 1) (l 3)

Пряма l 1 ділить площину хПро уна дві напівплощини, з яких потрібно вибрати одну, що задовольняє першу нерівність у системі (3). І тому візьмемо т. Про(0; 0) і підставимо у нерівність. Якщо воно вірне, то потрібно заштрихувати ту напівплощину від прямої, в якій знаходиться т.п. Про(0; 0). Аналогічно надходять із прямими l 2 та l 3 . Областью розв'язків нерівностей (3) є багатокутник АВСD. Для кожної точки площини функція Lнабуває фіксованого значення L=L 1 . Безліч всіх токах точок є пряма L=c 1 x 1 +c 2 x 2 (у нашому випадку L=2x 1 +2x 2), перпендикулярна вектору З(з 1 ;з 2) (З(2; 2)), що виходить із початку координат. Якщо цю пряму переміщати у позитивному напрямку вектора з, то цільова функція Lзростатиме, у протилежному випадку буде спадати. Таким чином, у нашому випадку, пряма при виході з багатокутника АВСDрішень пройде через т.п. У(3; 7,5), тому у т.ч. Уцільова функція набуває максимального значення, тобто. L max =2?3+2?7,5=21. Аналогічно визначається, що мінімальне значення функція набуває в т.ч. D(1; 0) та L min =2?1+2?0=2.

Алгоритм симплексного методу розв'язання задачі лінійного програмування полягає в наступному.

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

2. Функція мети виражається через базисні та допоміжні змінні.

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

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

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

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

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

8. Перетворення симплекс-таблиц проводять до того часу, поки отримають оптимального плану.

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

Рішення. 1. Вводимо нові змінні
, за допомогою яких нерівності системи перетворюємо на рівняння:

У коефіцієнтів цільової функції змінюємо знак або записуємо її як
. Заповнюємо першу симплексну таблицю, у нульовому рядку записуємо х 1 ,х 2 та (Вільні коефіцієнти). У нульовому стовпці – х 3 ,х 4 ,х 5 і F. Заповнюємо цю таблицю за отриманою системою рівнянь та перетвореною цільовою функцією.

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

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

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

3. Заповнюємо другу симплексну таблицю. Змінні на перетині яких отримуємо роздільну здатність, міняємо місцями, тобто. і . Дозволяючий елемент замінюємо йому зворотним, тобто. на. Елементи роздільної здатності рядка і стовпця (крім роздільної здатності) ділимо на роздільний елемент. При цьому у коефіцієнтів роздільного стовпця змінюємо знак.

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

.

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

	х 1	х 4					х 3	х 2
х 3						х 1
х 2						х 2
х 5						х 5

4. Результат виконання цього алгоритму записують так. У заключній таблиці елемент, що стоїть на перетині рядка
та стовпця bдає максимальне значення цільової функції. У нашому випадку
. Значення змінних по рядках дорівнюють вільним коефіцієнтам. Для нашого завдання маємо
.

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

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

Розв'язання задач лінійного програмування засобами Excel виконується в такий спосіб.

Для вирішення завдань лінійного програмування використовується надбудова Пошук рішення. Спочатку необхідно переконатися, що ця надбудова присутня на вкладці Дані у групі Аналіз (для 2003 дивитися Сервіс). Якщо команда Пошук рішення або група Аналіз відсутня, необхідно завантажити цю надбудову.

Для цього клацніть Microsoft Office (2010), потім клацніть Параметри Excel. У вікні Параметри Excel виберіть ліворуч поле Надбудови. У правій частині вікна має бути встановлене значення поля Управління рівним Надбудови Excel, натисніть кнопку «Перейти», яка знаходиться поруч із цим полем. У вікні Надбудови встановіть прапорець поруч із пунктом Пошук рішення та натисніть кнопку ОК. Далі можна працювати із встановленою надбудовою Пошук Рішення.

До виклику Пошук Рішення необхідно підготувати дані для вирішення задачі лінійного програмування (з математичної моделі) на робочому аркуші:

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

2) Ввести залежність від змінних осередків для цільової функції та залежності від змінних осередків для лівих частин системи обмежень у залишені вільні осередки. Для запровадження формул залежностей зручно користуватися математичною функцією СУММПРОИЗВ.

Далі необхідно скористатися надбудовою Пошук рішення. На вкладці Дані у групі Аналіз виберіть команду Пошук рішення. З'явиться діалогове вікно Пошук рішення, яке потрібно заповнити так:

1) Вказати комірку, що містить цільову функцію в полі «Оптимізувати цільову функцію» (ця комірка повинна містити формулу для цільової функції). Вибираємо варіант оптимізації значення цільового осередку (максимізація, мінімізація):

2) У полі «Змінюючи комірки змінних» вводимо комірки, що змінюються. У наступному полі «Відповідно до обмежень» вводимо задані обмеження за допомогою кнопки «Додати». У вікні вводимо комірки, що містять формули системи обмежень, вибираємо знак обмеження і значення обмеження (вільний коефіцієнт):

3) Ставимо прапорець у полі «Зробити змінні без обмежень невід'ємними». Вибрати метод розв'язання «Пошук розв'язання лінійних задач симплекс-методом». Після натискання кнопки "Знайти рішення" запускається процес розв'язання задачі. У результаті з'являється діалогове вікно «Результати пошуку рішення» та вихідна таблиця із заповненими осередками для значень змінних та оптимальним значенням цільової функції.

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

,

;

,
.

Рішення.Для вирішення нашого завдання на робочому аркуші Excel виконаємо вказаний алгоритм. Вводимо вихідні дані у вигляді таблиці

Вводимо залежності для цільової функції та системи обмежень. Для цього в комірку С2 вводимо формулу СУММПРОИЗВ(A2:B2;A3:B3). У комірки С4 і С5 відповідно формули: = СУММПРОИЗВ(A2:B2;A4:B4) і =СУММПРОИЗВ(A2:B2;A5:B5). У результаті одержуємо таблицю.

Запускаємо команду «Пошук рішення» і заповнюємо вікно Пошук рішення наступним чином. У полі «Оптимізувати цільову функцію» вводимо комірку С2. Вибираємо оптимізації значення цільового осередку «Максимум».

У полі «Змінюючи комірки змінних» вводимо комірки A2:B2, що змінюються. У полі «Відповідно до обмежень» вводимо задані обмеження за допомогою кнопки «Додати». Посилання на комірку $C$4:$C$5 Посилання на обмеження =$D$4:$D$5 між ними знак<= затем кнопку «ОК».

Ставимо прапорець у полі "Зробити змінні без обмежень невід'ємними". Вибрати метод розв'язання «Пошук розв'язання лінійних задач симплекс-методом».

Натисканням кнопки «Знайти рішення» запускається процес розв'язання задачі. У результаті з'являється діалогове вікно «Результати пошуку рішення» та вихідна таблиця із заповненими осередками для значень змінних та оптимальним значенням цільової функції.

У діалоговому вікні «Результати пошуку рішення» зберігаємо результат x1=0,75, x2=0,75, F=1,5-рівний максимальному значенню цільової функції.

Завдання для самостійної роботи

Завдання 1.Графічним, симплексним методами та засобами Excel знайти максимальне та мінімальне значення функції F(x) при заданій системі обмежень.

1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2

3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2

5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2

7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2

9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2

11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2

13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2

15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2

17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2

19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2

21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3

23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2

25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2

27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2

29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2

Контрольні питання.

1. Які завдання називаються задачами лінійного програмування?

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

3. Як розв'язується задача лінійного програмування графічним методом?

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

5. Опишіть алгоритм розв'язання задач лінійного програмування засобами Excel.

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

ЗАВДАННЯ 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).

Вступ

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

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

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


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

КОНТРОЛЬНА РОБОТА З ДИСЦИПЛІНИ:

«МЕТОДИ ОПТИМАЛЬНИХ РІШЕНЬ»

Варіант №8

1. Розв'язати графічним способом завдання лінійного програмування. Знайти максимум і мінімум функції при заданих обмеженнях:

,

.

Рішення

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

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

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

Перетином напівплощин буде область, координати точок якого задовольняють умові нерівностей системи обмежень задачі. Позначимо межі області багатокутника розв'язків.

Побудуємо пряму, що відповідає значенню функції F = 0: F = 2x 1 +3x 2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок мінімізації F(X). Початок вектора – точка (0; 0), кінець – точка (2; 3). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, то рухаємо пряму до першого торкання зазначеної області. На графіці ця пряма позначена пунктирною лінією.

Пряма
перетинає область у точці C. Так як точка C отримана в результаті перетину прямих (4) та (1), то її координати задовольняють рівнянням цих прямих:
.

Розв'язавши систему рівнянь, отримаємо: x 1 = 3.3333, x 2 = 0.

Звідки знайдемо мінімальне значення цільової функції: .

Розглянемо цільову функцію завдання.

Побудуємо пряму, що відповідає значенню функції F = 0: F = 2x1 +3x2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок максимізації F(X). Початок вектора – точка (0; 0), кінець – точка (2; 3). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить максимальне рішення, то рухаємо пряму до останнього дотику зазначеної області. На графіці ця пряма позначена пунктирною лінією.

Пряма
перетинає область у точці B. Оскільки точка B отримана в результаті перетину прямих (2) і (3), її координати задовольняють рівнянням цих прямих:

.

Звідки знайдемо максимальне значення цільової функції: .

Відповідь:
і
.

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

.

Рішення

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

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

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

У 1-й нерівності сенсу (≥) вводимо базову змінну x 3 зі знаком мінус. У 2-й нерівності сенсу (≤) вводимо базову змінну x 4 . У 3-й нерівності сенсу (≤) вводимо базову змінну x 5 .

Введемо штучні змінні : в 1-й рівності вводимо змінну x 6 ;

Для постановки завдання мінімум цільову функцію запишемо так: .

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

Отриманий базис називається штучним, а метод розв'язання називається методом штучного базису.

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

З рівнянь виражаємо штучні змінні: x 6 = 4-x 1 -x 2 +x 3 які підставимо в цільову функцію: або.

Матриця коефіцієнтів
цієї системи рівнянь має вигляд:
.

Розв'яжемо систему рівнянь щодо базисних змінних: x 6 , x 4 , x 5.

Вважаючи, що вільні змінні дорівнюють 0, отримаємо перший опорний план:

X1 = (0,0,0,2,10,4)

Базисне рішення називається допустимим, якщо воно невід'ємне.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Поточний опорний план не є оптимальним, оскільки в індексному рядку знаходяться позитивні коефіцієнти. Як ведучий виберемо стовпець, відповідний змінної x 2 так як це найбільший коефіцієнт. Обчислимо значення D i і їх виберемо найменше: min(4: 1 , 2: 2 , 10: 2) = 1.

Отже, другий рядок є провідним.

Роздільний елемент дорівнює (2) і знаходиться на перетині провідного стовпця та провідного рядка.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Формуємо наступну частину сімплексної таблиці. Замість змінної x 4 план 1 увійде змінна x 2 .

Рядок, що відповідає змінній x 2 у плані 1, отримана в результаті поділу всіх елементів рядка x 4 плану 0 на роздільну здатність елемент РЕ=2. На місці роздільного елемента отримуємо 1. В інших клітинах стовпця x 2 записуємо нулі.

Таким чином, у новому плані 1 заповнені рядок х 2 і стовпець х 2 . Решта всіх елементів нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1 / 2 +1 1 / 2 M

Поточний опорний план неоптимальний, оскільки в індексному рядку є позитивні коефіцієнти. Як ведучий виберемо стовпець, відповідний змінної x 1, оскільки це найбільший коефіцієнт. Обчислимо значення D iпо рядках як приватне від поділу: і їх виберемо найменше: min (3: 1 1 / 2 , - , 8: 2) = 2.

Отже, перший рядок є провідним.

Роздільний елемент дорівнює (1 1 / 2) і знаходиться на перетині провідного стовпця та провідного рядка.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Формуємо наступну частину сімплексної таблиці. Замість змінної x6 у план 2 увійде змінна x1.

Отримуємо нову симплекс-таблицю:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

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

Остаточний варіант симплекс-таблиці:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Так як в оптимальному рішенні відсутні штучні змінні (вони дорівнюють нулю), то це рішення є допустимим.

Оптимальний план можна записати так: x1=2, x2=2:.

Відповідь:
,
.

3. Фірма «Три товстуни» займається доставкою м'ясних консервів із трьох складів, розташованих у різних точках міста в три магазини. Запаси консервів, що є на складах, а також обсяги замовлень магазинів та тарифи на доставку (в умовних грошових одиницях) представлені у транспортній таблиці.

Знайти план перевезень, що забезпечує найменші грошові витрати (початковий план перевезень виконати методом «північно-західного кута»).

Рішення

Перевіримо необхідну та достатню умову розв'язності задачі:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Умови балансу дотримуються. Запаси дорівнюють потребам. Отже, модель транспортного завдання закрита.

Занесемо вихідні дані у розподільчу таблицю.

Потреби

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

План починається заповнюватися з верхнього лівого кута.

Шуканий елемент дорівнює 4. Для цього елемента запаси дорівнюють 300, потреби 250. Оскільки мінімальним є 250, то віднімаємо його: .

			300 - 250 = 50
250 - 250 = 0

Шуканий елемент дорівнює 2. Для цього елемента запаси дорівнюють 50, потреби 400. Оскільки мінімальним є 50, то віднімаємо його: .

			50 - 50 = 0
	400 - 50 = 350

Шуканий елемент дорівнює 5. Для цього елемента запаси дорівнюють 300, потреби 350. Оскільки мінімальним є 300, то віднімаємо його:

			300 - 300 = 0
	350 - 300 = 50

Шуканий елемент дорівнює 3. Для цього елемента запаси дорівнюють 200, потреби 50. Оскільки мінімальним є 50, то віднімаємо його:

			200 - 50 = 150
	50 - 50 = 0

Шуканий елемент дорівнює 6. Для цього елемента запаси дорівнюють 150, потреби 150. Оскільки мінімальним є 150, то віднімаємо його:

			150 - 150 = 0
		150 - 150 = 0

Потреби