Лінійне програмування - допустимі оптимальні рішення. Допустиме та оптимальне рішення. Приклад складання математичної моделі

Загальна постановка задачі лінійного програмування(ЗЛП). Приклади ЗЛП

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

• - Завдання про оптимальне використання ресурсів при виробничому плануванні;
• - Завдання про суміші (планування складу продукції);
• - Завдання про знаходження оптимальної комбінації різних видівпродукції для зберігання на складах (управління товарно-матеріальними запасами або "завдання про рюкзак");
• - Транспортні завдання (аналіз розміщення підприємства, переміщення вантажів). Лінійне програмування - найбільш розроблений та широко застосовуваний розділ математичного програмування (крім того, сюди відносять: ціле чисельне, динамічне, нелінійне, параметричне програмування). Це пояснюється так:
• - математичні моделі великої кількості економічних завдань лінійні щодо шуканих змінних;
• - даний тип завдань нині найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці завдання вирішуються, та відповідні програми для ЕОМ;
• - багато завдань лінійного програмування, будучи вирішеними, знайшли широке застосування;
• - деякі завдання, які в початковому формулюванні не є лінійними, після низки додаткових обмежень і припущень можуть стати лінійними або можуть бути приведені до такої форми, що можна вирішувати методами лінійного програмування. Економіко-математична модель будь-якого завдання лінійного програмування включає: цільову функцію, оптимальне значення якої (максимум або мінімум) потрібно знайти; обмеження у вигляді системи лінійних рівнянь чи нерівностей; вимога невід'ємності змінних. У загальному вигляді модель записується так:
• - цільова функція:

C1x1 + c2x2 + ... + cnxn > max(min); - обмеження:

a11x1 + a12x2 + ... + a1nxn (? = ?) b1,

a21x1 + a22x2 + ... + a2nxn (? = ?) b2

am1x1 + am2x2 + ... + amnxn (? = ?) bm;

Вимога невід'ємності:

При цьому aij, bi, cj() - задані постійні величини. Завдання полягає у знаходженні оптимального значення функції (2.1) при дотриманні обмежень (2.2) та (2.3). Систему обмежень (2.2) називають функціональними обмеженнями завдання, а обмеження (2.3) – прямими. Вектор, що відповідає обмеженням (2.2) і (2.3), називається допустимим рішенням (планом) завдання лінійного програмування. План, у якому функція (2.1) досягає свого максимального (мінімального) значення, називається оптимальним.

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

1. Завдання про оптимальне використання ресурсів під час виробничого планування. Загальний сенсЗавдань цього класу зводиться до наступного. Підприємство випускає n різних виробів. Для виробництва потрібно m різних видів ресурсів (сировини, матеріалів, робочого дня тощо.). Ресурси обмежені, їх запаси в період, що планується, становлять, відповідно, b1, b2,..., bm умовних одиниць. Відомі також технологічні коефіцієнти aij, які показують скільки одиниць i-го ресурсу потрібно для виробництва одиниці виробу j-го виду (). Прибуток, що отримується підприємством при реалізації виробу j-го виду, дорівнює cj. У запланованому періоді значення величин aij, bi і cj залишаються постійними. Потрібно скласти такий план випуску продукції, при реалізації якого прибуток підприємства був би найбільшим. Далі наведемо простий приклад завдання такого класу.

Компанія спеціалізується на випуску хокейних ключок та наборів шахів. Кожна ключка приносить компанії прибуток у розмірі $2, а кожен шаховий набір – у розмірі $4. На виготовлення однієї ключки потрібно чотири години роботи на ділянці A та дві години роботи на ділянці B. Шаховий набір виготовляється із витратами шести годин на ділянці A, шести годин на ділянці B та однієї години на ділянці C. Доступна виробнича потужність ділянки A становить 120 н. -годин на день, ділянки В - 72 н-години та ділянки С - 10 н-годин. Скільки ключок та шахових наборів має випускати компанія щодня, щоб отримувати максимальний прибуток?

Умови завдань зазначеного класу часто подають у табличній формі (див. таблицю 2.1).

За цією умовою сформулюємо завдання лінійного програмування. Позначимо: x1 - кількість що випускаються щодня хокейних ключок, x2 - кількість що випускаються щодня шахових наборів. Формулювання ЗЛП:

