Стратегия решения задачи программирование

Пример решения матричной игры методом линейного программирования

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции 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)), поэтому он может быть гораздо более быстрым, чем линейный поиск.

Оптимизация использования памяти

Эффективное использование памяти является ключом к созданию быстрых и эффективных программ. Оптимизация использования памяти может включать в себя использование более компактных структур данных, совместное использование памяти и т.д.

Накопление опыта

Накопление опыта – это один из наиболее эффективных способов стать лучшим программистом. Чем больше задач вы решаете, тем проще для вас будет решать новые задачи и принимать более эффективные решения.

Выводы

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

Источник

Оцените статью