Реферат: Линейное программирование

Содержание

Содержание

1.Пояснительная записка

1.1.Введение

2.Теоретическая часть

2.1 Элементы теории матричных игр

2.2 Решение матричных игр в чистыхстратегиях

2.3 Решение матричных игр в смешанныхстратегиях путём сведения к задаче линейного программирования

3. Практическая часть

3.1 Построение математической моделизадачи

3.2 Выбор метода решения и привидениязадачи к каноническому виду

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

— Блок схема к поставленной задачи

— Программа к поставленной задачи(программный код)

3.4 Анализ результата решенияпоставленной задачи

4. Вывод курсового проектирования

Заключение

Список основных источников

1. Пояснительнаязаписка курсового проектирования

Цель данного курсового проекта — составить план производства требуемойпродукции, обеспечивающий максимальную прибыль от выпускаемой продукции, свестиданную задачу к задаче линейного программирования, решить её симплекс — методоми составить программу для решения задачи этим методом на ЭВМ.

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА 1.1 Математическоепрограммирование.

Математическое программирование занимается изучение экстремальных задач ипоиском методов их решения. Задачи математического программированияформулируются следующим образом: найти экстремум некоторой функции многихпеременных f ( x1, x2,…, xn ) при ограничениях gi ( x1, x2,…, xn ) ( bi, где gi — функция, описывающая ограничения, ( — один из следующих знаков (, (, (, а bi — действительное число, i = 1,…, m. f называется функцией цели (целевая функция ). Линейное программирование — это раздел математическогопрограммирования, в котором рассматриваются методы решения экстремальных задачс линейным функционалом и линейными ограничениями, которым должны удовлетворятьискомые переменные. Задачу линейного программирования можно сформулировать так. Найти max [pic] при условии: a11 x1 + a12 x2 +… + a1n xn ( b1; a21 x1 + a22 x2 +… + a2n xn ( b2;….… am1 x1 + am2 x2 +… + amn xn( bm; x1 ( 0, x2 ( 0,..., xn ( 0. Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то даннаяформа называется канонической. В матричной форме задачу линейногопрограммирования, записывают следующим образом. Найти max cT x при условии A x( b; x ( 0, где А — матрица ограничений размером (m(n), b(m(1) — вектор-столбец свободных членов, x(n ( 1) — вектор переменных, сТ = [c1, c2,…, cn ] — вектор-строка коэффициентов целевой функции. Решение х0 называетсяоптимальным, если для него выполняется условие сТ х0 ( сТ х, для всех х (R(x). Поскольку min f(x) эквивалентен max [ — f(x) ], то задачу линейногопрограммирования всегда можно свести к эквивалентной задаче максимизации. Для решениязадач данного типа применяются методы:

1) графический;

2) табличный ( прямой, простой ) симплекс — метод;

3) метод искусственного базиса;

4) модифицированный симплекс — метод;

5) двойственный симплекс — метод.

1.2 Табличный симплекс — метод Для его применения необходимо, чтобы знакив ограничениях были вида “ меньше либо равно ”, а компоненты вектора b — положительны. Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введениядополнительных переменных для приведения неравенств к равенствам.

2. Если в исходной системе ограничений присутствовали знаки “ равно ” или“ больше либо равно ”, то в указанные ограничения добавляются искусственныепеременные, которые так же вводятся и в целевую функцию со знаками,определяемыми типом оптимума.

3. Формируется симплекс-таблица.

4. Рассчитываются симплекс- разности.

5. Принимается решение об окончании либо продолжении счёта.

6. При необходимости выполняются итерации.

7. На каждой итерации определяется вектор, вводимый в базис, и вектор,выводимый из базиса. Таблица пересчитывается по методу Жордана Гаусса иликаким-нибудь другим способом.

1.3 Метод искусственного базиса. Данный метод решения применяется приналичии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либоравно ” и является модификацией табличного метода. Решение системы производитсяпутём ввода искусственных переменных со знаком, зависящим от типа оптимума,т.е. для исключения из базиса этих переменных последние вводятся в целевуюфункцию с большими отрицательными коэффициентами, а в задачи минимизации сположительными. Таким образом, из исходной получается новая задача. Если воптимальном решении задачи нет искусственных переменных, это решение естьоптимальное решение исходной задачи. Если же в оптимальном решении задачи хотьодна из искусственных переменных будет отлична от нуля, то система ограниченийисходной задачи несовместна и исходная задача неразрешима.

1.4 Модифицированный симплекс-метод. В основу данной разновидностисимплекс-метода положены такие особенности линейной алгебры, которые позволяютв ходе решения задачи работать с частью матрицы ограничений. Иногда методназывают методом обратной матрицы. В процессе работы алгоритма происходитспонтанное обращение матрицы ограничений по частям, соответствующим текущимбазисным векторам. Указанная способность делает весьма привлекательной машиннуюреализацию вычислений вследствие экономии памяти под промежуточные переменные изначительного сокращения времени счёта. Хорош для ситуаций, когда числопеременных n значительно превышает число ограничений m. В целом, метод отражаеттрадиционные черты общего подхода к решению задач линейного программирования,включающего в себя канонизацию условий задачи, расчёт симплекс -разностей,проверку условий оптимальности, принятие решений о коррекции базиса иисключение Жордана Гаусса. Особенности заключаются в наличии двух таблиц — основной и вспомогательной, порядке их заполнения и некоторой специфичностирасчётных формул.

ПОСТАНОВКА ЗАДАЧИ:

Дляпроизводства трёх видов продукции используется три вида сырья. Нормы затраткаждого из видов сырья на единицу продукции данного вида, запасы сырья, а такжеприбыль с единицы продукции.

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

Соответственно:

1. Первое с чего начинаем, это строим математическую модельзадачи;

2.Выбираем метод решения задачи и приводим задачу к каноническому виду;

3.Решаем задачу путём сведения к задаче линейного программирования;

4.Затем строим блок схему к задачи с написанием программы на языке С++Builder 6.;

5.Дальнейшим этапом моей работы будет анализ результата решения выполненной мноюзадачи.

1.1 Введение

1 Математические методы

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

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

Общее в моделях то, чтово всех случаях модель в определённом смысле заменяла сам исследуемый объект.Вместо исходного объекта (оригинала) использовалась его модель, модель являласьпредставлением объекта в некоторой форме, отличной от формы его реальногосуществования.

Модель – это материальныйили идеальный объект, который строится для изучения исходного объекта(оригинала) и который отражает наиболее важные качества и параметры оригинала.

Практически во всехнауках о природе, живой и неживой, об обществе, построение и использованиемоделей является мощным орудием познания. Реальные объекты и процессы бываютстоль многообразны и сложны, что лучшим способом изучения часто являетсяпостроение модели, отражающей лишь какую – то часть реальности.

В любом случае модельстроится для с целью узнать про объект что – либо новое или сохранить обобъекте информацию, которая может стать недоступной в будущем.

Как правило, процессизучения, связанный с использованием моделей и называемый моделированием незаканчивается созданием одной модели. Построив модель и получив с её помощью,какие – либо результаты, соотносят их с реальностью и если это соотношение даётнеудовлетворительные результаты, то в построенную модель вносят коррективы илидаже создают другую модель. В случае достижения хорошего соответствия среальностью выясняют границы применения модели. Это очень важный вопрос, он решаетсяпутём сравнения модели с оригиналом путём сравнения предсказаний, полученных спомощью компьютерной модели. Если это сравнение даёт удовлетворительные результаты,то модель принимают на вооружение, если нет, приходится создавать другую модель.

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

Практически во всехнауках построение и использование моделей является мощным орудием познания.

В моделированиисуществует два пути:

Модель может быть похожейкопией объекта, выполненной из другого материала и в другом масштабе, сотсутствием ряда деталей.

Модель может отражатьреальность более абстрактно – словесным описанием формализованным по каким – топравилам, соотношениям.

Существует следующаяклассификация абстрактных моделей:

Вербальные

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

Математические

Это очень широкий классзнаковых моделей, основанных на формальных языках над конечными алфавитами,широко использующих те или иные математические методы.

Информационные

Это класс знаковыхмоделей описывающих информационные процессы в системах самой разнообразнойприроды.

Граница междувербальными, математическими и информационными моделями может быть проведенавесьма условно; можно считать информационные методики подклассом математическихмоделей.

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

Понятие «аналитическое»решение и «компьютерное» решение не противостоят друг другу, так как:

Всё чаще компьютеры приматематическом моделировании используются не только для численных расчётов, нои для аналитических преобразований.

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

2Симплексметод решения задач линейного программирования

Симплекс метод — универсальный метод для решения линейной системы уравнений или неравенств илинейного функционала.

Для привидения системыограничений неравенств к каноническому виду, необходимо в системе ограниченийвыделить единичный базис.

I. Ограничения вида «»-ресурсные ограничения. Справа находится то что мы используем на производстве,слева — то что получаем. При таких ограничения вводят дополнительные переменныес коэффициентом «+1», образующие единичный базис. В целевую функцию этипеременные войдут с коэффициентом «0».

II. Ограничениявида «=». Часто бывает, что несмотря на то что ограничения имеют видравенства, единичный базис не выделяется или трудно выделяется. В этом случаевводятся искусственные переменные для создания единичного базиса — Yi. В систему ограничений они входят скоэффициентом «1», а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin — «+M», при Fmax — «-M»).

III. Ограничениявида «» — Плановые ограничения. Дополнительные переменные (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).

Таблица 1.

C Б H C1 C2 … Cm Cm+1 … Cm+k X1 X2 … Xm Xm+1 … Xm+k C1

q1,m+1

q2,m+1

q3,m+1

qm,m+1

q1,m+k

q2,m+k

q3,m+k

qm,m+k

F= F0   … m m+1 … m+k

Первый столбец- коэффициентыв целевой функции при базисных переменных.

Второй столбец — базисныепеременные.

Третий столбец — свободные члены (hi0).

Самая верхняя строка — коэффициенты при целевой функции.

Вторая верхняя строка — сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплексметода — система коэффициентов из уравнения.

Последняя строка — служитдля того, чтобы ответить на вопрос: «оптимален план или нет».

Для первой итерации F0= ci*hi.

m — оценки они рассчитываются поформуле:

j =  ciqij-cj.

Индексная строкапозволяет нам судить об оптимальности плана:

1. При отыскании Fmin в индексной строке должны бытьотрицательные и нулевые оценки.

2. При отыскании Fmax в индексной строке должны бытьнулевые и положительные оценки.

Переход ко второйитерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую(главную) строку.

Ключевым столбцомявляется тот в котором находится наибольший положительный элемент индекснойстроки при отыскании Fminили наименьший отрицательный элемент при отыскании Fmax.

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

На пересечении строки истолбца находится разрешающий элемент.

На этом этапеосуществляется к переходу к последующим итерациям.

Переход к итерациям:

1. Выводится базис ключевой строки,уступая место переменной из ключевого столбца со своим коэффициентом.

2. Заполняется строка вновь введенногобазиса путем деления соответствующих элементов выделенной строки предыдущейитерации на разрешающий элемент.

3. Если в главной строке содержитсянулевой элемент, то столбец, в котором находиться этот элемент переноситься впоследующую итерацию без изменения.

4. Если в главном столбце имеетсянулевой элемент, то строка, в которой он находиться переноситься без измененияв последующую итерацию.

5. Остальные элементы переносятся поформуле:

Метод искусственногобазиса.(Втораясимплекс таблица)

При использованииискусственного базиса необходимо добиваться выхода искусственных переменных избазиса и введение в него независимых переменных. Для этой цели можно такжеиспользовать симплекс метод, причем решение распадается на две фазы:

I. Построениеискусственного базиса и оптимизация функции суммы искусственных переменных,т.е. F0=Y1+Y2+…+Yn = 0 (Fmin). Если при этом F0=0, то искусственный базис мы вывели из состава переменных,переходим ко второй фазе – решаем задачу по первой симплекс таблице сдействительными переменными. Если же F00, т.е. искусственныйбазис не выведен из состава переменных – ОЗЛП решений не имеет.

II. Решение преобразованнойсистемы ограничений с заданной целевой функцией и действительными переменными.При этом столбцами искусственных переменных в симплекс методе пренебрегаем.

Замечания:

1. При решении задач на max с искусственным базисом следуетпереходить к решению на min,меняя лишь только целевую функцию:

Fmax = — Fmin.

2. При решении ЗЛП с искусственнымбазисом особое внимание следует обратить на вычисление элементов индексныхстрок.

a) Для столбцов X вычисление элементов идет поформулам:

j =  qij.

 yi = y1+y2+…+yR.

Hi=F0.

Примечание: только длястрок Y.

б) Для столбцов Y работает старая формула:

j =  ciqij-cj.

2. Теоретическая часть

Математические модели

Математическаямодель — приближенное описание объекта моделирования, выраженное с помощью математическойсимволики.

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

Этапы компьютерного математического моделирования изображены на рисунке (1). Первый этап —определениецелей моделирования. Этицели могут быть различными:

1. модель нужна длятого, чтобы понять, как устроен конкретный объект, какова его структура,основные свойства, законы развития и взаимодействия с окружающим миром(понимание);

2. модель нужна длятого, чтобы научиться управлять объектом (или процессом) и определить наилучшиеспособы управления при заданных целях и критериях (управление);

3. модель нужна длятого, чтобы прогнозировать прямые и косвенные последствия реализации заданныхспособов и форм воздействия на объект (прогнозирование).

4. Построение математической модели. На этом этапе происходитпереход от абстрактной формулировки модели к формулировке, имеющей конкретноематематическое представление. Математическая модель — это уравнения, системыуравнений, системы неравенств, дифференциальные уравнения или системы такихуравнений .

Классификацияматематических моделей

В основу классификацииматематических моделей можно положить различные принципы. Можноклассифицировать модели по отраслям наук (математические модели в физике,биологии, социологии и т.д.). Можно классифицировать по применяемомуматематическому аппарату (модели, основанные на применении обыкновенныхдифференциальных уравнений, дифференциальных уравнений в частных производных,стохастических методов, дискретных алгебраических преобразований и т.д.).

Наконец, если исходить изобщих задач моделирования в разных науках безотносительно к математическомуаппарату, наиболее естественна такая классификация:

● дескриптивные (описательные)модели;

● оптимизационныемодели;

● многокритериальные модели;

● игровые модели.

Рис. (1).Блок схема математического моделирования.

2.1 Элементы теории матричных игр

СВЕДЕНИЕМАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Предположим, что цена игры положительна (u > 0). Еслиэто не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементамматрицы выигрышей даёт матрицу сположительными элементами, и следовательно, с положительным значением ценыигры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласносвойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2и цена игры u должны удовлетворять соотношениям.

/> />

Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :

/> />, /> />,

Тогда (1) и (2) перепишется в виде :

/>, />, />, />,

/>, />, />, />.

Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi, чтобы цена игры uбыламаксимальной, то решение первой задачи сводится к нахождению такихнеотрицательных значений pi />, при которых

/>, />. />

Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры uбыланаименьшей, то решение второй задачи сводится к нахождению такихнеотрицательных значений qj, />, при которых

/>, />. />

Формулы (3) и (4) выражают двойственные друг другу задачи линейногопрограммирования (ЛП).

Решив эти задачи, получим значения pi />, qj /> и u.Тогдасмешанные стратегии, т.е. xi и yj получаются по формулам :

/> />

Пример. Найти решение игры, определяемой матрицей.

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач :

/> />

Решим вторую из них

Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение -1 -1 -1 0 0 0 0 -3 q4 1 2 0 1 0 0 1 5 — q5 1 0 1 0 1 0 1 4

q6 2 1 0 0 0 1 1 5 — Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение 0 -1 0 0 1 0 1 1 q4 1 2 0 1 0 0 1 5

q3 1 0 1 0 1 0 1 4 — q6 2 1 0 0 0 1 1 5

Б.п. q1 q2 q3 q4 q5 q6 Решение a Отношение

0 0

1 0

0 0

q3 1 0 1 0 1 0 1 4 q6

0 0

0 1

Из оптимальной симплекс-таблицы следует, что/>

(q1, q2, q3) = (0;/>; 1),

а из соотношений двойственности следует, что

( p1, p2, p3) = (/>; 1; 0).

Следовательно, цена игры с платёжной матрицей А1 равна

/>. />,

а игры с платёжной матрицей А :

/>.

При этом оптимальные стратегии игроков имеют вид:

Х = (х1,х2, х3) = (uр1; uр2; uр3)= />= />

Y = (y1, y2, y3) = (uq1; uq2; uq3) = />= />.

2.2 Решение матричных игр в чистых стратегиях

Матричная игра двух игроков с нулевой суммой может рассматриваться какследующая абстрактная игра двух игроков.

Первый игрок имеет m стратегийi = 1,2,...,m,второй имеет n стратегий j = 1,2,...,n. Каждойпаре стратегий (i,j) поставленов соответствие число аij, выражающее выигрыш игрока1 за счёт игрока 2, если первый игрок примет свою i-юстратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-юстратегию (i=/>), 2 – свою j-юстратегию (j=/>), после чего игрок 1получает выигрыш аij засчёт игрока 2 (если аij<0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается.

Каждая стратегия игрока i=/>; j = /> частоназывается чистой стратегией.

Если рассмотреть матрицу

А = />

то проведение каждой партии матричной игры с матрицей А сводитсяк выбору игроком 1 i-й строки,а игроком 2 j-го столбца иполучения игроком 1 (за счёт игрока 2) выигрыша аij.

Главным в исследовании игр является понятие оптимальных стратегийигроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрокаявляется оптимальной, если применение этой стратегии обеспечивает емунаибольший гарантированный выигрыш при всевозможных стратегиях другого игрока.Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значенияi (i =/>) определяется минимальноезначение выигрыша в зависимости от применяемых стратегий игрока 2

/>аij (i = />)

т.е. определяется минимальный выигрыш для игрока 1 при условии, что онпримет свою i-ю чистую стратегию, затем из этихминимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будетмаксимальным, т.е. находится

/>/>аij = />= /> (1).

Определение. Число />, определённое по формуле (1)называется нижней чистой ценой игры ипоказывает, какой минимальный выигрыш может гарантировать себе игрок 1,применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможностиза счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому дляигрока 2 отыскивается

/>аij, т.е. определяется max выигрышигрока 1, при условии, что игрок 2 применит свою j-ючистую стратегию,

затем игрок 2 отыскивает такую свою j = j1 стратегию,при которой игрок 1 получит min выигрыш, т.е. находит

/>/>aij = />= /> (2).

Определение. Число />, определяемое по формуле (2),называется чистой верхней ценой игры ипоказывает, какой максимальный выигрыш за счёт своих стратегий может себегарантировать игрок 1.

Другими словами, применяя свои чистые стратегии игрок 1 может обеспечитьсебе выигрыш не меньше />, а игрок 2 за счётприменения своих чистых стратегий может не допустить выигрыш игрока 1 больше,чем />.

Определение. Если в игре с матрицей А />=/>, то говорят, что этаигра имеет седловую точку вчистых стратегиях и чистую цену игры

u = />=/>.

Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, прикоторых достигается равенство /> = />. В это понятие вложен следующийсмысл: если один из игроков придерживается стратегии, соответствующей седловойточке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии,соответствующей седловой точке. Математически это можно записать и иначе:

/> />

где i, j – любыечистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент /> является минимальным в iо-йстроке и максимальным в jо-м столбце в матрице А. Отыскание седловой точкиматрицы А происходит следующим образом: в матрице А последовательно в каждой строке находятминимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловойэлемент, а пара стратегий, ему соответствующая, образует седловую точку. Парачистых стратегий (iо,jо)игроков 1 и 2, образующая седловую точку и седловой элемент />, называется решением игры. При этом iо и jоназываются оптимальными чистыми стратегиями соответственно игроков 1 и2.

2.3 Решение матричных игр в смешанных стратегиях путёмсведения к задаче линейного программирования

Исследование в матричных играх начинается с нахождения её седловой точкив чистых стратегиях. Если матричная игра имеет седловую точку в чистыхстратегиях, то нахождением этой седловой точки заканчивается исследование игры.Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю иверхнюю чистые цены этой игры, которые указывают, что игрок 1 не долженнадеяться на выигрыш больший, чем верхняя цена игры, и можетбыть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решенийматричных игр следует искать в использовании секретности применения чистыхстратегий и возможности многократного повторения игр в виде партии. Этотрезультат достигается путём применения чистых стратегий случайно, сопределённой вероятностью.

Определение. Смешаннойстратегией игрока называется полный набор вероятностейприменения его чистых стратегий.

Таким образом, если игрок 1 имеет mчистых стратегий 1,2,...,m, то его смешанная стратегия x –это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям

xi >= 0 (i = 1,m), />= 1.

Аналогично для игрока 2, который имеет nчистых стратегий, смешанная стратегия y – это набор чисел

y = (y1, ..., yn), yj >= 0, (j = 1,n), />= 1.

Так как каждый раз применение игроком одной чистой стратегии исключаетприменение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являютсяединственными возможными событиями.

Чистая стратегия есть частный случай смешанной стратегии. Действительно,если в смешанной стратегии какая-либо i-я чистая стратегия применяется свероятностью 1, то все остальные чистые стратегии не применяются. И эта i-ячистая стратегия является частным случаем смешанной стратегии. Для соблюдениясекретности каждый игрок применяет свои стратегии независимо от выбора другогоигрока.

Определение. Средний выигрыш игрока 1 вматричной игре с матрицей А выражаетсяв виде математического ожидания его выигрышей

E (A,x, y) =/>= x A yT

Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой среднийвыигрыш Е (А, х, y), а второй – за счёт своихсмешанных стратегий стремится сделать Е (А, х, y) минимальным, т.е. для решенияигры необходимо найти такие х иy, при которых достигаетсяверхняя цена игры

/> Е (А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игрыдолжна быть

/> Е (А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводитсяследующее определение: оптимальнымисмешанными стратегиями игроков 1 и 2 называются такие наборы хо, уосоответственно, которые удовлетворяют равенству

/> Е (А, х, y) =/>Е (А, х,y) = Е (А, хо, уо).

Величина Е (А, хо, уо) называется при этом ценойигры и обозначается через u.

Имеется и другое определение оптимальных смешанных стратегий: хо, уо называютсяоптимальными смешанными стратегиями соответственно игроков 1 и 2, если ониобразуют седловую точку:

Е (А,х, уо)<= Е (А, хо,уо)<= Е (А, хо,у)

Оптимальные смешанные стратегии и цена игры называются решениемматричной игры.

Основная теорема матричных игр имеет вид :

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

/> Е (А, х, y) и /> Е (А, х,y) существуют и равны между собой.

Игра m × n в общемслучае не имеет наглядной геометрической интерпретации. Ее решение достаточнотрудоемко при больших m и n, однако принципиальных трудностей не имеет,поскольку может быть сведено к решению задачи линейного программирования.

Пусть игра m × n заданаплатежной матрицей p = (aij ), i = 1, 2, ..., m; j = 1, 2, ..., n.Игрок А обладает стратегиями A1, A2, ..., Am,игрок В — стратегиями B1, B2, ..., Bm.Необходимо определить оптимальные стратегии S*A = ( p*1,p*2, ...<sub/>, p*m ) и S*B = ( q*1, q*2, ...<sub/>, q*n ), где p*i,q*j — вероятности применения соответствующих чистых стратегий Ai, Bj, p*1 + p*2 +...+ p*m =1, q*1+ q*2 +...+ q*n = 1.

Оптимальная стратегия S*Aудовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш,не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равныйцене игры v, при оптимальной стратегии игрока B. Без ограничения общностиполагаем v > 0: этого можно добиться, сделав все элементы aij ≥0. Если игрок А применяет смешанную стратегию S*A = ( p*1,p*2, ...<sub/>, p*m ) против любой чистойстратегии Bj игрока В, то он получает средний выигрыш, или математическоеожидание выигрыша aj = a1j p1 + a2jp2 +...+ am j pm, о = 1, 2, ..., n (т.е.элементы j-го столбца платежной матрицы почленно умножаются на соответствующиевероятности стратегий A1, A2, ..., Am ирезультаты складываются).

Для оптимальной стратегииS*A все средние выигрыши не меньше цены игры v, поэтому получаемсистему неравенств:

/> (2.3.1)

Каждое из неравенствможно разделить на число v > 0. Введем новые переменные:

x1 = p1/v, x2= p2/v, ..., pm/v (2.3.2)

Тогда система (2.3.1)примет вид:

/> (2.3.3)

Цель игрока А — максимизировать свойгарантированный выигрыш, т.е. цену игры v.

Разделив на v ≠ 0 равенствоp1 + p2 + ...+ pm = 1, получаем, чтопеременные x1 (i = 1, 2, ..., m) удовлетворяют условию: x1+ x2 + ...+ xm = 1/v. Максимизация цены игры v эквивалентнаминимизации величины1/v, поэтому задача может быть сформулирована следующимобразом: определить значения переменных xi ≥ 0, i = 1, 2, ...,m, так, чтобы они удовлетворяли линейным ограничениям (2.3.3) и при этомлинейная функция

Z = x1 + x2 +...+ xm, (2.3.4)

обращалась в минимум. Это задача линейногопрограммирования. Решая задачу (2.3.3)—( 2.3.4), получаем оптимальное решение p*1+ p*2 + ...+ p*m и оптимальную стратегию SA.

Для определенияоптимальной стратегии S*B = (q*1 + q*2 + ...+ q*n)следует учесть, что игрок В стремится минимизировать гарантированный выигрыш,т.е. найти />.Переменные q1, q2, ..., qn удовлетворяютнеравенствам:

/> (2.3.5)

которые следуют из того,что средний проигрыш игрока В не превосходит цены игры, какую бы чистуюстратегию не применял, игрок А.
Если обозначить

yj = qj/v, j =1, 2, ..., n, (2.3.6)

то получим системунеравенств:

/> (2.3.7)

Переменные yj (1,2, ..., n) удовлетворяют условию />.

Игра свелась к следующейзадаче

Определить значенияпеременных yj ≥ 0, j = 1, 2, ..., n, которые удовлетворяютсистеме неравенств (2.3.7) и максимизируют линейную функцию

Z' = y1 + y2 +...+ yn, (2.3.8)

Решение задачи линейногопрограммирования (2.3.6), (2.3.7) определяет оптимальную стратегию S*B= (q*1 + q*2 + ...+ q*n). При этом цена игры

v = 1 / max, Z' = 1 / minZ (2.3.9)

Составив расширенныематрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что однаматрица получилась из другой транспонированием:

Таким образом, задачилинейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являютсявзаимно-двойственными. Очевидно, при определении оптимальных стратегий вконкретных задачах следует выбрать ту из взаимно-двойственных задач, решениекоторой менее трудоемко, а решение другой задачи найти с помощью теоремдвойственности.

3.Практическая часть

Постановказадачи: Для производства трёх видов продукции используется три вида сырья.Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасысырья, а также прибыль с единицы продукции приведены в таблице:

Продукция/сырьё А В С Запасы сырья, ед. I 4 2 ≤ 19 II 1 1 = 8 III 1 2 ≤ 24 Прибыль, ден. ед. 3 7 2 ≥ max

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

Вид таблицы по заданию поставленной задачи:

Вид сырья Нормы затрат сырья (кг) на единицу продукции

III

Цена единицы продукции (руб.) 3 7 2

Решениепоставленной задачи:

Предположим,что производится x1 изделий А,/>изделий В и />изделий С.Для определения оптимального плана производства нужно решить задачу,состоящую в максимизации целевой функции

3.1.Построим математическую модель задачи:

тогдафункция цели:

Z-0 = 3X1 + 7X2 + 2X3 – совокупная прибыль от продажи произведенной продукции,которую требуется максимизировать.

Подсчитаемзатраты сырья:

Сырье 1-готипа: 4 х1 + 2 х2 + 0 х3, по условию затраты не превосходят 19,

Сырье 2-готипа: 0 х1 + 1 х2 + 1 х3, по условию затраты не превосходят 8,

Сырье 3-готипа: 1x1 + 2x2 + 0x3, поусловию затраты не превосходят 24.

при следующихусловиях:

+ 2

≤ 19

+ 1

= 8 1

+ 2

≤ 24

X1, X2, X3 ≥ 0.

4X1+2X2+X4 ≤19

X2 + X3 +X5 = 8

X1+ 2X2+X6 ≤24

3.2 Выбираем метод решения и приводим задачу к каноническому виду:

Пришли кзадаче линейного программирования:

припишемкаждому из видов сырья, используемых для производства продукции. Тогда общая оценка сырья, используемого напроизводство продукции, составит:

Получилиматематическую модель. Необходимо максимизировать функцию цели ↓

Z-0 (x1, x2, x3) = 3X1 + 7X2 + 2X3 → max

Введем дополнительныепеременные X4, X5, X6.

Z-0= 3

+ 7

+ 2

à(max) при системе ограничений:

Преобразуем первоеограничение:

+ 2

= 19

+ 1

= 8 1

+ 2

= 24

Получили задачу:

4X1+2X2+X4 = 19

X2 + X3 +X5 = 8

X1+2X2 +X6 =24

3.3 Решаем задачу путем сведения к задаче линейного программирования:

Xi≥0; 0-Z= -3X1- -7X2--2X3

Приведем задачу к каноническойформе.

Задача линейногопрограммирования записана в канонической форме, если она формулируетсяследующим образом.

Требуется найти вектор />, доставляющиймаксимум линейной форме

при условиях

где />

Решимзадачу симплекс-методом

Строим начальную симплекс-таблицу:

Базисные переменные

Свободные члены

4 2 1 19

1 1 8

1 2 1 24 0-Z -3 -7 -2

Так как в столбцесвободных членов нет отрицательных элементов, то найдено допустимое решение.Так как в строке 0-Z естьотрицательные элементы, то полученное решение не оптимально. Для определенияведущего столбца найдем максимальный по модулю отрицательный элемент в строке0-Z (-7). А ведущая строка та, у которойнаименьшее положительное отношение свободного члена к соответствующему элементуведущего столбца.

Пересчитаем таблицу:

Базисные переменные

Свободные члены

-2 -2 1 3

1 1 1 8

1 -2 -2 1 8 0-Z -3 7 5 56

Так как в столбцесвободных членов нет отрицательных элементов, то найдено допустимое решение.Так как в строке 0-Z естьотрицательные элементы, то полученное решение не оптимально. Для определенияведущего столбца найдем максимальный по модулю отрицательный элемент в строке0-Z (-3). А ведущая строка та, у которойнаименьшее положительное отношение свободного члена к соответствующему элементуведущего столбца.

Тогда каноническую формузадачи ЛП можно представить в следующем матричном виде эквивалентномпервоначальному:

Z=CX →max,

AX=B,

X≥0.

где 0 — нулеваяматрица-столбец той же размерности, что и матрица X.

замечание.

Не ограничивая общности,можно полагать, что свободные члены неотрицательны, т.е. b i ≥ 0, где i =¯1,m (иначе ограничительные уравнения можно умножить на (-1)).

Пересчитаем таблицу:

Базисные переменные

Свободные члены

1/4 -1/2 -1/2 3/4

1 1

-1/4 -3/2 -3/2 29/4 0-Z 3/4 11/2 7/2 233/4

Эта таблица является последней, по ней читаем ответ задачи.

Найдено оптимальное базисное решение:

При котором Z max =233/4= 58,25 ден. ед.

План производства:

X1 =3/4=0,75; X2 = 0; X3 = 0; X4 = 3; X5 =0; X6 = 29/4= 7,25

Соответственно по решению, вычисляем:

Z=3*0,75+7*0+2*0+3+7,25= 24

Z= 24

Ответ поставленной задачи: План выпускапродукции (Z) дляполучения максимальной прибыли, при том, что сырьё IIвида было израсходованополностью равен 24 (Z= 24).Из хода решения задачи по условию мы видим, что оценен каждый из видов сырья,используемых для производства продукции.

Блок-схемы основных процедур при решении и программировании задач

Алгоритм программы →Рис. 1. ↓

Рисунок 1 –Алгоритмпрограммы для решения ЗЛП (частный случай)

Программа к поставленной задачи (код программы)

Программа — реализующая решение задачи дляпроизводства всех видов продукции с использованием всех видов сырья. Нормызатрат каждого из видов сырья на единицу продукции данного вида, запасы сырья,а также прибыль с единицы продукции.

Программаопределяет:

План выпускапродукции для получения максимальной прибыли.

1. Описание работы программы, листингпрограммы

1.1 Обоснование выбораязыка

Программа для решенияданной задачи составлена на языке C++.C++ представляет собой системупрограммирования. Как любая подобная система,C++ предназначена для разработки программ и имеет двехарактерные особенности: создаваемые с ее помощью программы могут работать нетолько под управлением Windows, нои в системе MS-DOS.

C++ представляет собой наиболее полныйпакет объектно-ориентированного программирования. Язык прост в применении и базируетсяна C#, что упрощает создание программ,людям, знакомым с данным языком.

1.2 Описание работыпрограммы

Программа составлена дляобщего случая. В первую матрицу вводятся ее члены в обычных дробях. Программапереводит эти дроби в десятичные и составляет каноническую форму. Затемпроисходит процесс формирования первой симплекс таблицы.

Следующим этапомпрограмма начинает составлять итерации, до тех пор пока не будет найденооптимальное решение (в данном случае составлено 2 итерации).

Программа выводит данныев строку F/

1.3 Листингпрограммы

//-------------------------------------------------------------------------------------------

#include <stdio.h>

#include<string.h>

#include<math.h>

#define PRECISION "%6.2f" //формат вывода дробных чисел

#define PRECISION2 "%.2f" // он же только целая часть любой длины

#define MAXDIGIT 1000000 // должно быть оченьбольшое число (больше всех)

typedef enum

{

NEXT_ITERATION, // нужно продолжатьитерации

PLAN_OPTIMAL, // найден оптимальный опорный план

ODR_BREAK, // ОДР разомкнута

ODR_EMPTY, // ОДР пустая

DUAL_DONE /* первый этап (построениеопорного плана) окончен,

переходимк поиску оптим.оп.плана (обычный Симплекс) */

} plan_t;

int cn=0; // длина вектора исходного ур-я

int cnr=0; /* cn, только без членов == 0 (cnr==cn_real)

нужнотолько для вывода сокращенной таблицы */

float *c = NULL; //исходное ур-е

int m=0, n=0; //размеры матрицы условий

float **a = NULL; //матрица условий

float *b = NULL; //столбец свободных членов матрицы условий

int *base = NULL; //базовые переменные

float zb=0; // оценки оптимальности b

float *za = NULL; //оценки оптимальности a

int base_column= -1; // разрешающий столбец

int base_row =-1; // разрешающая строка

bool full_table= true; // вид выводимой таблицы: true==полная, false==сжатая

void FreeMem()

{

delete[]za;

delete[]base;

delete[]b;

for(int i=0; i<m; i++)

delete[]a[i];

delete[]a;

delete[]c;

}

bool ReadInput(char *filename)

{

inti,j;

FILE*f = fopen(filename, «r»);

if(NULL == f)

returnfalse;

// исходное ур-е

fscanf(f, "%i",&cn);

c = new float [cn];

cnr=cn;

for(i=0; i<cn; i++)

{

fscanf(f,"%f", &c[i]);

if (0 == c[i]) cnr--;

}

// матрицаусловий

fscanf(f, "%i %i",&n, &m);

a =new float* [m];

for(i=0; i<m; i++)

a[i]= new float[n];

b =new float [m];

for(j=0; j<m; j++)

{

for(i=0; i<n; i++)

fscanf(f,"%f", &a[j][i]);

fscanf(f,"%f", &b[j]);

}

// базовыепеременные

base = new int [m];

for (j=0; j<m; j++)

{

fscanf(f,"%i", &base[j]);

--base[j];

}

// флаг — полнуюили сжатую таблицу выводить ?

int flag = 1;

fscanf(f,"%i", &flag);

full_table= flag? true: false;

fclose(f);

za =new float[n];

// for(i=0;i<n;i++)za[i]=0;//!!! только для отладки !!!

return true;

}

// Вычисление оценокоптимальности {za==delta_j[] and zb==Z}

voidEvaluationOptimal ()

{

inti,j;

zb=0;

for(i=0; i<n; i++) za[i]=0;

for(j=0; j<m; j++)

{

for(i=0; i<n; i++)

za[i]+= c[base[j]]*a[j][i];

zb+= c[base[j]]*b[j];

}

for(i=0; i<n; i++)

za[i]-= c[i];

}

// Построение опорногоплана (этот этап только в двойственном симплекс-методе)

plan_tBuildPsevdoPlan ()

{

inti,j;

base_column = -1; // разрешающий столбец

base_row = -1; // разрешающая строка

float acc; // временно: аккумулятор — будет хранить min, max, etc.

acc = 0; // min отрицательное значение b

for (j=0; j<m; j++)

if (b[j] < acc)

{

acc= b[j];

base_row= j;

}

if(-1 == base_row)

returnDUAL_DONE;

acc =-MAXDIGIT; // max отношение za к отрицат. эл-там в строке base_row

for(i=0; i<n; i++)

{

floattemp;

if(a[base_row][i] < 0 && (temp = za[i]/a[base_row][i]) > acc)

{

acc= temp;

base_column= i;

}

if(-1 == base_column)

returnODR_EMPTY;

return NEXT_ITERATION;

}

// Проверка опорногоплана на оптимальность

plan_tCheckStrongPlan ()

{

inti,j;

floatza_min = 0;

base_column= -1; // разрешающий столбец

base_row = -1; // разрешающая строка

// выборразрешающего столбца

for (i=0; i<n; i++)

{

if(za[i] >= 0)

continue;

elseif (za[i] < za_min)

{

za_min= za[i];

base_column= i;

}

if(-1 == base_column)

returnPLAN_OPTIMAL;

za_min = MAXDIGIT;

// выборразрешающей строки

for (j=0; j<m; j++)

{

if(a[j][base_column] > 0)

{

floatt = b[j]/a[j][base_column];

if(t < za_min)

{

za_min= t;

base_row= j;

}

if(-1 == base_row)

returnODR_BREAK;

returnNEXT_ITERATION;

}

// Преобразование таблицыпо ф-лам Жордана-Гаусса

voidJGTransformation (int base_row, int base_column)

{

// проверка навсякий случай: чтобы не было деления на нуль

if (0 ==a[base_row][base_column]) return;

base[base_row]= base_column;

inti,j;

float**a2 = new float* [m]; // матрица условий

float *b2 = new float [m]; // столбец свободных членовматрицы условий

memcpy(b2,b,m*sizeof(float));

for(j=0; j<m; j++)

{

a2[j]= new float[n];

memcpy(a2[j],a[j],n*sizeof(float));

}

for(j=0; j<m; j++)

{

for(i=0; i<n; i++)

{

if(i == base_column)

{

a2[j][i]= (float) (j == base_row? 1: 0);

}

else

{

if(j == base_row)

a2[j][i]= a[j][i]/a[base_row][base_column];

else

a2[j][i]= a[j][i] — a[base_row][i]*a[j][base_column]/

a[base_row][base_column];

}

if(j == base_row)

b2[j]= b[j]/a[base_row][base_column];

else

b2[j]= b[j] — b[base_row]*a[j][base_column]/

a[base_row][base_column];

}

memcpy(b,b2,m*sizeof(float));

delete[]b2;

for(j=0; j<m; j++)

{

memcpy(a[j],a2[j],n*sizeof(float));

delete[]a2[j];

}

delete[]a2;

}

// проверка: входит линомер столбца в число базисных переменных

bool InBase(int num)

{

for(int j=0; j<m; j++)

if(num == base[j])

returntrue;

returnfalse;

}

// вывод линиисимволов

void Rule(char c, int amount = full_table? 5+(n+2)*8: 5+(cnr+1)*8)

{

for(int i=0; i<amount; i++)

printf("%c",c);

printf("\n");

}

// вывод Симплекс-таблицы

void ShowTable()

{

inti,j;

staticint iteration = 0;

printf("[%i]\n",iteration++);

if(full_table)

// полная таблица

{

Rule('=');

printf(«Баз.| | |»);

for(i=0; i<cn; i++)

printf(PRECISION" |", c[i]);

printf("\nпер.|Ci | Bi |");

Rule('-',n*8);

printf("| | |");

for(i=0; i<cn; i++)

printf("x%i |", i+1);

printf("\n");

Rule('=');

for(j=0; j<m; j++)

{

printf("x%i |" PRECISION " |" PRECISION " |",

base[j]+1,c[base[j]], b[j]);

for(i=0; i<n; i++)

printf(PRECISION"%c|", a[j][i],

base_column== i && base_row == j ?'*':' ');

printf("\n");

}

Rule('=');

printf("Z | — |" PRECISION " |", zb);

for(i=0; i<n; i++)

printf(PRECISION" |", za[i]);

printf("\n");

Rule('-');

}

else

//сжатая таблица

{

Rule('=');

printf(«БvС>|»);

for(i=0; i<cn; i++)

{

if(!InBase(i))

printf("x%i |", i+1);

}

printf("Bi |\n");

Rule('=');

for(j=0; j<m; j++)

{

printf("x%i |", base[j]+1);

for(i=0; i<n; i++)

{

if(!InBase(i))

printf(PRECISION"%c|", a[j][i],

base_column== i && base_row == j ?'*':' ');

}

printf(PRECISION"|\n", b[j]);

}

Rule('=');

printf("Z |");

for(i=0; i<n; i++)

{

if(!InBase(i))

printf(PRECISION" |", za[i]);

}

printf(PRECISION" |\n", zb);

Rule('-');

}

if(base_column > -1 && base_row > -1)

printf(«Разрешающий столбец:%2i\nРазрешающая строка: %2i\n\nX=(»,

base_column+1,base_row+1);

else

printf("\nX=(");

for(i=0; i<n; i++)

{

intbasen = -1;

for(j=0; j<m; j++)

if(base[j] == i) {basen = j; break;}

printf(PRECISION2"%c ", -1==basen?0:b[basen], i!=n-1?',':')');

}

printf("\nZ="PRECISION2 "\n\n\n", zb);

}

int main (intargc, char *argv[])

{

if(argc < 2)

{

printf(«Missingargument\n»);

return-1;

}

if(!ReadInput(argv[1]))

{

printf(«Erroropen file %s.\n», argv[1]);

return -1;

}

printf("*** ДВОЙСТВЕННЫЙСИМПЛЕКС-МЕТОД ***\n\n");

plan_t plan;

booldual_done = false;

for(int k=0; k<2*m+1; k++)

{

if(k) JGTransformation(base_row, base_column);

EvaluationOptimal();

if(dual_done)

{

plan= CheckStrongPlan();

}

else

{

plan= BuildPsevdoPlan(); // only in dual-simplex

if(DUAL_DONE == plan)

{

dual_done= true;

plan= CheckStrongPlan();

}

ShowTable();

if(NEXT_ITERATION != plan)

{

char*s;

switch(plan)

{

casePLAN_OPTIMAL: s=«Опорный план оптимальный»; break;

case ODR_BREAK:s=«Область допустимых решенийразомкнутая»; break;

case ODR_EMPTY:s=«Область допустимых решенийпустая»; break;

}

printf("\n%s.\n",s);

break;

}

FreeMem();

return 0;

}

//-----------------------------------------------------------------------------------------

Результат работыпрограммы

Работу программы мы можемпроанализировать по результату. Здесь мы видим первоначальную матрицу, котораяпредставлена в виде симплекс таблицы и результат преобразования таблицы.Результат преобразования таблицы представлен в виде симплекс таблицы, подобнойпервоначальной.

Проанализировав данныеполученные с помощью программы и сравнив их с результатами вычислений можносделать вывод, что полученные результаты равны между собою, а это значит чтопрограмма работает верно.

3.4. Анализ результатарешения поставленной задачи

1. Задачи анализа,источники информации

Необходимым условием выполнения планов по производству продукции, снижению ее себестоимости, росту прибыли, рентабельности является полное и своевременное обеспечение предприятия сырьем и материалами необходимого ассортимента и качества. Рост потребности предприятия в материальных ресурсах может быть удовлетворен экстенсивным путем (приобретением или изготовлением большего количества материалов и энергии) или интенсивным (более экономным использованием имеющихся запасов в процессе производства продукции).

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

Задачи анализа обеспеченности и использования материальных ресурсов:

а) оценка реальности планов материально-технического снабжения, степени их выполнения и влияния на объем производства продукции, ее себестоимость и другие показатели;

б) оценка уровня эффективности использования материальных ресурсов;

в) выявление внутрипроизводственных резервов экономии материальных ресурсов и разработка конкретных мероприятий по их использованию.

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

2. Анализ обеспеченности предприятия материальными ресурсами

При анализе обеспеченности предприятия материальными ресурсами в первую очередь проверяют качество плана материально-технического снабжения. Проверку реальности плана начинают с изучения норм и нормативов, которые положены в основу расчета потребности предприятия в материальных ресурсах. Затем проверяется соответствие плана снабжения потребностям производства продукции и образования необходимых запасов исходя из прогрессивных норм расхода материалов. Важным условием бесперебойной работы предприятия является полная обеспеченность

потребности в материальных ресурсах источниками покрытия. Очи могут быть внешними и внутренними. К внешним источникам относятся материальные ресурсы, поступающие от поставщиков в соответствии с заключенными договорами.

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

Позаданной задачи мы видим, что:

Вид сырья Нормы затрат сырья (кг) на единицу продукции

III

Цена единицы продукции (руб.) 3 7 2

1. Первое,что я сделал, это определил план выпуска продукции для получения максимальнойприбыли, с учетом того что бы сырьё IIвида было израсходовано полностью.

Z-0 = 3X1 + 7X2 + 2X3

+ 2

≤ 19

+ 1

= 8 1

+ 2

≤ 24

X1, X2, X3 ≥ 0.

4X1+2X2+X4 ≤ 19

X2 + X3 +X5 = 8

X1+ 2X2+X6 ≤24

2. Второе, оценил каждый из видов сырья, используемых дляпроизводства продукции.

Z-0 = 3X1 + 7X2 + 2X3 → max

Ввел дополнительныепеременные X4, X5, X6.

Z-0= 3

+ 7

+ 2

à(max)

Ограничения:

+ 2

= 19

+ 1

= 8 1

+ 2

= 24

3. Построил математическую модель задачи;

4X1+2X2+X4 = 19

X2 + X3 +X5 = 8

X1+2X2 +X6 =24

4.Выбрал метод решения задачи и привел задачу к каноническому виду;

Xi≥0; 0-Z= -3X1- -7X2--2X3

5.Решил задачу путём сведения к задаче линейного программирования;

Базисныепеременные

Свободныечлены

4 2 1 19

1 1 8

1 2 1 24 0-Z -3 -7 -2

Пересчитал таблицу:

Базисные переменные

Свободные члены

-2 -2 1 3

1 1 1 8

1 -2 -2 1 8 0-Z -3 7 5 56

Пересчитал таблицу:

Базисные переменные

Свободные члены

1/4 -1/2 -1/2 3/4

1 1 8

-1/4 -3/2 -3/2 29/4 0-Z 3/4 11/2 7/2 233/4

Нашел оптимальное базисное решение

6. Затем построил блок схему к задачи с написанием программы ивыводом на печать программного кода.

7. Анализом моего результата решения состоит из правилоптимального решения задачи из поставленного условия.

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

Просматривается последняя строка (индексная) таблицы и средикоэффициентов этой строки (исключая столбец свободных членов ) выбираетсянаименьшее отрицательное число при отыскании max, либо наибольшееположительное при задачи на min. Если такового нет, то исходное базисноерешение является оптимальным и данная таблица является последней; просматриваетсястолбец таблицы, отвечающий выбранному отрицательному (положительному)коэффициенту в последней строке — ключевой столбец, и в этом столбце выбираютсяположительные коэффициенты.

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

Этот коэффициент называется разрешающим, а строка в которойон находится ключевой; в дальнейшем базисная переменная, отвечающая строкеразрешающего элемента, должна быть переведена в разряд свободных, а свободнаяпеременная, отвечающая столбцу разрешающего элемента, вводится в числобазисных. Строится новая таблица, содержащая новые названия базисныхпеременных: разделяем каждый элемент ключевой строки (исключая столбецсвободных членов) на разрешающий элемент и полученные значения записываем встроку с измененной базисной переменной новой симплекс таблицы… Строкаразрешающего элемента делится на этот элемент и полученная строка записываетсяв новую таблицу на то же место в новой таблице все элементы ключевого столбца =0, кроме разрезающего, он всегда равен 1. Столбец, у которого в ключевой строкеимеется 0, в новой таблице будет таким же строка, у которой в ключевом столбцеимеется 0, в новой таблице будет такой же в остальные клетки новой таблицызаписывается результат преобразования элементов старой таблицы: В результатеполучаем новую симплекс-таблицу, отвечающую новому базисному решению. Теперьследует просмотреть строку целевой функции (индексную), если в ней нетотрицательных значений (в задачи на нахождение максимального значения), либоположительных (в задачи на нахождение минимального значения) кроме стоящего наместе (свободного столбца), то значит, что оптимальное решение получено. Впротивном случае, переходим к новой симплекс таблице по выше описанномуалгоритму.

4. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ ИСПОЛЬЗОВАНИЮ

Цельюкурсового проекта было решение задач линейного программированиясимплекс-методом, составление алгоритма, составление программы по алгоритму ивывод результата на экран.

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

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

Симплекс-методявляется вычислительной процедурой представленной в алгебраической форме. Оннепосредственно применяется к общей задаче линейного программирования встандартной форме.

В данномпроекте был составлен оптимальный план выпуска продукции каждого вида,обеспечивающий максимальную прибыль.

В выводе своегопроектирования хочу подвести итог в целом “Решению матричных игр в смешанныхстратегиях” .

Классификацию игр можнопроводить: по количеству игроков, количеству стратегий, характерувзаимодействия игроков, характеру выигрыша, количеству ходов, состояниюинформации и т.д.

В зависимости от количестваигроков различают игры двух и n игроков. Первые из них наиболее изучены. Игрытрёх и более игроков менее исследованы из-за возникающих принципиальныхтрудностей и технических возможностей получения решения. Чем больше игроков — тем больше проблем.

По количеству стратегийигры делятся на конечные и бесконечные. Если в игре все игроки имеют конечноечисло возможных стратегий, то она называется конечной.Если же хотя бы один из игроков имеет бесконечное количество возможныхстратегий игра называется бесконечной.

По характерувзаимодействия игры делятся на:

1) бескоалиционные: игроки не имеют прававступать в соглашения, образовывать коалиции;

2) коалиционные (кооперативные) – могут вступать вкоалиции.

В кооперативных играхкоалиции наперёд определены.

По характеру выигрышейигры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, аперераспределяется между игроками; сумма выигрышей всех игроков равна нулю) иигры с ненулевой суммой.

По виду функций выигрышаигры делятся на: матричные, биматричные, непрерывные, выпуклые, сепарабельные,типа дуэлей и др.

Матричная игра – это конечная игра двух игроков снулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строкаматрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеруприменяемой стратегии игрока 2; на пересечении строки и столбца матрицынаходится выигрыш игрока 1, соответствующий применяемым стратегиям).

Для матричных игрдоказано, что любая из них имеет решение и оно может быть легко найдено путём сведенияигры к задаче линейного программирования.

Биматричная игра – это конечная игра двух игроков сненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельнодля соответствующего игрока (в каждой матрице строка соответствует стратегииигрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца впервой матрице находится выигрыш игрока 1, во второй матрице – выигрыш игрока2.)

Для биматричных игр такжеразработана теория оптимального поведения игроков, однако решать такие игрысложнее, чем обычные матричные.

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

Если функция выигрышейявляется выпуклой, то такая игра называется выпуклой.Для них разработаны приемлемые методы решения, состоящие в отыскании чистойоптимальной стратегии (определённого числа) для одного игрока и вероятностейприменения чистых оптимальных стратегий другого игрока. Такая задача решаетсясравнительно легко.

Заключение курсовогопроектирования по теме задания ”Решение матричной игры в смешанных стратегиях”

Чтобы описать игру,необходимо сначала выявить ее участников. Это условие легко выполнимо, когдаречь идет об обычных играх типа шахмат, канасты и т.п. Иначе обстоит дело с“рыночными играми”. Здесь не всегда просто распознать всех игроков, т.е.действующих или потенциальных конкурентов. Практика показывает, что не обязательноидентифицировать всех игроков, надо обнаружить наиболее важных. Игрыохватывают, как правило, несколько периодов, в течение которых игрокипредпринимают последовательные или одновременные действия. Эти действияобозначаются термином “ход”. Действия могут быть связаны с ценами, объемамипродаж, затратами на научные исследования и разработки и т.д. Периоды, втечение которых игроки делают свои ходы, называются этапами игры. Выбранные накаждом этапе ходы в конечном счете определяют “платежи” (выигрыш или убыток)каждого игрока, которые могут выражаться в материальных ценностях или деньгах(преимущественно дисконтированная прибыль). Еще одним основным понятием даннойтеории является стратегия игрока. Под ней понимаются возможные действия,позволяющие игроку на каждом этапе игры выбирать из определенного количестваальтернативных вариантов такой ход, который представляется ему “лучшим ответом”на действия других игроков. Относительно концепции стратегии следует заметить,что игрок определяет свои действия не только для этапов, которых фактическидостигла конкретная игра, но и для всех ситуаций, включая и те, которые могут ине возникнуть в ходе данной игры.

Важна и формапредоставления игры. Обычно выделяют нормальную, или матричную, форму и развернутую,заданную в виде дерева. Чтобы установить первую связь со сферой управления,игру можно описать следующим образом. Два предприятия, производящие однороднуюпродукцию, стоят перед выбором. В одном случае они могут закрепиться на рынкеблагодаря установлению высокой цены, которая обеспечит им среднюю картельнуюприбыль ПK. При вступлении в жесткую конкурентную борьбу оба получают прибыльПW. Если один из конкурентов устанавливает высокую цену, а второй – низкую, топоследний реализует монопольную прибыль ПM, другой же несет убытки ПG. Подобнаяситуация может, например, возникнуть когда обе фирмы должны объявить свою цену,которая впоследствии не может быть пересмотрена. При отсутствии жестких условийобоим предприятиям выгодно назначить низкую цену. Стратегия “низкой цены”является доминирующей для любой фирмы: вне зависимости от того, какую ценувыбирает конкурирующая фирма, самой всегда предпочтительней устанавливатьнизкую цену. Но в таком случае перед фирмами возникает дилемма, так как прибыльПK (которая для обоих игроков выше, чем прибыль ПW) не достигается. Стратегическаякомбинация “низкие цены/низкие цены” с соответствующими платежами представляетсобой равновесие Нэша, при котором ни одному из игроков невыгодно сепаратноотходить от выбранной стратегии. Подобная концепция равновесия являетсяпринципиальной при разрешении стратегических ситуаций, но при определенныхобстоятельствах она все же требует усовершенствования. Что касается указаннойвыше дилеммы, то ее разрешение зависит, в частности, от оригинальности ходовигроков.

Список основныхисточников опорной литературы

1. Б.Банди, Основы линейногопрограммирования. М: Высшая мат.,1989г.

2. Б.Т Кузнецов Математические методыи модели исследования операций. М: Юнити,2005г.

3. В.Н. Ашихмин и др. Введение вматематическое моделирование, М: Логос, 2005г.

4. Т.Л. Партыко, И.И. Попов.Математические методы, М: Форум, 2003г.

5. В.В. Фаронов. Программированиена языке С++, СПб.: Питер, 2006г.

еще рефераты

Еще работы по информатике, программированию

Реферат по информатике, программированию

Линейное программирование симплекс-методом Данцига

31 Августа 2013

Реферат по информатике, программированию