4x1 + 6x2? 120,

Підкреслимо, що кожна нерівність у системі функціональних обмежень відповідає у разі тому чи іншому виробничому ділянці, саме: перше - ділянці А, друге - ділянці У, третє - ділянці З.

Система змінних величин у задачі з оптимізації структури посівних площ з урахуванням сівозмін

Завдання лінійного програмування (ЗЛП) – це завдання знаходження найбільшого (або найменшого) значення лінійної функції на опуклій багатогранній множині.

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

Розглянемо наступне завдання лінійного програмування у канонічній формі:

Метод штучного базису

Як було зазначено вище, для задачі, записаної в канонічній формі, якщо серед векторів стовпців матриці Aє mодиничних і лінійно незалежних можна безпосередньо вказати опорний план. Однак для багатьох завдань лінійного програмування, записаних у канонічній формі та мають опорні плани, серед векторів стовпців матриці Aне завжди є mпоодиноких та лінійно незалежних. Розглянемо таке завдання:

Нехай потрібно знайти максимум функції

за умов

де перші nелементи нулі. Змінні називаються штучними. Вектори стовпці

(28)

утворюють так званий штучний базис m-вимірного векторного простору.

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

Теорема 4. Якщо оптимальному плані розширеного завдання (24)-(26) значення штучних змінних , то є оптимальним планом завдання (21)-(23).

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

Значення цільової функції при опорному плані (27):

Помічаємо, що F(X)і складаються з двох незалежних частин, одна з яких залежить від M, а інша – ні.

Після обчислення F(X)та їх значення, а також вихідні дані розширеної задачі заносять у симплекс таблицю, як було показано вище. Різниця полягає лише в тому, що дана таблиця містить один рядок більше, ніж звичайна симплекс таблиця. При цьому ( m+1)-ю рядок поміщають коефіцієнти, які містять M, а в ( m+2)-й рядок − коефіцієнти при M.

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

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

m+2 рядки, стовпця x 0 негативний, то вихідне завдання немає рішення.

Якщо ж не всі штучні змінні виключені з базису та елемент m+2 рядки, стовпця x 0 дорівнює нулю, то опорний план вихідного завдання є виродженим і базис містить щонайменше один із векторів штучного базису.

Якщо вихідна задача містить кілька одиничних векторів, їх слід включити в штучний базис.

Якщо під час ітерацій m+2 рядок більше не містить негативних елементів, то ітераційний процес продовжують з m+1 рядком, доки знайдено оптимальний план розширеної завдання чи виявлено нерозв'язність задачи.

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

• Складають розширене завдання (24) - (26).
• Знаходять опорний план розширеного завдання.
• Використовуючи симплекс метод виключають штучні вектори з базису. В результаті знаходять опорний план вихідного завдання або фіксують його нерозв'язність.
• Використовуючи знайдений опорний план ЗЛП (21)-(23), або знаходять оптимальний план вихідної задачі, або встановлюють її нерозв'язність.

Для вирішення задач лінійного програмування онлайн, використовуйте калькулятор

Основою вирішення економічних завдань є математичні моделі.

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

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

Змінними завданняназиваються величини Х1, Х2, Хn, що повністю характеризують економічний процес. Зазвичай їх записують як вектора: X=(X 1 , X 2 ,...,X n).

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

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

Загалом завдання лінійного програмування може бути записана у такому вигляді:

Даний запис означає наступне: знайти екстремум цільової функції (1) та відповідні йому змінні X=(X 1 , X 2 ,...,X n) за умови, що ці змінні задовольняють системі обмежень (2) та умов невід'ємності (3) .

Допустимим рішенням(планом) завдання лінійного програмування називається будь-який n-мірний вектор X=(X 1 , X 2 ,...,X n), що задовольняє системі обмежень та умов невід'ємності.

Безліч допустимих рішень (планів) завдання утворює область допустимих рішень(ОДР).

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

Приклад складання математичної моделі

Завдання використання ресурсів (сировини)

Умова:Для виготовлення n видів продукції використовується m видів ресурсів. Скласти математичну модель.

Відомі:

