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

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

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. сумарні потреби

Рішення: знайдемо максимальне та мінімальне значення функції \(f (x, y)\) за наступних обмежень $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \begin(cases) 2x+3y\geq 6 \3x-2y\leq 18\x +2y\leq 8\x,y\geq0\end(cases) $$
Графічний спосіб розв'язання задачі доцільно використовувати для завдань з двома змінними, які записані в симетричній формі, а також для завдань з багатьма змінними за умови, що в їх канонічному записі міститься не більше двох вільних змінних.

У разі завдання із двома змінними.

Алгоритм розв'язання задачі "геометрична інтерпретація задачі лінійного програмування":

1.Побудуємо на площині xOy область допустимих рішень.
2.Виділимо область невід'ємних рішень.

4. Побудуємо сімейство цільових функцій.
5. Знаходимо максимальне (мінімальне) значення цільової функції.

1. Будуємо область допустимих розв'язків задачі (D).

Для побудови області допустимих рішень:
1) Будуємо граничні прямі:
перетворимо нерівності до рівностей, а потім до рівняння прямої лінії у відрізках на осях виду \(\frac(x)(a)+\frac(y)(b) = 1\), тоді \(x=a\) - відрізок що відсікається на осі Ox, \(y=b\) - на осі Oy $$ \begin(cases) 2x+3y = 6 3x-2y = 18 -x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac(y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Для кожної прямої відкладаємо відрізки на осях і з'єднуємо їх. Отримали потрібні прямі.

2) Знаходимо напівплощини, які задовольняють заданим нерівностям:
Для нерівності \(2x+3y\geq 6\) - напівплощина, яка лежить вище за пряму \(2x+3y = 6\). Пряма AC
Для нерівності \(3x-2y\leq 18 => -3x+2y \geq -18\)- напівплощина, яка лежить вище за пряму \(3x-2y = 18\). Пряма CB
Для нерівності \(-x + 2y \ leq 8 \) - напівплощина, яка лежить нижче прямої \ (-x + 2y = 8 \). Пряма AB

Область допустимих рішень визначається як загальна частина трьох напівплощин, що відповідають даним нерівностям. Ця область є трикутником \(ABC\)

Областью (D) є трикутник (ABC) див. рис.

2.Виділимо область невід'ємних рішень.

Область невід'ємних рішень розташована в першій чверті і є загальною частиною всіх п'яти напівплощин, три з яких - область \(D\), отримана з нерівностей і додатково дві нерівності \(x \geq 0\) - верхня напівплощина (I і II чверті) та \(y \geq 0\) - права напівплощина (I і IV чверті), які виражають умову невід'ємності змінних \(x;y\). Отримали потрібну область невід'ємних рішень (DEBFG)

3.Знайдемо координати вершин області.
Координати чотирьох вершин вже відомі (це точки перетину прямих з осями).
Запишемо ці координати:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Знайдемо координати точки \(B\) як точки перетину прямих \(-x+2y = 8\) і \(3x-2y = 18\). Розв'яжемо систему рівнянь і знайдемо координати цієї точки $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\ 3x-2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Отримали координати точки \(B(13;10.5)\)

4. Будуємо сімейство цільових функцій.
Рівняння \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) визначає на площині xOy сімейство концентричних кіл з центом у точці з координатами \(Q(4 ;3)\), кожній з яких відповідає певне значення параметра \(f\). Як відомо, для рівняння кола параметр \(f=R^2\).

Зобразимо в одній системі координат сімейство концентричних кіл і сімейство прямих. Завдання визначення точки максимуму (мінімуму) точки (f) зведеться до знаходження в допустимій області точки, через яку проходить коло сімейства (f = const), що відповідає за найбільше (найменше) значення параметра (f).

5. Знаходимо максимальне (мінімальне) значення цільової функції.

Мінімальне значення цільової функції: Шляхом поступового збільшення радіуса кола ми отримали, що перша вершина, через яку пройде коло це точка \(G(3;0)\). Цільова функція в цій точці буде мінімальною і дорівнює \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Максимальне значення цільової функції: Шляхом подальшого збільшення радіуса кола ми отримали, що остання вершина, через яку пройде коло це точка \(B(13;10.5)\). Цільова функція в цій точці буде максимальною і дорівнює \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

Можна переконатися в правильності рішення шляхом підстановки координат вершин, що залишилися, в рівняння цільової функції:
у вершині \(D(0;2)\) значення цільової функції дорівнює \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
у вершині \(E(0;4)\) значення цільової функції дорівнює \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
у вершині \(F(6;0)\) значення цільової функції дорівнює \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Отримали, що

Відповідь:
мінімальне значення цільової функції \(f_(min) = 10\)
максимальне значення цільової функції (f_(max) = 137.25)

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

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

Варіант №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 2 так як це найбільший коефіцієнт. Обчислимо значення D i і їх виберемо найменше: min(4: 1 , 2: 2 , 10: 2) = 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рішення

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

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

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

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

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

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

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

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

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

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

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