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

Задача 1. Вирішити графічним методом наступну задачу лінійного програмування:

Розв’язок

1. Знаходимо многокутник розв’язків. Для цього:

А) побудуємо прямі, рівняння яких дістанемо заміною в обмеженнях знаків нерівностей на знаки точних рівностей:

Б) знаходимо півплощини, що визначені кожним з обмежень задачі;

В) знаходимо многокутник розв’язків як перетин побудованих півплощин.

2. Знаходимо градієнт функції, тобто

І будуємо цей вектор.

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

4. Визначаємо координати цієї точки, розв’язуючи систему рівнянь Дістанемо

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

Вирішити попередню задачу симплекс-методом:

Введемо додаткові змінні, щоб звести задачу до канонічного виду:

Отримали розширену задачу з опорним планом .

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

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

Отже, елемент — розв’язуючий.

Отже оцінки невід'ємні, тому план, або, є оптимальним.

Максимальне значення функції

.

Задача 2. Вирішити наступну задачу лінійного програмування симплекс-методом. Для одержання базисного рішення використовувати М-метод.

Розв’язання Дана система є системою з базисом, в якій базисні змінні, а вільні змінні, вільні члени всіх рівнянь невід'ємні. Отже, для розв’язання задачі можемо застосувати симплекс — метод. Запишемо початкову симплекс таблицю:

1-а ітерація

2-а ітерація

3-я ітерація

В — строчці всі коефіцієнти невід'ємні. Отже, оптимальний розв’язок:

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

Розв’язок Помножимо друге рівняння системи обмежень на (-1), маємо Складемо двояку задачу

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

Задача 4

Проаналізувати на чутливість рішення задачі 3.

Розв’язок.

Область допустимих розв’язків — відрізок .

Обмеження є зв’язаним.

Обмеження, є незв’язаними.

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

.

Повний аналіз результату на чутливість подано у файлі 21 092 009. xls

Задача 5. Вирішити наступну транспортну задачу

Розв’язок Для того, щоб транспортна задача мала розв’язок, необхідно і достатньо, щоб .

Рівність не виконується. Тому вводимо ще одне значення .

Тоді опорний план має вигляд

Опорний план по правилу найменшого елементу:

Введемо декотрі позначки: — надлишок від , — нестача .

Знаходимо незайняту клітинку з мінімальним тарифом: (5,4). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (3,3). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (2,2). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (1,3). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (1,1). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (4,2). Поміщаємо туди найменше з чисел и .

Знаходимо незайняту клітинку з мінімальним тарифом: (4,1). Поміщаємо туди найменше з чисел и .

Транспортні витрати складатимуть:

.

Задача 6. Вирішити задачу на призначення Розв’язок

Припускаємо, що .

1.

2.

3.

Мінімальним розв’язком даної задачі є:

4+3+0+2+1=10.

Задача 7. Вирішити наступну задачу методом динамічного програмування

Інвестору необхідно оптимальним шляхом розподілити капітал між підприємствами. В залежності від розміру капіталу, що вкладається, він одержує прибуток .

Розв’язок

— початковий стан.

Розв’язок на кожному кроці - розмір капіталу, який отримає підприємство ().

Критерій ефективності - прибуток, що отримує підприємство (). Загальний критерій ефективності - це загальний прибуток, тобто сума прибутків всіх підприємств: .

Цикл безумовної оптимізації

Шаг 4. Виділення коштів підприємству П4

Шаг 2. Виділення коштів підприємствам П3 і П4

Шаг 3. Виділення коштів підприємствам П2, П3 і П4

Шаг 4. Виділення коштів підприємствам П1, П2, П3 і П4

Цикл безумовної оптимізації

Для першого кроку отримано безумовний оптимальний розв’язок. Тоді (дивись таблицю кроку 2). З таблиці кроку 3 маємо. А отже, .

Таким чином, оптимальний розв’язок задачі: підприємствам П1 і П2 кошти зовсім не виділяються, підприємству П3 — виділяється 1 частина коштів, підприємству П4 — 4 частини. Загальний прибуток складатиме — 13 грошових одиниць.

Задача 8

Вирішити наступну антагоністичну гру

Розв’язок.

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

Середній виграш першого гравця Ці залежності показані на графіку Активними стратегіями є перша та третя.

Розв’язуючи обидві задачі, маємо:

Оптимальна стратегія для гравця:

1 ;

2 ;

Задача 9

Вирішити наступну матричну гру:

Розв’язок Побудуємо прямі:

Побудуємо верхню криву, що огинає прямі. Її нижня точка М лежить строго між 0 та 1.

Примітка. Наразі ми вважаємо, що пряма лежить нижче кривої, що огинає прямі.

Далі,

Отже,

.

Тоді оптимальна стратегія гравця 1

.

Таким чином,

Задача 10

Вирішити методом Брауна-Робінсона наступну матричну гру (число ітерацій 15).

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

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

Так як гравець 1 вибрав другу стратегію, то гравець 2 може програти:

6, якщо застосує свою першу стратегію;

2, якщо застосує свою другу стратегію;

2, якщо застосує свою третю стратегію.

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

Тоді перший гравець отримає виграш 4, 2 або 6 відповідно своєї першої, другої або третьої стратегії, а його сумарний виграш за дві партії складатиме:

2+4=6 при його першій стратегії;

6+2=8 при його другій стратегії;

2+6=8 при його третій стратегії.

Найбільший сумарний виграш складає 8 при другій та третій стратегіях. Нехай в цій партії він обере другу стратегію.

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

6+2=8 при першій стратегії;

2+4=6 при другій стратегії;

2+6=8 при третій стратегії.

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

В третій партії гравець 2 обирає свою другу стратегію, тому що найменшим сумарним програшем є 6.

Таким чином, продовжуючи процес далі, складемо таблицю розігрувань гри з 15 ітерацій (партій).

З таблиці видно, що в 15 програних партіях стратегії 1, 2, 3 для другого гравця зустрічаються відповідно 6, 3, 6 разів, отже, їх відносні частоти дорівнюють, ,. Стратегії 1, 2, 3 для гравця 1 зустрічаються відповідно 6, 7, 2 рази, отже, їх відносні частоти дорівнюють, ,. А приблизне значення гри дорівнює .

Таким чином, отримали приблизний розв’язок гри:

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