• b i (i = 1,2,3, ..., m) - запаси кожного i-го виду ресурсу;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - витрати кожного i-го виду ресурсу на виробництво одиниці обсягу j-го виду продукції;
• c j (j = 1,2,3,...,n) - прибуток від одиниці обсягу j-го виду продукції.

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

Рішення:

Введемо вектор змінних X = (X 1, X 2, ..., X n), де x j (j = 1,2, ..., n) - Обсяг виробництва j-го виду продукції.

Витрати i-го виду ресурсу виготовлення даного обсягу x j продукції рівні a ij x j , тому обмеження використання ресурсів виробництва всіх видів продукції має вид:
Прибуток від j-го виду продукції дорівнює c j x j , тому цільова функція дорівнює:

Відповідь- Математична модель має вигляд:

Канонічна форма задачі лінійного програмування

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

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

Вона може бути представлена ​​в координатному, векторному та матричному записі.

Канонічна задача лінійного програмування в координатному записі має вигляд:

Канонічна задача лінійного програмування матричного запису має вигляд:

• А - матриця коефіцієнтів системи рівнянь
• Х - матриця-стовпець змінних завдання
• Ао - матриця-стовпець правих частин системи обмежень

Нерідко використовуються завдання лінійного програмування, які називаються симетричними, які в матричному записі мають вигляд:

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

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

Візьмемо лінійну нерівність a 1 x 1 +a 2 x 2 +...+anxn ≤b і додамо до її лівої частини деяку величину x n+1 , таку, що нерівність перетворилася на рівність a 1 x 1 +a 2 x 2 + ...+anxn +x n+1 =b. У цьому дана величина x n+1 є неотрицательной.

Розглянемо все з прикладу.

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

Рішення:
Перейдемо до завдання знайти максимуму цільової функції.
Для цього змінимо знаки коефіцієнтів цільової функції.
Для перетворення другої та третьої нерівностей системи обмежень у рівняння введемо невід'ємні додаткові змінні x 4 x 5 (на математичній моделі ця операція відзначена буквою Д).
Змінна х 4 вводиться в ліву частину другої нерівності зі знаком "+", оскільки нерівність має вигляд "≤".
Змінна x 5 вводиться в ліву частину третьої нерівності зі знаком "-", оскільки нерівність має вигляд "≥".
У цільову функцію змінні х 4 х 5 вводяться з коефіцієнтом. рівним нулю.
Записуємо завдання у канонічному вигляді.

Тест з дисципліни «Дослідження операцій»

(вірні відповіді – перші)

1. Термін "дослідження операцій" виник …

у роки Другої світової війни

у 50-ті роки XX століття

у 60-ті роки XX століття

у 70-ті роки XX століття

у 90-ті роки XX століття

на початку XXI століття

2. Під дослідженням операцій розуміють (виберіть найкращий варіант) …

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

комплекс заходів, що вживаються для реалізації певних операцій

комплекс методів реалізації задуманого плану

наукові методи розподілу ресурсів при організації виробництва

3. Упорядкуйте етапи, якими, зазвичай, проходить будь-яке операційне дослідження:

постановка задачі

побудова змістовної (вербальної) моделі об'єкта (процесу), що розглядається.

побудова математичної моделі

вирішення завдань, сформульованих на базі побудованої математичної моделі

перевірка отриманих результатів на адекватність природі системи, що вивчається

реалізація одержаного рішення на практиці

4. У дослідженні операцій під операцією розуміють...

будь-який захід (систему дій), об'єднаний єдиним задумом і спрямований на досягнення будь-якої мети

всякий некерований захід

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

5. Рішення називають оптимальним, …

якщо воно за тими чи іншими ознаками краще за інших

якщо воно раціональне

якщо воно узгоджено з начальством

якщо вони затверджені загальними зборами

6. Математичне програмування …

займається вивченням екстремальних завдань та розробкою методів їх вирішення

є процес створення програм для комп'ютера під керівництвом математиків

займається вирішенням математичних завдань на комп'ютері

7. Завдання лінійного програмування полягає у …

знаходження найбільшого (найменшого) значення лінійної функції за наявності лінійних обмежень

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

описі лінійного алгоритмурозв'язання заданого завдання

