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

Тести для поточного контролюзнань

1. Будь-яка економіко – математична модель завдання лінійного програмуванняскладається з:

A. цільової функції та системи обмежень

B.цільової функції, системи обмежень та умови невід'ємності змінних

C. системи обмежень та умови невід'ємності змінних

D. цільової функції та умови невід'ємності змінних

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

B. система рівнянь

C. система нерівностей

D. умова невід'ємності змінних

3. Оптимальне вирішення задачі математичного програмування – це

A. допустиме рішення системи обмежень

B. будь-яке рішення системи обмежень

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

D. максимальне або мінімальне рішення системи обмежень

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

A. всі знаки

B.всі знаки

C. всі знаки

D. всі знаки

5. Завдання лінійного програмування вирішується графічним способомякщо в задачі

A. одна змінна

B.дві змінні

C. три змінні

D. чотири змінні

6. Нерівність виду описує

B. коло

C.напівплощина

D. площина

7. Максимум або мінімум цільової функції знаходиться

A. на початку координат

B. на сторонах опуклого багатокутника рішень

C. всередині опуклого багатокутника рішень

D.у вершинах опуклого багатокутника рішень

8. Канонічним видом ЗЛП називається такий її вид, у якому система обмежень містить знаки

A. всі знаки

B. всі знаки

C.всі знаки

D. всі знаки

9. Якщо обмеження задано зі знаком «>=», то додаткова змінна вводиться в це обмеження з коефіцієнтом

B.-1

10. До цільової функції додаткові змінні вводяться з коефіцієнтами

C.0

A.кількість ресурсу з номером i, необхідного для виготовлення 1 одиниці продукції j – го виду

B. невикористані ресурси i - го виду

C. прибуток від реалізації 1 одиниці продукції j – го виду

D. кількість продукції j – го виду

12. Стовпець, що дозволяє, при вирішенні ЗЛП на max цільової функції вибирається виходячи з умови

A.найбільше позитивне значеннякоефіцієнта Cj цільової функції

B. найменше позитивне значення коефіцієнта Cj цільової функції

C. найбільше негативне значеннякоефіцієнта Cj цільової функції

D. будь-який стовпець коефіцієнтів при невідомих

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

A. на перетині рядка коефіцієнтів цільової функції зі стовпцем коефіцієнтів при х1

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

C. у стовпці коефіцієнтів при хn

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

14. Штучні змінні до системи обмежень у канонічному вигляді вводяться з коефіцієнтом

A.1

15. Оптимальність плану в симплексній таблиці визначається

A. по стовпцю b

B.по рядку значень цільової функції

C. за роздільною здатністю

D. по роздільному стовпцю

16. Дана задача лінійного програмування

B.1

17. Дана задача лінійного програмування

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

C.2

18. Якщо вихідна ЗЛП має вигляд

тоді обмеження двоїстої задачі

A. мають вигляд

B.мають вигляд

C. мають вигляд

D. мають вигляд

19. Якщо вихідна ЗЛП має вигляд

A. мають вигляд

B. мають вигляд

C. мають вигляд

D.мають вигляд

20. Коефіцієнтами за невідомих цільової функції двоїстої задачі є

A. коефіцієнти при невідомих цільової функції вихідної задачі

B.вільні члени системи обмежень вихідного завдання

C. невідомі вихідні завдання

D. коефіцієнти при невідомих системиобмежень вихідного завдання

21. Якщо вихідна ЗЛП була на максимум цільової функції, то подвійне завдання буде

A. теж на максимум

B. або на максимум, або на мінімум

C. і на максимум, і на мінімум

D.на мінімум

22. Зв'язок вихідної та двоїстої задач полягає в тому, що

A. треба вирішувати обидві задачі

B.рішення однієї з них виходить із рішення іншої

C. з вирішення двоїстої задачі не можна отримати рішення вихідної

D. обидві мають однакові рішення

23. Якщо вихідна ЗЛП має вигляд

тоді цільова функція двоїстої задачі

A. мають вигляд

B. мають вигляд

C.мають вигляд

D. мають вигляд

24. Якщо вихідна ЗЛП має вигляд

то кількість змінних у подвійному завданні дорівнює

B.2

25. Модель транспортного завдання закрита,

A.якщо

26. Цикл у транспортному завданні – це

A. замкнута прямокутна ламана лінія, всі вершини якої знаходяться у зайнятих клітинах

B. замкнута прямокутна ламана лінія, всі вершини яких знаходяться у вільних клітинах

C. замкнута прямокутна ламана лінія, одна вершина якої у зайнятій клітці, решта у вільних клітинах

