Лабораторна робота № 8.

Симплекс-метод розв’язування задач

Лінійного програмування

Теоретичні відомості

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

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

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

2. Побудова симплексної таблиці.

3. Перевірка опорного плану на оптимальність за допомогою оцінок Z_j – C_j. Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок Z_j – C_j не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.

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

5. Повторення дій починаючи з п. 3.

Завдання лабораторної роботи

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

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.

Лабораторна робота № 9. Розв’язування матричних ігор Теоретичні відомості

Основна теорема теорії ігор. Кожна скінчена гра має, принаймні, один розв’язок, можливо, в області мішаних стратегій.

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

, .

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

, .

Найбільш проста матрична гра – це гра, у якій кожен з гравців має дві стратегії. Матриця А гри має вигляд:

Якщо сідлової точки немає, то розв’язком гри є змішані стратегії ,;, а також ціну гри, знаходимо з системи рівнянь

, а також ціну гри , знаходимо з системи рівнянь

Завдання лабораторної роботи

Розв’язати матричну гру.

1.		2.		3.
4.		5.		6.
7.		8.		9.
10.		11.		12.
13.		14.		15.
16.		17.		18.
19.		20.		21.
22.		23.		24.
25.		26.		27.
28.		29.		30.