8. У задачі квадратичного програмування…

цільова функція є квадратичною

область допустимих рішень є квадратом

обмеження містять квадратичні функції

9. У задачах цілісного програмування…

невідомі можуть набувати тільки цілих чисел

цільова функція повинна обов'язково набути цілого значення, а невідомі можуть бути будь-якими

цільовою функцією є числова константа

10. У задачах параметричного програмування…

цільова функція та/або система обмежень містить параметр(и)

область допустимих рішень є паралелограмом або паралелепіпедом

кількість змінних може бути лише парною

11. У задачах динамічного програмування…

процес знаходження рішення є багатоетапним

необхідно раціоналізувати виробництво динаміту

потрібно оптимізувати використання динаміків

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

F(х 1, х 2) = 5х 1 + 6х 2→ мах

0.2х 1 + 0.3х 2 ≤ 1.8,

0.2х 1 + 0.1х 2 ≤ 1.2,

0.3х 1 + 0.3х 2 ≤ 2.4,

х 1 ≥ 0, х 2 ≥ 0.

Виберіть завдання, яке еквівалентне цій задачі.

F(х 1, х 2)= 5х 1 + 6х 2 → мах,

2х 1 + 3х 2 ≤ 18,

2х 1 + х 2 ≤ 12,

х 1 + х 2 ≤ 8,

х 1 ≥ 0,

х 2 ≥ 0.

F(х 1, х 2)= 6х 1 + 5х 2 → min,

2х 1 + 3х 2 ≤ 18,

2х 1 + х 2 ≤ 12,

х 1 + х 2 ≤ 8,

х 1 ≥ 0,

х 2 ≥ 0.

F(х 1, х 2)= 50х 1 + 60х 2 → мах,

2х 1 + 3х 2 ≤ 18,

2х 1 + х 2 ≤ 12,

х 1 + х 2 ≤ 8,

х 1 ≥ 0,

х 2 ≥ 0.

F(х 1, х 2)= 5х 12 + 6х 22 → мах,

2х 1 + 3х 2 ≤ 18,

2х 1 + х 2 ≤ 12,

3х 1 + х 2 ≤ 2.4,

х 1 ≥ 0,

х 2 ≥ 0.

13. Цільовою функцією завдання лінійного програмування може бути функція:

F=12x1+20x2–3 0x3→min

F= →min

F=→max

F=→max.

14. Системою обмежень задачі лінійного програмування може бути система:

15. Симплекс-метод - це:

аналітичний метод вирішення основного завдання лінійного програмування

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

графічний метод вирішення основного завдання лінійного програмування;

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

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

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

розробці лінійного алгоритму та реалізації його на комп'ютері

складанні та розв'язанні системи лінійних рівнянь

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

17. Область допустимих розв'язків задачі лінійного програмування не можевиглядати так:

18. Цільовою функцією завдання лінійного програмування може бути функція:

F=12x1+20x2–3 0x3→min

F= →min

F=→max

F=→max.

19.Системою обмежень задачі лінійного програмування може бути система:

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

F(х 1, х 2)= 3х 1 + 5х 2 одно…

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

Тоді максимальне значення функції F(х 1, х 2)= 5х 1 + 3х 2 одно…

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

Тоді максимальне значення функції F(х 1, х 2)= 2х 1 - 2х 2 одно…

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

F(х 1, х 2)= 2х 1 - 2х 2 одно…

24. Область допустимих розв'язків задачі нелінійного програмування має вигляд:

Тоді максимальне значення функції F(х 1, х 2)= х 2 – х 12 одно…

25. Максимальне значення цільової функції F(х 1, х 2)= 5х 1 + 2х 2 при обмеженнях
х 1 + х 2 ≤ 6,

х 1 ≤ 4,

х 1 ≥ 0, х 2 ≥ 0, дорівнює …

26. Мале підприємство виробляє вироби двох видів. На виготовлення одного виробу виду А витрачається 2 кг сировини, виготовлення одного виробу виду В – 1 кг. Усього є 60 кг сировини. Потрібно скласти план виробництва, що забезпечує отримання найбільшого виторгу, якщо відпускна вартість одного виробу виду А 3 д. е., виду В - 1 у. е., причому виробів виду А потрібно виготовити трохи більше 25, а виду – трохи більше 30.

