Приклад рішення лабораторної роботи №7

Приклад рішення лабораторної роботи №7

На кожній з двох торгових баз асортиментний мінімум складає один і той же набір з n видів товарів. Магазини, позначимо їх А і В, конкурують між собою. Один і той же вид товару в обох магазинах продається за однією і тією ж ціною. Проте товар, що поставляється в магазин В, вищої якості. Якщо магазин А завезе з бази товар, відмінний від товару, завезеного в магазин В, то товар матиме попит і магазин А від його реалізації одержить прибуток с_j грошових одиниць. Якщо ж в магазини А і В завезені товари однакового вигляду, то товар в магазині А попиту мати не буде, оскільки такий же товар, за такою ж ціною, але вищої якості, можна купити в магазині В, і тому магазин А зазнає збитки по зберіганню і можливо псуванню товару у розмірі d_i грошових одиниць. Вимагається формалізувати конфліктну ситуацію, побудувати матрицю гри і дати рекомендації по вибору оптимальної змішаної стратегії.

Початкові дані задачі представлено в таблиці 1.1.

Таблиця 1.1 – Початкові дані задачі

n	c1	c2	c3	c1	d1	d2	d3	d1

1.1 Представимо задану ситуацію у вигляді матричної гри

Керівництво магазину А має чотири стратегії стосовно своїх майбутніх дій:

- А₁ продавати товар першого виду;

- А₂ продавати товар другого виду;

- А₃ продавати товар третього виду;

- А₁ продавати товар четвертого виду.

Аналогічно, керівництво магазину В має чотири стратегії:

- В₁ продавати товар першого виду;

- В₂ продавати товар другого виду;

- В₃ продавати товар третього виду;

- В₁ продавати товар четвертого виду.

Платіжна матриця даної гри представлена в таблиці 1.2.

Таблиця 1.2 – Платіжна матриця гри

	В1	В2	В3	В1
А1	-13
А2		-12
А3			-20
А1				-7

Визначимо, чи має гра оптимальне рішення в чистих стратегіях. Для цього розрахуємо верхню та нижню ціни гри.

Таблиця 1.3 – Верхня та нижня ціни гри

	В1	В2	В3	В4	a
А1	-13				-13
А2		-12			-12
А3			-20		-20
А4				-7	-7
b					-7

Отже:

(1.1)

Так як a ¹ b, то гра не має рішення в чистих стратегіях.

1.2 Знайдемо рішення гри в змішаних стратегіях

Для того щоб звести гру до пари двоїстих задач лінійного програмування, збільшимо всі елементи платіжної матриці на 20.

Таблиця 1.4 – Платіжна матриця

	В1	В2	В3	В4
А1
А2
А3
А4

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

Запишемо задачу лінійного програмування для гравця А, позначивши .

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

(1.5)

за умов:

(1.6)

Визначимо оптимальний план задачі. Для цього застосуємо алгоритм симплекс-методу.

1. Запишемо систему обмежень початкової задачі у канонічному вигляді

(1.7)

2. Векторна форма запису системи обмежень має вигляд:

де , , , , , , , , .

(1.8)

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

3. Розширена задача лінійного програмування буде такою:

(1.9)

У цій задачі t ₉, t ₁₀, t ₁₁ та t ₁₂ – базисні змінні, а t ₁, t ₂, t ₃, t ₄, t ₅, t ₆, t ₇, t ₈ – вільні. Нехай t ₁ = t ₂ = t ₃ = t ₄ = t ₅ = t ₆ = t ₇ = t ₈ =0, тоді t ₉ = t ₁₀ = t ₁₁ = t ₁₂ = 1.

Перший опорний план задачі:

Т0=(0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 1), Z0 = 4M.

(1.10)

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

5. З останньої симплекс-таблиці запишемо оптимальний план задачі:

Т0=(0,013; 0,017; 0,009; 0; 0; 0; 0; 0,387; 1; 1; 1; 1), Zmin = 0,039.

