Реализация симплекс-метода в случае положительных свободных членов

1. Введение

 

 В данной курсовой работе я хочу представить  метод решения «Реализация симплекс-метода в случае положительных свободных  членов».

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

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

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

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

 Действительно, путь необходимо исследовать на экстремум линейную функцию

 Z = С₁х₁+С₂х₂+... +С_Nx_N

 при линейных ограничениях

 a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

 a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

 . . . . . . . . . . . . . . .

 a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

 

 Так как Z - линейная функция, то Z = С_j, (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

 

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

 

   Теория  игр – это совокупность математических методов анализа и оценки конфликтных ситуаций.

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

   Моделями  теории игр можно описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой.

   Все такие модели в теории игр принято  называть играми.

   Игры  можно классифицировать по различным  признакам: стратегические и чисто  случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.

   Рассмотрим  простейшую модель – игру, в которой участвуют два игрока, множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц). Такую игру (Г) называют матричной. Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию  , а 2-й – стратегию  ). Пару (x,y) называют ситуацией в игре Г.

   Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы  , где a_ij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии называют чистыми).

   Матрица А называется матрицей игры или платежной матрицей.

   Пусть матрица игры  . Цель каждого игрока – получить как можно больший выигрыш. Но 1-му игроку нет смысла выбирать стратегию i=1 в надежде выиграть 5 ед., так как 2-й игрок, действуя разумно, не станет выбирать стратегию j=2, чтобы не проиграть максимальную сумму 5 ед. Игрокам удобнее выбрать «осторожные» стратегии.

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

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

   Схема:

   

   Например, 

   Соответствующие стратегии: i₀=1 (максиминная), j₀=1,2 (минимаксная).

   Справедливо неравенство:  .

   В игре Г естественно считать оптимальной такую ситуацию (i,j), от которой ни одному из игроков невыгодно отклоняться.

   Ситуация (i^*,j^*) называется ситуацией равновесия, или седловой точкой, если для любых  ,   выполняется неравенство  . Соответствующие стратегии i^*, j^*называются оптимальными чистыми стратегиями 1-го и 2-го игроков, а число   называется ценой игры. Элемент   является одновременно минимумом в своей строке и максимумом в своем столбце.

   Ситуация  равновесия существует тогда и только тогда, когда   (это значение и является ценой игры v).

   Например, 

   (2,3)-ситуация  равновесия, v=4 – цена игры, i^*=2, j^*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

   Наряду  с чистыми стратегиями игроков  рассматривают также смешанные стратегии.

   Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x₁, x₂, …, x_m),  ,  , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m.

   Аналогично  определяется смешанная стратегия  для 2-го игрока: y=(y₁, y₂, …, y_n),  ,  .

   Множества всех смешанных стратегий 1-го и 2-го игроков будем обозначать соответственно S_m и S_n.

   Чистые  стратегии можно рассматривать  как частный случай смешанных  стратегий. Например, чистую стратегию j=2 можно рассматривать как смешанную y=(0,1,0,…,0), чистую стратегиюi=1 – как смешанную x=(1,0,…,0).

   Пару  смешанных стратегий (x,y) называют ситуацией в смешанных стратегиях.

   Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x₁, x₂, …, x_m) и y=(y₁, y₂, …, y_n):  .

   Если  для некоторых   и   и для всех   и   выполняется неравенство  , то x^*, y^* называются оптимальными смешанными стратегиями игроков, число  называется ценой игры, пара (x^*, y^*) – стратегической седловой точкой, а тройка x^*, y^*, v – решением игры.

   Основная  теорема теории матричных  игр, или теорема о минимаксе. Если  – матрица игры Г и для всех   и    , то величины   и   существуют и равны между собой (эта величина и является ценой игры v).

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

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

 Действительно, путь необходимо исследовать на экстремум  линейную функцию

 Z = С₁х₁+С₂х₂+... +С_Nx_N

 при линейных ограничениях

 a₁₁x₁ + a₂₂x₂ + ... + a_1NХ_N = b₁

 a₂₁x₁ + a₂₂x₂ + ... + a_2NХ_N = b₂

 . . . . . . . . . . . . . . .

 a_М1x₁ + a_М2x₂ + ... + a_МNХ_N = b_М

 

 Так как Z - линейная функция, то Z = С_j, (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

Решение задач линейного  программирования средствами табличного процессора Excel.

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

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