Це завдання є …

завданням лінійного програмування

завданням, що розв'язується методом динамічного програмування

Завданням мережевого планування.

27. Мале підприємство виробляє вироби двох видів. На виготовлення одного виробу виду А витрачається 2 кг сировини, виготовлення одного виробу виду В – 1 кг. Усього є 60 кг сировини. Потрібно скласти план виробництва, що забезпечує отримання найбільшого виторгу, якщо відпускна вартість одного виробу виду А 3 д. е., виду В - 1 у. е., причому виробів виду А потрібно виготовити трохи більше 25, а виду – трохи більше 30.

Цільовою функцією цього завдання є функція …

F(x1, x2)=3x1+x2→max

F(x1, x2)=25x1+30x2→max

F(x1, x2)=2x1+x2→max

F(x1, x2)=60 -2x1 - x2→min

28. Мале підприємство виготовляє вироби двох видів. На виготовлення одного виробу виду А витрачається 2 кг сировини, виготовлення одного виробу виду В – 1 кг. Усього є 60 кг сировини. Потрібно скласти план виробництва, що забезпечує отримання найбільшого виторгу, якщо відпускна вартість одного виробу виду А 3 д. е., виду В - 1 у. е., причому виробів виду А потрібно виготовити не більше 25, а виду – не більше 30

Допустимим планом цього завдання є план:

X=(20, 20)

X=(25, 15)

X=(20, 25)

X=(30, 10)

29. У двох пунктах А1 та А2 є відповідно 60 та 160 одиниць товару. Весь товар потрібно перевезти до пунктів В1, В2, В3 у кількості 80, 70 та 70 одиниць відповідно. Таблиця тарифів така: . Сплануйте перевезення так, щоб їхня вартість була мінімальною.

Це завдання є …

транспортним завданням

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

завданням комівояжера

завданням про призначення

30. У двох пунктах А1 та А2 є відповідно 60 та 160 одиниць товару. Весь товар потрібно перевезти до пунктів В1, В2, В3 у кількості 80, 70 та 70 одиниць відповідно. Таблиця тарифів така: . Сплануйте перевезення так, щоб їхня вартість була мінімальною

Опорним планом цього завдання є план:

;

31. У двох пунктах А1 та А2 є відповідно 60 та 160 одиниць товару. Весь товар потрібно перевезти до пунктів В1, В2, В3 у кількості 80, 70 та 70 одиниць відповідно. Таблиця тарифів така: . Сплануйте перевезення так, щоб їхня вартість була мінімальною.

Цільовою функцією даного завдання є функція:

F=4x11+6x12+ 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2+ 80x3+70x4+705 →max

F=60x1+160x2- 80x3- 70x4- 705 →min

32. У двох пунктах А1 та А2 є відповідно 60 та 160 одиниць товару. Весь товар потрібно перевезти до пунктів В1, В2, В3 у кількості 80, 70 та 70 одиниць відповідно. Таблиця тарифів така: . Сплануйте перевезення так, щоб їхня вартість була мінімальною.

Оптимальним планом цього завдання є план:

;

.

;

;

33. Транспортне завдання

буде закритою, якщо…

34. Транспортне завдання

є…

відкритою

закритою

нерозв'язною

35. Транспортне завдання

є…

закритою

відкритою

нерозв'язною

36. Для вирішення наступної транспортного завдання

необхідно ввести…

фіктивного споживача

фіктивного постачальника;

ефективний тариф

37. Для вирішення наступного транспортного завдання

необхідно ввести…

фіктивного постачальника;

фіктивного споживача

ефективний тариф

ефективну відсоткову ставку.

38. Серед даних транспортних завдань

закритими є…

39. Вихідний опорний план транспортного завдання можна скласти.

усіма перерахованими методами

методом північно-західного кута

методом мінімального тарифу

методом подвійної переваги

методом апроксимації Фогеля

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

цільова функція у подвійному завданні відсутня

двоїсте завдання не має рішень

подвійне завдання має безліч рішень

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

F(х 1, х 2)= 2х 1 + 7х 2 → мах,

