Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С Builder 6.
Общее в моделях то, что во всех случаях модель в определенном смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования. В любом случае модель строится для с целью узнать про объект что - либо новое или сохранить об объекте информацию, которая может стать недоступной в будущем. Как правило, процесс изучения, связанный с использованием моделей и называемый моделированием не заканчивается созданием одной модели. Построив модель и получив с ее помощью, какие - либо результаты, соотносят их с реальностью и если это соотношение дает неудовлетворительные результаты, то в построенную модель вносят коррективы или даже создают другую модель.Математическая модель - приближенное описание объекта моделирования, выраженное с помощью математической символики. Математические модели появились вместе с математикой много веков назад. Применение вычислительных машин позволило проанализировать и применить на практике многие математические модели, которые раньше не поддавались аналитическому исследованию. Реализованная на компьютере математическая модель называется компьютерной математической моделью, а проведение целенаправленных расчетов с помощью компьютерной модели называется вычислительным экспериментом. 2. модель нужна для того, чтобы научиться управлять объектом (или процессом) и определить наилучшие способы управления при заданных целях и критериях (управление);Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей дает матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хм), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям. Поскольку первый игрок стремится найти такие значения хі и, следовательно, pi , чтобы цена игры uбыла максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры uбыла наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которыхМатричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков. Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 - свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш aij за счет игрока 2 (если aij< 0, то это значит, что игрок 1 платит второму сумму | aij | ). А = то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счет игрока 2) выигрыша aij. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2 aij (i = ) т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = io, при которой этот минимальный выигрыш будет максимальным, т.е. находится aij = = (1). Поэтому для игрока 2 отыскивается aij , т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит aij = = (2).Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x - это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям xi >= 0 (i = 1,m), = 1. Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока. Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют равенствуНормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы продукции приведены в таблице: Продукция/сырье А В С Запасы сырья, ед. Подсчитаем затраты сырья: Сырье 1-го типа: 4 х1 2 х2 0 х3 , по условию затраты не превосходят 19, Сырье 2-го типа: 0 х1 1 х2 1 х3, по условию затраты не превосходят 8, Сырье 3-го типа: 1x1 2x2 0x3, по усло
План
Содержание
Содержание
1. Пояснительная записка
1.1.Введение
2. Теоретическая часть
2.1 Элементы теории матричных игр
2.2 Решение матричных игр в чистых стратегиях
2.3 Решение матричных игр в смешанных стратегиях путем сведения к задаче линейного программирования
3. Практическая часть
3.1 Построение математической модели задачи
3.2 Выбор метода решения и привидения задачи к каноническому виду
3.3 Решение задачи путем сведения к задаче линейного программирования
- Блок схема к поставленной задачи
- Программа к поставленной задачи (программный код)
3.4 Анализ результата решения поставленной задачи
4. Вывод курсового проектирования
Заключение
Список основных источников
Введение
1 Математические методы
Математическое моделирование как инструмент познания завоевывает все новые и новые позиции в различных областях деятельности человека. Оно становится главенствующим направлением в проектировании и исследовании новых систем, анализе свойств существующих систем, выборе и обосновании оптимальных условий их функционирования и т.п.
Изучение математического моделирования открывает широкие возможности для осознания связи информатики с математикой и другими науками. Абстрактное моделирование с помощью компьютеров - вербальное, информационное, математическое - в наши дни стало одной из информационных технологий в познавательном плане исключительно мощной.
Общее в моделях то, что во всех случаях модель в определенном смысле заменяла сам исследуемый объект. Вместо исходного объекта (оригинала) использовалась его модель, модель являлась представлением объекта в некоторой форме, отличной от формы его реального существования.
Модель - это материальный или идеальный объект, который строится для изучения исходного объекта (оригинала) и который отражает наиболее важные качества и параметры оригинала.
Практически во всех науках о природе, живой и неживой, об обществе, построение и использование моделей является мощным орудием познания. Реальные объекты и процессы бывают столь многообразны и сложны, что лучшим способом изучения часто является построение модели, отражающей лишь какую - то часть реальности.
В любом случае модель строится для с целью узнать про объект что - либо новое или сохранить об объекте информацию, которая может стать недоступной в будущем.
Как правило, процесс изучения, связанный с использованием моделей и называемый моделированием не заканчивается созданием одной модели. Построив модель и получив с ее помощью, какие - либо результаты, соотносят их с реальностью и если это соотношение дает неудовлетворительные результаты, то в построенную модель вносят коррективы или даже создают другую модель. В случае достижения хорошего соответствия с реальностью выясняют границы применения модели. Это очень важный вопрос, он решается путем сравнения модели с оригиналом путем сравнения предсказаний, полученных с помощью компьютерной модели. Если это сравнение дает удовлетворительные результаты, то модель принимают на вооружение, если нет, приходится создавать другую модель.
Математическое моделирование относится к классу знакового моделирования, при этом модели могут создаваться из любых математических объектов, чисел, функций, уравнений, графиков, графов.
Практически во всех науках построение и использование моделей является мощным орудием познания.
В моделировании существует два пути: Модель может быть похожей копией объекта, выполненной из другого материала и в другом масштабе, с отсутствием ряда деталей.
Модель может отражать реальность более абстрактно - словесным описанием формализованным по каким - то правилам, соотношениям.
Существует следующая классификация абстрактных моделей: Вербальные
Эти модели используют последовательности предложений на формализованных диалектах естественного языка для описания той или иной области действительности.
Математические
Это очень широкий класс знаковых моделей, основанных на формальных языках над конечными алфавитами, широко использующих те или иные математические методы.
Информационные
Это класс знаковых моделей описывающих информационные процессы в системах самой разнообразной природы.
Граница между вербальными, математическими и информационными моделями может быть проведена весьма условно; можно считать информационные методики подклассом математических моделей.
Математическая модель выражает существенные черты объекта или процесса языком уравнений и других математических средств. Огромный толчок развитию математическому моделированию дало появление ЭВМ, хотя сам метод появился тысячи лет назад.
Понятие «аналитическое» решение и «компьютерное» решение не противостоят друг другу, так как: Все чаще компьютеры при математическом моделировании используются не только для численных расчетов, но и для аналитических преобразований.
Результат аналитического исследования часто выражен в столь сложной форме, что при взгляде на нее не складывается восприятие описываемого ею процесса. Эту формулу можно протабулировать, представить графически, проиллюстрировать в динамике, то есть проделать то, что называется визуализацией абстракции.
2 Симплекс метод решения задач линейного программирования
Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.
Для привидения системы ограничений неравенств к каноническому виду, необходимо в системе ограничений выделить единичный базис.
Ограничения вида «?»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом « 1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».
Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - « M», при Fmax - «-M»).
Ограничения вида «?» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.
Алгоритм симплекс метода.
(первая симплекс таблица)
Пусть система приведена к каноническому виду.
X1 q1,m 1 Xm 1 …. q1,m n Xm n = h1
X2 q1,m 1 Xm 1 …. q1,m n Xm n = h1
X3 q1,m 1 Xm 1 …. q1,m n Xm n = h1
……………………………………………………………….
Xm qm,m 1 Xm 1 …. qm,m n Xm n =hm
В ней m базисных переменных, k свободных переменных. m k=n - всего переменных.
Fmin= C1X1 C2X2 C3X3 .... CNXN
Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m 1,m 2,...,m k). При этом все базисные переменные Xi=Hi.
Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица 3.1).
Первый столбец- коэффициенты в целевой функции при базисных переменных.
Второй столбец - базисные переменные.
Третий столбец - свободные члены (hi?0).
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».
Для первой итерации F0= ??ci*hi.
?????????????????m - оценки они рассчитываются по формуле: ??j = ? ciqij-cj.
Индексная строка позволяет нам судить об оптимальности плана: При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.
При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.
Переход ко второй итерации: Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.
Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.
Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца.
На пересечении строки и столбца находится разрешающий элемент.
На этом этапе осуществляется к переходу к последующим итерациям.
Переход к итерациям: Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом.
Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент.
Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения.
Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию.
Остальные элементы переносятся по формуле:
Метод искусственного базиса.(Вторая симплекс таблица)
При использовании искусственного базиса необходимо добиваться выхода искусственных переменных из базиса и введение в него независимых переменных. Для этой цели можно также использовать симплекс метод, причем решение распадается на две фазы: Построение искусственного базиса и оптимизация функции суммы искусственных переменных, т.е. F0=Y1 Y2 … Yn = 0 (F?min). Если при этом F0=0, то искусственный базис мы вывели из состава переменных, переходим ко второй фазе - решаем задачу по первой симплекс таблице с действительными переменными. Если же F0?0, т.е. искусственный базис не выведен из состава переменных - ОЗЛП решений не имеет.
Решение преобразованной системы ограничений с заданной целевой функцией и действительными переменными. При этом столбцами искусственных переменных в симплекс методе пренебрегаем.
Замечания: При решении задач на max с искусственным базисом следует переходить к решению на min, меняя лишь только целевую функцию: Fmax = - Fmin.
При решении ЗЛП с искусственным базисом особое внимание следует обратить на вычисление элементов индексных строк. a) Для столбцов X вычисление элементов идет по формулам: ??j = ? qij.
? yi = y1 y2 … YR.
?Hi=F0.
Примечание: только для строк Y. б) Для столбцов Y работает старая формула: ??j = ? ciqij-cj.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