D.замкнута прямокутна ламана лінія, одна вершина якої у вільній клітині, а решта у зайнятих клітинах

27. Потенціалами транспортного завдання розмірності (m*n) називаються m+n чисел ui та vj, для яких виконуються умови

A.ui+vj=cij для зайнятих клітин

B. ui+vj=cij для вільних клітин

C. ui+vj=cij для перших двох стовпців розподільчої таблиці

D. ui+vj=cij для перших двох рядків розподільчої таблиці

28. Оцінками транспортного завдання розмірності (m+n) називаються числа

yij=cij-ui-vj, які обчислюються

A. для зайнятих клітин

B.для вільних клітин

C. для перших двох рядків розподільчої таблиці

D. для перших двох стовпців розподільчої таблиці

29. При вирішенні транспортного завдання значення цільової функції повинне від ітерації до ітерації.

A. збільшуватися

B. збільшуватися чи змінюватися

C. збільшуватися на величину будь-якої оцінки

D.зменшуватися чи не змінюватися

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

C.m+n-1

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

A. сумарний обсяг перевезень

B.сумарна вартість перевезень

C. сумарні постачання

D. сумарні потреби

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

Будуємо в системі координат х 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. Заповнюємо другу симплексну таблицю. Змінні на перетині яких отримуємо роздільну здатність, міняємо місцями, тобто. і . Дозволяючий елемент замінюємо йому зворотним, тобто. на. Елементи роздільної здатності рядка і стовпця (крім роздільної здатності) ділимо на роздільний елемент. При цьому у коефіцієнтів роздільного стовпця змінюємо знак.

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

.

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

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.

Державна бюджетна освітня установа

вищої професійної освіти

"Омський державний технічний університет"

РОЗРАХУНОВО-ГРАФІЧНА РОБОТА

з дисципліни "ТЕОРІЯ ОПТИМАЛЬНОГО УПРАВЛІННЯ »

на тему "МЕТОДИ ОПТИМІЗАЦІЇ І ДОСЛІДЖЕННЯ ОПЕРАЦІЙ »

варіант 7

Виконав:

студент заочного відділення

4-го курсу групи ЗА-419

ПІБ: Кужельов С. А.

Перевірила:

Девятерикова М.В.

Київ – 2012 р.
^

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

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

Перше обмеження моделі має вигляд . Замінивши в ньому знак ≤ на знак =, отримуємо рівняння . На рис. 1.1 воно визначає пряму (1), яка розбиває площину на дві напівплощини, в даному випадку вище лінії і нижче за неї. Щоб вибрати, яка з них задовольняє нерівність , підставимо в нього координати будь-якої точки, що не лежить на цій прямій (наприклад, початок координат х 1 = 0, х 2 = 0). Оскільки отримуємо правильне вираз (20 0 + 6 0 = 0 ≤15), то нерівності задовольняє напівплощину, що містить початок координат (позначена стрілкою). В іншому випадку інша напівплощина.

Аналогічно чинимо з іншими обмеженнями завдання. Перетин усіх побудованих напівплощин з першим квадрантом утворює ABCD(Див. рис. 1). Це і є допустима сфера завдання.

Крок 2. Побудова лінії рівня Лінія рівня Цільова функція - це безліч точок площини, в яких цільова функція набуває постійного значення. Така множина задається рівнянням f ( x) = const. Припустимо, наприклад, const = 0 і побудуємо лінію біля рівня f ( x) = 0, тобто. у нашому випадку пряму 7 x 1 + 6x 2 = 0.

Ця пряма проходить через початок координат і перпендикулярна вектору. Цей вектор є градієнтом цільової функції у точці (0,0). Градієнт функції - це вектор значень приватних похідних цієї функції у точці, що розглядається. У разі завдання ЛП приватні похідні цільової функції дорівнюють коефіцієнтам Ci, j = 1 , ..., n.

Градієнт показує напрямок якнайшвидшого зростання функції. Переміщуючи лінію рівня цільової функції f ( x) = const. перпендикулярно до напрямку градієнта, знайдемо останню точку, в якій вона перетинається з областю. У нашому випадку це точка D, яка буде точкою максимуму цільової функції (див. рис. 2).

Вона лежить на перетині прямих (2) і (3) (див. рис. 1) і задає оптимальне рішення.

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

^ Крок 3. Визначення координат точки максимуму (мінімуму) та оптимального значення цільової функції

Щоб знайти координати точки C, необхідно вирішити систему, що складається з відповідних прямих рівнянь (у даному випадку з рівнянь 2 і 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Отримаємо оптимальне рішення = 1,33.

^ Оптимальне значення цільової функції f * = f (х *) = 7 * 0 + 6 * 1,33 = 7,8