2х 1 + 3х 2 ≤ 14,

х 1 + х 2 ≤ 8,

х 1 ≥ 0, х 2 ≥ 0.

Двоїм для цього завдання буде наступне…

F*(y1, y2) = 14y1 + 8y2 → min,

3y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

F*(y1, y2) = 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0.

F*(y1, y2) = 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0.

F*(y1, y2) = 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. Якщо одне з пари двоїстих завдань має оптимальний план, то…

та інша має оптимальний план

інша не має оптимального плану

інша не має допустимих рішень

43. Якщо одне з пари двоїстих завдань має оптимальний план, то…

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

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

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

44. Якщо цільова функція однієї з пари двоїстих завдань не обмежена (для задачі на максимум – зверху, для задачі на мінімум – знизу), то

інше завдання не має допустимих планів

інше завдання має допустимі плани, але не має оптимального плану

цільова функція іншого завдання також не обмежена

45. При вирішенні деяких завдань нелінійного програмування застосовується …

метод множників Лагранжа

метод Гауса

метод апроксимації Фогеля

метод Гоморі

46. ​​Задано завдання нелінійного програмування

F(х 1, х 2)= х 12 + х 22 → мах,

х 1 + х 2 =6,

х 1 ≥ 0, х 2 ≥ 0.

F(х 1, х 2) …

не можна досягти (+ ¥)

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

F(х 1, х 2)= х 12 + х 22 → min,

х 1 + х 2 =6,

х 1 ≥ 0, х 2 ≥ 0.

F(х 1, х 2) …

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

F(х 1, х 2)= х 12 + х 22 → мах,

х 1 + х 2 =6,

х 1, х 2 – будь-які.

Найбільше значення цільової функції F(х 1, х 2) …

не можна досягти (+ ¥)

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

F(х 1, х 2)= х 12 + х 22 → min,

х 1 + х 2 =6,

х 1, х 2 – будь-які.

Найменше значення цільової функції F(х 1, х 2) …

не можна досягти (- ¥)

50. Область допустимих розв'язків задачі нелінійного програмування має вигляд:

Тоді максимальне значення функції F(х 1, х 2)= х 12 +х 22 одно…

51. Область допустимих розв'язків задачі нелінійного програмування має вигляд:

Тоді мінімальне значенняфункції F(х 1, х 2)= х 12 +х 22 одно…

52. Для вирішення транспортної задачі може застосовуватись...

метод потенціалів

метод множників Лагранжа

метод Гауса

метод дезорієнтації

53. У системі обмежень загального завдання лінійного програмування …

54. У системі обмежень стандартного (симетричного) завдання лінійного програмування …

можуть бути тільки нерівності

можуть бути і рівняння, і нерівності

можуть бути тільки рівняння

55. У системі обмежень канонічного (основного) завдання лінійного програмування …