(1.11)

Перевіримо правильність рішення задачі за допомогою MS Excel (див.рис. 1.1-1.3).

Рисунок 1.1 – Результати рішення задачі лінійного програмування для гравця А засобами MSExcel

Рисунок 1.2 – Вікно «Пошуку рішення» з введеними вихідними параметрами задачі

Рисунок 1.2 – Вікно параметрів «Пошуку рішення»

Для визначення змішаної стратегії скористаємося формулою:

(1.12)

Звідси, змішана стратегія має вигляд:

(1.13)

Тобто, оптимальною стратегією магазину А буде продаж товарів у наступних пропорціях:

- 33,31% першого товару;

- 43,45% другого товару;

- 23,24% третього товару.

При цьому середній прибуток магазину складе 25,79 гр. од.

Додаток А

Таблиця А.1 – Рішення задачі лінійного програмування для гравця А

Базис	Cбаз	План									M	M	M	M	θ
x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10	x 11	x 12
x9	M						-1								0,02
x10	M							-1							0,02
x11	M								-1						–
x12	M									-1					0,02
Zj-cj≤0	4M	118M-1	101M-1	129M-1	88M-1	-M	-M	-M	-M
x3		0,02	0,16	0,72		0,58	-0,02				0,02				0,14
x10	M			-23				-1			-1				0,00
x11	M								-1						0,03
x12	M					-12				-1	-1				0,00
Zj-cj≤0	M+0,02	97M-0,84	8M-0,28		13M-0,42	2M-0.02	-M	-M	-M	-3M+0,02
x3		0,02		0,85		0,58	-0,03	0,01			0,03	-0,01			0,03
x1				-0,77			0,03	-0,03			-0,03	0,03			–
x11	M			59,37			-1,23	1,23	-1		1,23	-1,23			0,02
x12	M					-12				-1		-1
Zj-cj≤0	M+0,02		82,37M- -0,92		13M-0,42	-1,23M+ +0,01	2,23M- -0,03	-M	-M	0,23M- -0,01	-3,23M+ +0,03
x3		0,02				1,02	-0,03	-0,03		0,04	0,03	0,03		-0,04	0,022
x1						-0,4	0,03			-0,03	-0,03			0,03	–
x11	M					55,97	-1,23	-1,35	-1	2,58	1,23	1,35		-2,58	0,018
x2						-0,52		0,04		-0,04		-0,04		0,04	–
Zj-cj≤0	M+0,03				55,98M-0,9	-1,23M+ +0,01	-1,35M+ +0,01	-M	2,58M-0,04	0,23M-0,01	0,35M-0,02		-3,58M+ +0,04
x3		0,01					-0,01	-0,01	0,02	-0,01	0,01	0,01	-0,02	0,01	–
x1		0,01					0,03	-0,01	-0,01	-0,02	-0,03	0,01	0,01	0,02	–
x4		0,02					-0,02	-0,02	-0,02	0,05	0,02	0,02	0,02	-0,05	0,39
x2		0,01					-0,01	0,03	-0,01	-0,02	0,01	-0,03	0,01	0,02	–
Zj-cj≤0	0,039					-0,015	-0,01	-0,016	0,001	-M+0,015	-M+0,010	-M+0,016	-M-0,001
x3		0,009				0,225	-0,011	-0,012	0,014		0,011	0,012	-0,014
x1		0,013				0,323	0,017	-0,017	-0,01		-0,017	0,017	0,013
x8		0,387				21,686	-0,478	-0,522	-0,39		0,478	0,522	0,387	-1
x2		0,017				0,421	-0,021	0,021	-0,02		0,021	-0,021	0,017
Zj-cj≤0	0,039				-0,031	-0,014	-0,009	-0,016		-M+0,014	-M+0,009	-M+0,016	-M

Дата добавления: 2015-09-29