- Пример решения матричной игры методом линейного программирования
- Второй способ нахождений двойственной задачи
- Решение матричной игры симплексным методом
- Эффективные стратегии решения задач в программировании
- Исходные данные
- Алгоритмы
- Поиск
- Сортировка
- Динамическое программирование
- Рекурсия
- Алгоритмы оптимизации
- Мемоизация
- Двоичный поиск
- Оптимизация использования памяти
- Накопление опыта
- Выводы
Пример решения матричной игры методом линейного программирования
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
6x1 + 5x2 + 7x3≤1
10x1 + 4x2 + 7x3≤1
13x1 + 10x2 + 4x3≤1
7x1 + 11x2 + 5x3=1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 = 1
10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 = 1
13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 = 1
7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 = 1
Введем искусственные переменные x.
6x1 + 5x2 + 7x3 + 1x4 + 0x5 + 0x6 + 0x7= 1
10x1 + 4x2 + 7x3 + 0x4 + 1x5 + 0x6 + 0x7= 1
13x1 + 10x2 + 4x3 + 0x4 + 0x5 + 1x6 + 0x7= 1
7x1 + 11x2 + 5x3 + 0x4 + 0x5 + 0x6 + 1x7= 1
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = x1+x2+x3 — Mx7 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x7 = 1-7x1-11x2-5x3
которые подставим в целевую функцию:
F(X) = x1 + x2 + x3 — M(1-7x1-11x2-5x3) => max
или
F(X) = (1+7M)x1+(1+11M)x2+(1+5M)x3+(-1M) => max
Второй способ нахождений двойственной задачи
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда
Решение матричной игры симплексным методом
Найти решение матричной игры. Решить матричные игры симплексным методом.
Задание. Свести задачу, заданную платежной матрицей, к задаче линейного программирования (предварительно упростив задачу, убрав строго доминируемые стратегии, если это возможно) и решить симплекс методом.
Решение проводим с помощью калькулятора.
| Игроки | B1 | B2 | B3 | a = min(Ai) |
| A1 | 0 | 3 | 1 | 0 |
| A2 | 3 | 0 | 5 | 0 |
| A3 | 2 | 1 | 1 | 1 |
| b = max(Bi ) | 3 | 3 | 5 | 0 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 1, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0x1 + 3x2 + 2x3-1x4 + 0x5 + 0x6 = 1
3x1 + 0x2 + 1x3 + 0x4-1x5 + 0x6 = 1
1x1 + 5x2 + 1x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
0x1-3x2-2x3 + 1x4 + 0x5 + 0x6 = -1
-3x1 + 0x2-1x3 + 0x4 + 1x5 + 0x6 = -1
-1x1-5x2-1x3 + 0x4 + 0x5 + 1x6 = -1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6,
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,-1,-1,-1)
| План | Базис | B | x1 | x2 | x3 | x4 | x5 | x6 |
| 0 | x4 | -1 | 0 | -3 | -2 | 1 | 0 | 0 |
| x5 | -1 | -3 | 0 | -1 | 0 | 1 | 0 | |
| x6 | -1 | -1 | -5 | -1 | 0 | 0 | 1 | |
| Индексная строка | F(X0) | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A -1 =
Оптимальный план двойственной задачи равен:
y1 = 1 /3, y2 = 1 /3, y3 = 0
Z(Y) = 1* 1 /3+1* 1 /3+1*0 = 2 /3
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 2 /3 = 1 1 /2
Оптимальная стратегия игрока А: P( 1 /2 ; 1 /2; 0)
Оптимальная стратегия игрока B: Q( 1 /2; 1 /2; 0)
Пример №3 . Предприятие выпускает скоропортящуюся продукцию, которую сразу можно доставить потребителю (А1 стратегия). Отправить на склад для хранения (А2 стратегия) или подвергнуть обработке для длит. Хранения (А3 стратегия) . Потребитель может приобрести немедленно (В1 стратег) ,через некоторое время (В2 стратег) или после длительного периода (В3 стратегия).
В случае стратегий А2 и А3 предприятие несет дополнительные затраты на хранение и обработку продукции. Однако, при А2 следует вычесть убытки, если потребитель выберет стратегию В2 или В3 . Определить оптимальные пропорции для применения стратегий А1,А2,А3. Руководствуясь минимаксным критерием, гарантирует средний уровень убытка. Пользуясь минимальным критерием из таблицы.
| Игроки | B1 | B2 | B3 | a = min(Ai) |
| A1 | 2 | 3 | 2 | 2 |
| A2 | 4 | 2 | 1 | 1 |
| A3 | 1 | 3 | 3 | 1 |
| b = max(Bi ) | 4 | 3 | 3 | 0 |
Решение матричной игры находим через сервис решение матричной игры.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2 Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
2x1+4x2+x3 >= 1
3x1+2x2+3x3 >= 1
2x1+x2+3x3 >= 1
F(x) = x1+x2+x3 = min
найти максимум функции Ф(y) при ограничениях:
2y1+3y2+2y3 4y1+2y2+y3 y1+3y2+3y3 Ф(y) = y1+y2+y3 = max
Решаем эти системы симплекс-методом.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
2x1 + 4x2 + x3≥1
3x1 + 2x2 + 3x3≥1
2x1 + x2 + 3x3≥1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 4x2 + 1x3-1x4 + 0x5 + 0x6 = 1
3x1 + 2x2 + 3x3 + 0x4-1x5 + 0x6 = 1
2x1 + 1x2 + 3x3 + 0x4 + 0x5-1x6 = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
-2x1-4x2-1x3 + 1x4 + 0x5 + 0x6 = -1
-3x1-2x2-3x3 + 0x4 + 1x5 + 0x6 = -1
-2x1-1x2-3x3 + 0x4 + 0x5 + 1x6 = -1
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 5 /11 = 2 1 /5
p1 = 2 1 /5•0 = 0
p2 = 2 1 /5• 2 /11 = 2 /5
p3 = 2 1 /5• 3 /11 = 3 /5
q1 = 2 1 /5• 2 /11 = 2 /5
q2 = 2 1 /5•0 = 0
q3 = 2 1 /5• 3 /11 = 3 /5
Оптимальная стратегия игрока А: P( 0; 2 /5; 3 /5)
Оптимальная стратегия игрока B: Q( 2 /5;0; 3 /5)
Эффективные стратегии решения задач в программировании
Программирование — это наука о создании программных продуктов. Хотя задачи могут быть разнообразными, процесс решения может быть описан эффективными стратегиями.
Исходные данные
Стратегии решения задач в программировании будут зависеть от исходных данных. Обычно их можно разбить на несколько категорий:
Алгоритмы
Поиск
Поиск является одним из наиболее часто встречающихся алгоритмов. Он включает поиск определенного элемента или паттерна в множестве данных. Существует несколько подходов к решению задач поиска, включая:
Сортировка
Алгоритмы сортировки также часто используются. Они обеспечивают упорядочивание элементов в заданном наборе данных. Некоторые из алгоритмов сортировки включают:
- Сортировка выбором
- Сортировка вставками
- Быстрая сортировка
- Сортировка слиянием
Динамическое программирование
Динамическое программирование – это метод оптимизации поиска решения. С его помощью можно решать задачи, которые могут быть подразделены на более мелкие подзадачи и которые могут быть решены повторно с использованием результатов предыдущих вычислений. Это может значительно ускорить поиск решений некоторых сложных задач.
Рекурсия
Рекурсия – это техника программирования, при которой функция вызывает саму себя. Этот подход особенно полезен, когда нужно решить задачу, которая может быть разделена на несколько подзадач. Рекурсивный подход позволяет создавать компактный, понятный и универсальный код.
Алгоритмы оптимизации
Мемоизация
Мемоизация – это техника, которая помогает избежать повторных вычислений. Если результат вычисления функции может быть сохранен, он сохраняется, и при следующем вызове функции сохраненный результат будет использован вместо повторного вычисления.
Двоичный поиск
Двоичный поиск – это алгоритм, который используется для поиска элемента в отсортированном массиве. Он имеет сложность O(log(n)), поэтому он может быть гораздо более быстрым, чем линейный поиск.
Оптимизация использования памяти
Эффективное использование памяти является ключом к созданию быстрых и эффективных программ. Оптимизация использования памяти может включать в себя использование более компактных структур данных, совместное использование памяти и т.д.
Накопление опыта
Накопление опыта – это один из наиболее эффективных способов стать лучшим программистом. Чем больше задач вы решаете, тем проще для вас будет решать новые задачи и принимать более эффективные решения.
Выводы
Существует множество подходов к решению задач в программировании. Выбор правильной стратегии зависит от конкретных условий исходных данных. Однако эффективное использование алгоритмов, алгоритмов оптимизации и оптимизации использования памяти могут помочь создавать более быстрые и эффективные программные продукты.