можуть бути тільки рівняння (за умови невід'ємності змінних)

можуть бути тільки нерівності (за умови невід'ємності змінних)

можуть бути і рівняння, і нерівності (за умови невід'ємності змінних)

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

F(х 1, х 2)= 2х 1 + 7х 2 → мах,

2х 1 + 3х 2 ≤ 14,

х 1 + х 2 ≤ 8,

х 1 ≥ 0, х 2 ≥ 0.

записано у …

стандартною (симетричною) формою

канонічної (основної) форми

словесній формі

57. Для запису задачі

F(х 1, х 2)= 2х 1 + 7х 2 → мах,

2х 1 + 3х 2 ≤ 14,

х 1 + х 2 ≤ 8,

х 1 ≥ 0, х 2 ≥ 0.

у канонічній формі …

58. Для запису задачі

F(х 1, х 2)= 2х 1 + 7х 2 → мах,

2х 1 + 3х 2 ≤ 14,

х 1 + х 2 ≤ 8,

х 1 + 4х 2 ≥ 10,

х 1 ≥ 0, х 2 ≥ 0.

у канонічній формі …

необхідно ввести три додаткові невід'ємні змінні

необхідно ввести дві додаткові невід'ємні змінні

необхідно ввести чотири додаткові невід'ємні змінні

59. Для запису задачі

F(х 1, х 2)= 2х 1 + 7х 2 → мах,

2х 1 + 3х 2 = 14,

х 1 + х 2 ≤ 8,

х 1 + 4х 2 ≥ 10,

х 1 ≥ 0, х 2 ≥ 0.

у канонічній формі …

необхідно ввести дві додаткові невід'ємні змінні

необхідно ввести три додаткові невід'ємні змінні

необхідно ввести чотири додаткові невід'ємні змінні

необхідно ввести п'ять додаткових невід'ємних змінних

60. При вирішенні завдань цілісного програмування може застосовуватись …

метод Гоморі

метод множників Лагранжа

метод Гауса

метод апроксимації Фогеля

61. В основі розв'язання задач методом динамічного програмування лежить...

принцип «бритва Оккама»

принцип «зуб – за зуб, око – за око»

принцип Гейзенберга

62 . Ситуація, у якій беруть участь сторони, інтереси яких повністю чи частково протилежні, називається …

(Конфліктна, конфліктна, конфлікт, конфліктом)

63. Справжній чи формальний конфлікт, в якому є принаймні два учасники (гравці), кожен з яких прагне досягнення власних цілей, називається …

(Гра, грою)

64. Допустимі дії кожного з гравців, спрямовані на досягнення певної мети, називаються …

(Правила гри, правилами гри)

65. Кількісна оцінка результатів гри називається …

(платіж, платіж, платіж)

66. Якщо у грі бере участь лише дві сторони (дві особи), то гра називається…

(парна, парна, парна гра, парна гра)

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

(З нульовою сумою)

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

(стратегія гравця, стратегія гравця, стратегія, стратегія)

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

(оптимальною, оптимальною, оптимальною стратегією, оптимальною стратегією)

70. Нехай a – нижня ціна, а b – верхня ціна парної гри з нульовою сумою. Тоді правильне твердження…

71. Нехай a – нижня ціна, а b – верхня ціна парної гри з нульовою сумою. Якщо a = b = v, число v називається …

ціною гри

точкою рівноваги

оптимальною стратегією

змішаною стратегією

72. Нехай a – нижня ціна, а b – верхня ціна парної гри з нульовою сумою. Якщо a = b, гра називається…

грою з сідловою точкою

нерозв'язним конфліктом

грою без правил

73. Вектор, кожен із компонентів якого показує відносну частоту використання гравцем відповідної чистої стратегії, називається…

змішаною стратегією

напрямним вектором

вектором нормалі

градієнтом

74. Нижня ціна матричної гри, заданої платіжною матрицею, дорівнює…

Більше нижньої ціни

дорівнює нижній ціні

не існує

81. Матрична гра, задана платіжною матрицею, …

має сідлову точку

не має сідлової точки

не є парною

82. Ціна гри, заданої платіжною матрицею, дорівнює…

83. Матрична гра, задана платіжною матрицею, …

є парною

має сідлову точку

не є парною

84. Парна гра з нульовою сумою, задана своєю платіжною матрицею, може бути зведена до …

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

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

цілісної задачі лінійного програмування

класичної задачі оптимізації

85. Нижня ціна матричної гри, заданої платіжною матрицею, дорівнює…

Більше нижньої ціни

дорівнює нижній ціні

не існує

92. Матрична гра, задана платіжною матрицею, …

не має сідлової точки

має сідлову точку

не є парною

93. Ціна гри, заданої платіжною матрицею, укладена в межах...

94. Якщо в потоці подій події йдуть одна за одною через заздалегідь задані та суворо визначені проміжки часу, то такий потік називається …

регулярним

організованим

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

стаціонарним

потоком без наслідків

найпростішим

пуассонівським

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

потоком без наслідків

регулярним

показовим

нормальним

97. Якщо ймовірність попадання на дуже малий відрізок часу одразу двох або більше подій зневажливо мала порівняно з ймовірністю попадання лише однієї події, то відповідний потік подій називається…

ординарним

неординарним

нормальним

пуассонівським

98. Якщо потік подій одночасно має властивості стаціонарності, ординарності та відсутність наслідку, то він називається:

найпростішим (пуассонівським)

нормальним

99. Одноканальна СМО з відмовами є постом щоденного обслуговування для миття автомобілів. Заявка - автомобіль, що прибув у момент, коли пост зайнятий - отримує відмову в обслуговуванні. Інтенсивність потоку автомобілів λ=1,0 (автомобіль за годину). Середня тривалість обслуговування – 1,8 години. Потік автомобілів та потік обслуговування є найпростішими. Тоді в режимі, що встановився, відносна пропускна здатність qдорівнює…

100. Одноканальна СМО з відмовами є постом щоденного обслуговування для миття автомобілів. Заявка - автомобіль, який прибув у момент, коли пост зайнятий - отримує відмову в обслуговуванні. Інтенсивність потоку автомобілів λ=1,0 (автомобіль за годину). Середня тривалість обслуговування – 1,8 години. Потік автомобілів та потік обслуговування є найпростішими. Тоді в режимі відсоток автомобілів, що отримують відмову в обслуговуванні, дорівнює…

Складові математичної моделі

Основою вирішення економічних завдань є математичні моделі.

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

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

Змінними завданняназиваються величини Х1, Х2, Хn, що повністю характеризують економічний процес. Зазвичай їх записують як вектора: X=(X1, X2,...,Xn).

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

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

Загалом завдання лінійного програмування може бути записана у такому вигляді:

Цей запис означає наступне: знайти екстремум цільової функції (1) та відповідні йому змінні X=(X1, X2,...,Xn) за умови, що ці змінні задовольняють системі обмежень (2) та умов невід'ємності (3).

Допустимим рішенням(планом) завдання лінійного програмування називається будь-який n-мірний вектор X = (X1, X2, ..., Xn), що задовольняє системі обмежень та умов невід'ємності.

Безліч допустимих рішень (планів) завдання утворює область допустимих рішень(ОДР).

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

Умова:Для виготовлення n видів продукції використовується m видів ресурсів. Скласти математичну модель.

Відомі:

• bi(i = 1,2,3,...,m) - запаси кожного i-го виду ресурсу;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - витрати кожного i-го виду ресурсу виробництва одиниці обсягу j-го виду продукції;
• cj (j = 1,2,3,...,n) - прибуток від одиниці обсягу j-го виду продукції.

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

Рішення:

Введемо вектор змінних X = (X1, X2, ..., Xn), де xj (j = 1,2, ..., n) - обсяг виробництва j-го виду продукції.

Витрати i-го виду ресурсу виготовлення даного обсягу xj продукції рівні aijxj, тому обмеження використання ресурсів виробництва всіх видів продукції має вид:
Прибуток від j-го виду продукції дорівнює cjxj, тому цільова функція дорівнює:

Відповідь- Математична модель має вигляд:

Канонічна форма задачі лінійного програмування

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

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

Вона може бути представлена ​​в координатному, векторному та матричному записі.

Канонічна задача лінійного програмування в координатному записі має вигляд:

Канонічна задача лінійного програмування матричного запису має вигляд:

• А – матриця коефіцієнтів системи рівнянь
• Х - матриця-стовпець змінних завдання
• Ао - матриця-стовпець правих частин системи обмежень

Нерідко використовуються завдання лінійного програмування, які називаються симетричними, які в матричному записі мають вигляд:

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

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

Візьмемо лінійну нерівність a1x1+a2x2+...+anxn≤b і додамо до її лівої частини деяку величину xn+1, таку, що нерівність перетворилася на рівність a1x1+a2x2+...+anxn+xn+1=b. У цьому дана величина xn+1 є неотрицательной.

Розглянемо все з прикладу.

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

Рішення:
Перейдемо до завдання знайти максимуму цільової функції.
Для цього змінимо знаки коефіцієнтів цільової функції.
Для перетворення другої та третьої нерівностей системи обмежень у рівняння введемо невід'ємні додаткові змінні x4 x5 (на математичній моделі ця операція відзначена буквою Д).
Змінна х4 вводиться в ліву частину другої нерівності зі знаком "+", оскільки нерівність має вигляд "≤".
Змінна x5 вводиться в ліву частину третьої нерівності зі знаком "-", оскільки нерівність має вигляд "≥".
У цільову функцію змінні x4 x5 вводяться з коефіцієнтом. рівним нулю.
Записуємо завдання у канонічному вигляді: