Системный анализ
Понятие линейного математического программирования. Модели линейного программирования с двумя переменными. Системы линейных уравнений. Принцип максимина в антагонистических играх, седловая точка. Чистые и смешанные стратегии. Теоремы матричных игр.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 24.06.2014 |
| Размер файла | 459,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
В технической и экономической деятельности мы постоянно сталкиваемся с одним и тем же кругом задач: как по известной ситуации и множеству возможных альтернативных вариантов дальнейшего поведения выбрать наилучший вариант. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении.
Рассмотрим постановку такой задачи.
Пусть решение принимаемое субъектом описывается набором чисел (например, xi -это количества выпускаемой продукции i-ого вида). Достоинства решения определяются значением целевой функции , то есть функции, значения которой зависят от выбранных нами параметров производства. При этом наилучшим считается то решение, при котором целевая функция принимает max значение ( если она описывает доход ), или min значение (если она описывает издержки ). Требуется найти те значения , при которых , или . Множество на котором ищется наше решение называется областью допустимых решений.
Возможны следующие два принципиально разных случая.
1. Если для решения доступны все точки пространства, то экстремум отыскивается во всем пространстве и называется безусловным. Если к тому же целевая функция непрерывно дифференцируема, то экстремум находится из условия ( см. необходимые условия экстремума функции нескольких переменных).
2. Если не все точки пространства доступны ( что, например, может быть связано с ограниченностью ресурсов ), то в этом случае имеем ограничения вида , или . В этом случае экстремум ищется только среди допустимых точек и называется условным.
В данном методическом пособии рассматривается решение задач в которых экстремум ищется на границе выпуклой области заданной системой неравенств . Решение таких задач изучается в разделе математики называемом «математическое программирование». К задачам математического программирования относятся задачи следующих типов: линейные, нелинейные, целочисленные, динамические, одно - и многокритериальные и т.д. Наиболее развитый раздел этих задач - Задачи линейного программирования (ЗЛП ). Эти задачи впервые были исследованы в работах российского ученого Л.В. Канторовича в 1939 г. Затем они получили развитие в США, где в 1949 г. Данциг разработал Симплексный метод, наиболее широко используемый при решении ЗЛП.
Линейное программирование (ЛП) - это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны.
ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках.
линейный программирование игра матричный
1. Модели линейного программирования с двумя переменными
Пример 1.1.Компания Mikks производит краску для внутренних и наружных работ из сырья двух типов С1 и С2. Следующая таблица представляет основные данные для задачи.
|
Расход сырья (в тоннах) на тонну краски |
Максимально возможный ежедневный расход сырья |
|||
|
Для наружных работ |
Для внутренних работ |
|||
|
Сырье С1 |
6 |
4 |
24 |
|
|
Сырье С2 |
1 |
2 |
6 |
|
|
Доход (в тыс. долл.) на тонну краски |
5 |
4 |
Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т (из-за отсутствия надлежащего спроса), а также поставил условие, чтобы ежедневное производство краски для внутренних работ не превышало более, чем на 1 т аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное(наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.
Задача (модель) линейного программирования (ЗЛП), как и любая задача исследования операций, включает три основных элемента.
1. Переменные, которые следует определить.
2. Целевая функция, подлежащая оптимизации.
3. Ограничения, которым должны удовлетворять переменные.
Определение переменных - первый шаг в создании модели. В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:
- ежедневный объем производства краски для наружных работ;
- ежедневный объем производства краски для внутренних работ.
Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок.
При построении модели нужно учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию.
Поскольку ежедневный расход сырья С1 и С2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.
Существует еще два ограничения по спросу на готовую продукцию:
1. Максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т, т.е.
2. Ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну (разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны)
Еще одно неявное ограничение состоит в том, что переменные и должны быть неотрицательными.
Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение и будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения и в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно (тысяч долларов). Итак, задача сформулирована. Теперь встает вопрос о нахождении оптимального допустимого решения, доставляющего максимум целевой функции. После некоторых раздумий приходим к выводу, что задача имеет много (фактически, бесконечно много) допустимых решений. По этой причине невозможна подстановка значений переменных для поиска оптимума, т.е. нельзя применить простой перебор всех допустимых решений. Следовательно, необходима эффективная процедура отбора допустимых решений для поиска оптимального.
2 .Системы линейных уравнений
Системой m линейных уравнений с n неизвестными называется система вида
где aij и bi (i=1,…,m; b=1,…,n) - некоторые известные числа, а x1,…,xn - неизвестные. В обозначении коэффициентов aij первый индекс i обозначает номер уравнения, а второй j - номер неизвестного, при котором стоит этот коэффициент.
Коэффициенты при неизвестных будем записывать в виде матрицы
,
которую назовём матрицей системы.
Числа, стоящие в правых частях уравнений, b1,…,bm называются свободными членами.
Совокупность n чисел c1,…,cn называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чиселc1,…,cn вместо соответствующих неизвестных x1,…,xn. Наша задача будет заключаться в нахождении решений системы. При этом могут возникнуть три ситуации:
1. Система может иметь единственное решение.
2. Система может иметь бесконечное множество решений. Например,
.
Решением этой системы является любая пара чисел, отличающихся знаком.
3. И третий случай, когда система вообще не имеет решения. Например,
,
если бы решение существовало, то x1 + x2 равнялось бы одновременно нулю и единице.
Система линейных уравнений, имеющая хотя бы одно решение, называется совместной. В противном случае, т.е. если система не имеет решений, то она называется несовместной.
Приведем определение общего частного базисного решения:
Общим решением разрешенной системы уравнений называется совокупность выражений разрешенных неизвестных через свободные члены и свободные неизвестные:
Частным решением системы уравнений называется решение, получающиеся из общего при конкретных значениях свободных переменных и неизвестных.
Базисным решением называется частное решение, получающееся из общего при нулевых значениях свободных переменных.
§ Базисное решение (вектор) называется вырожденным, если число его координат, отличных от нуля, меньше числа разрешенных неизвестных.
§ Базисное решение называется невырожденным, если число его координат, отличных от нуля, равно числу разрешенных неизвестных системы, входящих в полный набор.
Теорема (1)
Разрешенная система уравнений всегда совместна (потому что она имеет хотя бы одно решение);причем если система не имеет свободных неизвестных, (то есть в системе уравнений все разрешенные входят в базис) то она определена (имеет единственное решение); если же имеется хотя бы одна свободная переменная, то система не определена (имеет бесконечное множество решений).
Пример 1. Найти общее, базисное и какое-либо частное решение системы уравнений:
Решение:
1. Проверяем является ли система разрешенной?
Система является разрешенной (т.к. каждое из уравнений содержит в себе разрешенную неизвестную)
2. Включаем в набор разрешенные неизвестные -- по одному из каждого уравнения.
В нашем случае мы можем включить в набор разрешенных неизвестных из первого уравнения -- и , а из второго уравнения только . То есть набор может состоять из () или ().
3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор. Допустим мы включили в набор неизвестные и , тогда общее решение будет выглядеть так:
4. Находим частное решение. Для этого приравниваем свободные переменные, которые мы не включили в набор приравнять к произвольным числам.
Пусть , , , тогда из общего решения находим:
Ответ: частное решение (один из вариантов)
5. Находим базисное решение. Для этого приравниваем свободные переменные, которые мы не включили в набор к нулю.
, то из общего решения получаем , и базисное решение:
Постановка ЗЛП
Линейной функцией переменных x1, x2,…,xn называется функция вида F = a1x1 + a2x2 + … + anxn + a0 , где все ai - некоторые const. В задачах линейного программирования все входящие в них функции - целевая функция F(), все ограничения и т.д. являются линейными функциями переменных x1, x2, … ,xn.
Как правило ЗЛП может быть записана в одной из следующих двух форм.
1. Стандартная (основная ) форма ЗЛП.
Найти вектор-план , удовлетворяющий системе ограничений
( 1 )
и доставляющий max целевой функции = c1 x1 + c2 x2 + …+ cn xn max
2. Каноническая форма ЗЛП.
Найти вектор-план , удовлетворяющий системе ограничений
( 2 )
и доставляющий max целевой функции = c1 x1 + c2 x2 + …+ cn xn max
Замечание Каждая из форм может быть легко сведена к другой.
Так ограничение можно записать системой
откуда легко получаем
В результате от ЗЛП в канонической форме перешли к ЗЛП в стандартной форме.
Если ЗЛП записана в стандартной форме, например, , то введем дополнительную переменную , после чего получим запись ЗЛП в канонической форме.
3. Графическое решение ЗЛП
ЗЛП записанная в стандартной форме и содержащая только 2 переменные может быть решена графическим методом. Поскольку графический метод наиболее наглядный и служит основой для осмысления всех других методов, то рассмотрим его подробно. Пусть дана следующая ЗЛП.
Найти вектор - план , удовлетворяющий системе ограничений
( 3 )
и доставляющий максимум целевой функции .
Очевидно, уравнения на плоскости OX1X2 определяют прямые, каждая из которых разбивает плоскость на 2 полуплоскости. Неравенства определяют каждое одну из этих двух полуплоскостей. Множество D допустимых решений представляет собой область, полученную от пересечения всех указанных полуплоскостей, удовлетворяющих вышеприведенной системе неравенств. Можно показать, что область D представляет собой выпуклый многоугольник. Выпуклым называется многоугольник, у которого отрезок прямой соединяющий любые две точки границы этого многоугольника целиком принадлежит этому многоугольнику. Так на рис.1 изображены
Выпуклый многоугольник Не выпуклый многоугольник
Для решения задачи надо найти такую точку этого многоугольника D, в которой целевая функция принимала бы максимальное значение.
Для определения этой точки проведем через многоугольник решений D линию уровня функции , то есть такую линию, во всех точках которой целевая функция принимает постоянное значение F() = c1 x1 + c2 x2 = const. Увеличивая значение этой const получим семейство параллельных прямых, на каждой из которых целевая функция принимает все большие и большие значения. Очевидно, что из всех линий уровня этого семейства следует взять ту, которая проходит через самую крайнюю точку А области D, так как именно на ней целевая функция принимает самое большое значение. Действительно, поскольку эта линия проходит через крайнюю точку области D, то при дальнейшем увеличении значения целевой функции линия уровня выйдет за пределы области D и значения переменных x1 и x2 уже не будут принадлежать области допустимых решений. Поэтому координаты крайней точки А и являются оптимальным планом решаемой ЗЛП.
Для проведения линии уровня и определения направления в котором ее следует перемещать используется вектор «градиент функции F» с координатами
- grad F = c1, c2 , обладающий двумя важными свойствами:
- grad F перпендикулярен линии уровня F
- grad F всегда направлен в сторону увеличения значения функции F.
При отыскании минимума функции линию уровня перемещают в направлении -grad F = -с1, -с2.
Выпуклые множества и многогранники
Перейдем теперь к более строгому изложению основ теории линейного программирования, хотя будут изложены лишь наиболее простые результаты.
Рассмотрим n - мерное евклидово пространство и пусть ? точка в этом пространстве.
Рассмотрим две точки и , принадлежащие .Множество точек , которые могут быть представлены в виде
(в координатах это записывается так:
,
отрезком, соединяющим точки и . Сами точки и называются концами отрезка. В случаях n =2 и n =3 это ? отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12).Заметим, что при =0 выполняется: , а при =1 , т.е. при =0 и =1 получаются концы отрезка.
,
где все и называется выпуклой комбинацией точек .
Пусть есть некоторая область в пространстве
Определение. Множество (область) называется выпуклым, если из того, что и следует, что для ? ?[0,1]. Другими словами, G ? выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.
На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.
Теорема 1. Пусть G ? выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.
Теорема 2. Допустимая область задачи линейного программирования является выпуклым множеством.
Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).
Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).
Применение математических методов в экономике приводит к необходимости отыскания неотрицательных решений системы линейных уравнений, т.е. таких, в которых
При этом особое значение имеют неотрицательные базисные решения, которые принято называть опорными решениями.
Таким образом, у опорных решений все базисные неизвестные должны иметь только неотрицательные значения.
Пример № 1 графического решение ЗЛП для Задачи использования сырья
Пусть для изготовления двух видов продукции Р1 и Р2 требуется три вида сырья S1, S2, S3. Параметры производства даны в таблице.
Выбрать производственный план, обеспечивающий максимальную прибыль.
|
Вид сырья |
Запасы сырья (кол. единиц) |
Количество единиц сырья идущих на единицу продукции |
||
|
Продукция Р1 |
Продукция Р2 |
|||
|
Сырье S1 |
20 |
2 |
5 |
|
|
Сырье S2 |
40 |
8 |
5 |
|
|
Сырье S3 |
30 |
5 |
6 |
|
|
Прибыль от продажи единицы продукции (тыс. руб.) |
50 |
40 |
Решение
Составим математическую модель ЗЛП.
Обозначим через x1 - количество выпускаемой продукции Р1 , а через x2 - количество выпускаемой продукции Р2 . Система ограничений, означающая, что количество израсходованного сырья не превышает имеющихся запасов, будет иметь вид
Ограничения очевидны.
Прибыль от реализации всей выпущенной продукции описывается линейной функцией двух переменных - целевой функцией . Стремление получить максимальную прибыль приводит к необходимости выбрать такие значения x1 и x2 при которых целевая функция принимает максимально возможное значение
Итак, получили ЗЛП, записанную в стандартной форме :
Найти вектор - план , удовлетворяющий системе ограничений
( 4 )
и доставляющий максимум целевой функции .
Поскольку неизвестных в задаче две ( x1 и x2 ), то возможно ее графическое решение. Решение начнем с построения области допустимых решений D. Найдем границы области D, для чего в системе ограничений ЗЛП заменим знаки неравенств на знаки равенств и построим соответствующие прямые по двум точкам, откладываемым на осях координат. Имеем
Построив эти границы отметим стрелками полуплоскости, удовлетворяющие неравенствам, для чего подставим точку ( 0, 0 ) в каждое неравенство. Если эта точка удовлетворяет неравенству, то стрелки направлены в сторону этой точки, если нет, то в противоположную сторону. Учитывая, что неравенства
x1 0, x2 0 определяют на плоскости первую четверть заштрихуем общую часть всех полуплоскостей и получим искомую область допустимых решений D (пятиугольник OBАCE) как это показано на рис. 2.
Рис. 2
Теперь строим вектор grad F = , причем, поскольку нас интересует только направление этого вектора, то на рисунке отметим вектор в 10 раз меньший, т.е. grad F = . Затем через область D произвольно проведем линию уровня F = c1 x1 + c2 x2 = const , которая в нашем случае будет записа-на в виде 50 x1 + 40 x2 = const. По свойству вектора grad F линия уровня
F = const расположена перпендикулярно этому вектору. Потом линию уровня перемещаем параллельно самой себе в направлении вектора grad F (так как ищем max F ), до совмещения с последней точкой области D. Как видно из чертежа такой точкой будет точка А, которая и является решением исходной ЗЛП (рис. 3).
Рис.3
Найдем координаты точки А. Так как точка А образована пересечением прямых отмеченных на чертеже номерами 2 и 3, то решим совместно систему уравнений 2 и 3. Имеем
Решением будет
После этого находим значение целевой функции при этих x1, x2
F( ) = 50 + 40 =
Ответ: Для получения максимального дохода рекомендуется выпускать продукцию первого вида в количестве 4 ед., а продукцию второго вида в количестве 1,8 ед. в день. При этом максимально возможный при данных параметрах производства доход составит 265,2 тыс. денежн. ед.
Замечания. Анализируя решение приведенной задачи можно сделать следующие заключения:
- Область D является выпуклым многоугольником, координаты точек которого являются решением исходной системы ограничений ЗЛП. Если система несовместна, то множество точек области D пустое и в этом случае ЗЛП решения не имеет.
- ЗЛП может не иметь решения и в случае если область D открытая. В этом случае линия уровня перемещаясь в направлении grad F уходит на бесконечность и значение целевой функции на ней неограниченно возрастает.
- Экстремальное значение целевой функции (оптимальное решение ) всегда достигается в угловой точке (вершине) многоугольника допустимых решений D и никогда во внутренней точке. Если экстремальное решение достигается в двух соседних вершинах, то оно будет таким же и во всех точках отрезка (границы) соединяющего эти вершины.
4. Транспортная задача
Задача о размещении (транспортная задача) - это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов.
Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.
Стандартная транспортная задача - это задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.
Исходные параметры модели ТЗ:
1. n - количество пунктов отправления, m - количество пунктов назначения.
2. - запас продукции в пункте отправления () [ед. тов.].
3. - спрос на продукцию в пункте назначения () [ед. тов.].
4. - тариф (стоимость) перевозки единицы продукции из пункта отправления в пункт назначения [руб./ед. тов.].
Искомые параметры модели ТЗ
1. - количество продукции, перевозимой из пункта отправления в пункт назначения [ед. тов.].
2. - транспортные расходы на перевозку всей продукции [руб.].
Этапы построения модели
1. Определение переменных.
2. Проверка сбалансированности задачи.
3. Построение сбалансированной транспортной матрицы.
4. Задание ЦФ.
5. Задание ограничений.
Транспортная модель
Целевая функция представляет собой транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели ТЗ является транспортная матрица.
Таблица Общий вид транспортной матрицы
|
Пункты отправления, |
Пункты потребления, |
Запасы,[ед. прод.] |
||||
|
… |
||||||
|
… |
||||||
|
… |
||||||
|
… |
… |
… |
… |
… |
… |
|
|
… |
||||||
|
Потребность[ед. прод.] |
… |
|||||
|
Сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления, то есть. |
Транспортная задача называется сбалансированной, если , в противном случае -несбалансированной.
Поскольку ограничения модели (7) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса. В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть:
Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:
Введение фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных тарифов (реально не существующих) для фиктивных перевозок. Поскольку нас интересует определение наиболее выгодных реальных перевозок, то необходимо предусмотреть, чтобы при решении задачи (при нахождении опорных планов) фиктивные перевозки не рассматривались до тех пор, пока не будут определены все реальные перевозки. Для этого надо фиктивные перевозки сделать невыгодными, то есть дорогими, чтобы при поиске решения задачи их рассматривали в самую последнюю очередь. Таким образом, величина фиктивных тарифов должна превышать максимальный из реальных тарифов, используемых в модели, то есть
На практике возможны ситуации, когда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов . Запрещающие тарифы необходимо сделать невозможными, то есть совершенно невыгодными, перевозки в соответствующих направлениях. Для этого величина запрещающих тарифов должна превышать максимальный из реальных тарифов, используемых в модели:
Построение первоначального опорного плана.
Распределительная таблица имеет вид
|
поставщики |
||||||
|
c11 x11 |
c12 x12 |
c1n x1n |
a1 |
|||
|
c21 x21 |
c22 x22 |
c2n x2n |
a2 |
|||
|
cm1 xm1 |
cm2 xm2 |
cmn xmn |
am |
|||
|
потребители |
b1 |
b2 |
…… |
bn |
Строки и столбцы по контуру таблицы служат для вспомогательных записей, а в клетках самой таблицы в правом верхнем углу пишут тарифы перевозок cij, а посреди клетки величины перевозок. Если в данном плане перевозка от i-ого поставщика к j-ому потребителю присутствует и составляет величину a 0, то значение xij = a заносится в клетку ( i,j ) и эта клетка считается занятой. Если перевозка отсутствует, то в клетку ничего не заносится и клетка считается свободной.
В крайний правый (вспомогательный) столбец пишут количества грузов имеющихся у поставщиков. В крайнюю нижнюю (вспомогательную) строку пишут количество грузов требующихся потребителю.
Замечание. Число занятых клеток основной таблицы обязательно должно быть равным m+n-1 (m - число строк, n - число столбцов основной таблицы). Если занятых клеток меньше, то план вырожденный и следует добавить клетки c нулевой перевозкой до m+n-1. Тогда в свободную клетку с наименьшим тарифом пишут число «0», и клетка считается занятой. Для того, чтобы занятых клеток было именно столько сколько нужно разработан ряд методов заполнения таблицы. В дальнейшем будем пользоваться одним из них, наиболее удобным для применения.
Метод минимальной стоимости
Заполнение таблицы начинаем с клетки с min тарифом, в которую заносится максимально возможная перевозка. Из оставшихся клеток выбираем клетку со следующим по величине тарифом и заносим в нее максимально возможную перевозку из оставшихся, и т.д. На последнем шаге остается один незаполнен-ный поставщик или потребитель и в его клетки заносятся оставшиеся перевозки уже несмотря на тарифы.
Пример. Даны поставщики А1=35, А2 =55 и потребители В1=10, В2=50, В3 =30.
Матрица тарифов Cij =
Строим первоначальный опорный план заполняя последовательно клетки методом минимальной стоимости.
3. Для проверки построенного опорного плана на оптимальность используется метод потенциалов. Для этого по числу строк m и числу столбцов n вводятся двойственные переменные , называемые потенциалами. После этого для каждой клетки определяется величина , называемая оценкой этой клетки. Признак оптимальности сохраняется тот же, что и в симплексном методе, а именно:
Если задача решается на min, то опорное решение будет оптимальным в том и только в том случае, если для всех клеток оценки будут неположительными (то есть все ). При этом для занятых клеток обязательно должно выполняться условие то есть , а для свободных клеток условие , или что то же самое .
На основании указанных равенств для занятых клеток сначала находятся все потенциалы ( для вырожденного плана учитывается и клетка с xij = 0 ). Кроме того, поскольку потенциалов m+n штук, а занятых клеток m+n-1, то для полу-чения замкнутой системы добавляется еще одно уравнение. Обычно это .
После того, как все потенциалы найдены, для свободных клеток проверяется условие . Если это условие выполнено для всех свободных клеток, то план оптимальный. Если есть свободные клетки, где это условие не выполнено, то план не оптимальный и в эти клетки надо занести (перераспределить) перевозки. Для этого из клеток с нарушенными условиями оптимальности () выбирают ту, в которой . Для перераспределения перевозок из выбранной клетки строят цикл пересчета.
Определение. Циклом в распределительной таблице ТЗ называется ломанная с вершинами в занятых клетках и звеньями вдоль столбцов и строк. В каждой вершине соединяются только 2 звена. Самопересечение вершиной не является.
Примеры циклов.
Для любой свободной клетки цикл единственен.
После построения цикла все его вершины помечаются знаками «+» и «-», начиная с «+» в исходной свободной клетке и чередуя знаки. Кроме исходной клетки все остальные знаки стоят в занятых клетках.
Из перевозок в вершинах со знаком «-» выбираем наименьшую и вычитаем ее из всех перевозок в вершинах со знаком «-», а затем прибавляем ее ко всем перевозкам в вершинах со знаком «+». Все остальные клетки без знаков оставляем без изменения. В результате одна свободная клетка из которой начинался цикл стала занятой, а одна занятая клетка в которой разность двух перевозок оказалась равной нулю стала свободной (в ней «0» не пишем). Число занятых клеток поэтому не изменилось. При этом, если разность двух перевозок оказалась равной нулю в двух клетках, то пустой делаем только одну клетку, ту, в которой тариф больше. В клетке с меньшим тарифом оставляем «0», и считаем ее занятой.
В результате получаем новый опорный план и повторяем всю процедуру проверки его на оптимальность заново.
Пример № 4 решения транспортной задачи
На 4-х базах у поставщиков имеется однородный груз в количестве
100, 200, 400, 300 ед. Его надо развести 5-и потребителям в количествах 50, 150, 250, 300, 200 ед. Стоимость доставки ед. груза от поставщика к потребителю задана матрицей тарифов
cij =
Составить план перевозок с минимальными транспортными затратами.
Решение
1. Проверяем условие баланса , т.е.
100+200+400+300 = 1000 50+150+250+300+200 = 950
Условие не выполнено, поэтому добавляем одного потребителя с 50 ед. груза.
2. Составляем распределительную таблицу, в которую заносится первый опорный план. У фиктивного потребителя в последнем столбце тарифы перевозок равны нулю и перевозки в его клетки заносятся в последнюю очередь.
|
поставщики |
||||||||
|
2 |
3 |
5 |
1 100 |
8 |
0 |
100 |
||
|
4 |
5 |
1 200 |
6 |
2 |
0 0 |
200 |
||
|
3 |
4 150 |
7 |
2 200 |
6 |
0 50 |
400 |
||
|
3 50 |
7 |
1 50 |
5 |
4 200 |
0 |
300 |
||
|
потребители |
50 |
150 |
250 |
300 |
200 |
50 |
1000=1000 |
Сначала согласно правилу минимальной стоимости заполняем клетки с минимальным тарифом, то есть с тарифом «1» (1-я строка 4-й столбец заносим 100 ед., 2-я строка 3-ий столбец заносим 200 ед., 4-я строка 3-ий столбец заносим 50 ед.). Затем клетки с тарифом «2» (3-я строка 4-й столбец заносим 200 ед.). Потом клетки с тарифом «3» (4-я строка 1-й столбец заносим 50 ед.) После этого клетки с тарифом «4» (3-я строка 2-ой столбец заносим 150 ед., 4-я строка 5-й столбец заносим 200 ед.). И, наконец, оставшиеся 50 ед. груза у 3-го поставщика заносим в клетку фиктивного потребителя с тарифом «0» (3-я строка 6-й столбец заносим 50 ед.).
Весь груз распределен. И поставщики и потребители полностью удовлетворены. Для проверки суммируем перевозки по строкам и столбцам - они должны совпадать со значениями запасов и потребностей в последних столбцах и строках.
3. Проверяем число занятых клеток. Их 8, а должно быть m+n-1 = 4+6-1 = 9. Мы получили вырожденный план. С таким планом дальше работать нельзя, поэтому добавляем нулевую перевозку в клетку с минимальным тарифом (пусть, например, это будет клетка в последнем столбце во 2-й строке).
План стал невырожденным. Идем дальше.
4. Находим стоимость перевозок (значение целевой функции) по этому плану
F = 100•1 + 200•1 + 0•0 + 150•4 + 200•2 + 50•0 + 50•3 + 50•1 + 200•4 = 2300
5. Для проверки условия оптимальности находим потенциалы по занятым клеткам из условия .
Зная находим последовательно все остальные потенциалы из приведенных уравнений, выбирая каждый раз уравнение так, чтобы один из входящих в него потенциалов был бы известен. Уравнения решаются устно, а потенциалы заносятся в распределительную таблицу (например: и т. д.)
6. Когда все потенциалы найдены, проверяем условие оптимальности для свободных клеток. Для этого находим оценки .
Так как нас интересует только случай когда (план не оптимальный), то в таблицу заносятся только положительные значения в левый нижний угол клетки (например, в нашем случае это будет только )
В результате получаем следующую таблицу
|
поставщики |
||||||||
|
2 |
3 |
5 |
1 100 |
8 |
0 |
100 |
||
|
4 |
5 |
1 200 |
6 |
2 |
0 0 |
200 |
||
|
3 |
4 150 |
7 |
2 200 |
6 |
0 50 |
400 |
||
|
3 50 |
7 |
1 50 |
5 |
4 200 |
0 |
300 |
||
|
потребители |
50 |
150 |
250 |
300 |
200 |
50 |
1000=1000 |
7. Так как в таблице есть положительные оценки клеток , то план не оптимальный. Для его улучшения выбираем клетку с положительной оценкой у которой . (Если несколько одинаковых , то берем ту где тариф меньше.) В нашем случае это одна клетка с . Из этой клетки строим цикл пересчета согласно приведенному выше определению. В силу единственности другого цикла из этой клетки получиться не может
|
Поставщики |
||||||||
|
2 |
3 |
5 |
1 100 |
8 |
0 |
100 |
||
|
4 |
5 |
1 200 |
6 |
2 |
0 0 |
200 |
||
|
3 |
4 150 |
7 |
2 200 |
6 |
0 50 |
400 |
||
|
3 50 |
7 |
1 50 |
5 |
4 200 |
0 |
300 |
||
|
Потребители |
50 |
150 |
250 |
300 |
200 |
50 |
1000=1000 |
Расставляем знаки в вершинах цикла чередуя их и начиная со знака «+» в свободной клетке (2;5) с положительной оценкой. Из клеток со знаком «-» выбираем ту где перевозка наименьшая. В нашем случае это
= min (200, 200) =200.
Вычитая значение 200 из перевозок в клетках со знаком «-» и прибавляя к перевозкам со знаком «+» получим новый опорный план. При этом свободные клетки и перевозки в клетках без знака оставляем без изменения.
Поскольку при вычитании освобождаются сразу две клетки, а надо чтобы только одна, то клетку (4;5) с большим тарифом «4» делаем свободной, а в клетку (2;3) с меньшим тарифом «1» заносим перевозку «0» и считаем ее занятой. В результате число занятых клеток осталось без изменения.
Замечание. В нашем случае три таблицы приведены только затем, чтобы показать последовательность заполнения клеток таблицы. На практике же все предыдущие рассуждения оформляются в виде одной таблицы, поэтому новый опорный план и его исследование приведем в одной таблице, как это и следует делать дальше.
|
Поставщики |
||||||||
|
2 |
3 |
5 |
1 100 |
8 |
0 |
100 |
||
|
4 |
5 |
1 0 |
6 |
2 200 |
0 0 |
200 |
||
|
3 |
4 150 |
7 |
2 200 |
6 |
0 50 |
400 |
||
|
3 50 |
7 |
1 250 |
5 |
4 |
0 |
300 |
||
|
Потребители |
50 |
150 |
250 |
300 |
200 |
50 |
1000=1000 |
В новом плане проверяем число занятых клеток - оно не нарушилось
Стоимость перевозок по новому плану составляет
F = 100·1 + 200·2 + 0·0 + 150·4 + 200·2 + 50·0 + 50·3 + 250·1 + 0·0 = 1900
Согласно формуле (6) должно выполняться Fнов = Fстар - .В нашем случае и , поэтому получаем Fнов = 2300 - 2•200 = 1900, что подтверждает правильность всех проведенных вычислений.
Аналогично предыдущему вычисляются потенциалы и оценки свободных клеток. Потенциалы приведены в таблице. Все оценки свободных клеток оказались отрицательными, поэтому в таблице они не приводятся, а полученный план с такими оценками является оптимальным.
Ответ: Вычеркивая фиктивного потребителя, получаем матрицу оптимальных перевозок и min стоимость перевозок равную 1900 ед.
4. Теория игр
Игра - это идеализированная математическая модель коллективного поведения нескольких лиц (игроков), интересы которых различны, что и порождает конфликт. Конфликт не обязательно предполагает наличие антагонистических противоречий сторон, но всегда связан с определенного рода разногласиями. Конфликтная ситуация будет антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину и наоборот. Антагонизм интересов порождает конфликт, а совпадение интересов сводит игру к координации действий (кооперации).
Примерами конфликтной ситуации являются ситуации, складывающиеся во взаимоотношениях покупателя и продавца; в условиях конкуренции различных фирм; в ходе боевых действий и др. Примерами игр являются и обычные игры: шахматы, шашки, карточные, салонные и др. (отсюда и название “теория игр” и ее терминология).
В большинстве игр, возникающих из анализа финансово-экономических, управленческих ситуаций, интересы игроков (сторон) не являются строго антагонистическими ни абсолютно совпадающими. Покупатель и продавец согласны, что в их общих интересах договориться о купле-продаже, однако они энергично торгуются при выборе конкретной цены в пределах взаимной выгодности.
Теория игр - это математическая теория конфликтных ситуаций.
Цель теории игр - выработка рекомендаций по разумному поведению участников конфликта (определение оптимальных стратегий поведения игроков).
От реального конфликта игра отличается тем, что ведется по определенным правилам. Эти правила устанавливают последовательность ходов, объем информации каждой стороны о поведении другой и результат игры в зависимости от сложившейся ситуации. Правилами устанавливаются также конец игры, когда некоторая последовательность ходов уже сделана, и больше ходов делать не разрешается.
В теории игр предполагается, что игра состоит из ходов, выполняемых игроками одновременно или последовательно.
Ходы бывают личными и случайными. Ход называется личным, если игрок сознательно выбирает его из совокупности возможных вариантов действий и осуществляет его (например, любой ход в шахматной игре). Ход называется случайным, если его выбор производится не игроком, а каким-либо механизмом случайного выбора (например, по результатам бросания монеты).
Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией.
Одним из основных понятий теории игр является понятие стратегии. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от ситуации, сложившейся в процессе игры. В простых (одноходовых) играх, когда в каждой партии игрок может сделать лишь по одному ходу, понятие стратегии и возможного варианта действий совпадают. В этом случае совокупность стратегий игрока охватывает все возможные его действия, а любое возможное для игрока i действие является его стратегией. В сложных (многоходовых играх) понятие «варианта возможных действий» и «стратегии» может отличаться друг от друга.
Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от того, какие стратегии применяет противник. Могут быть использованы и другие критерии оптимальности.
Возможно, что стратегия, обеспечивающая максимальный выигрыш, не обладает другим важным представлением оптимальности, как устойчивостью (равновесностью) решения. Решение игры является устойчивым (равновесным), если соответствующие этому решению стратегии образуют ситуацию, которую ни один из игроков не заинтересован изменить.
Повторим, что задача теории игр - нахождение оптимальных стратегий.
В зависимости от числа участников игры подразделяются на парные и множественные. В парной игре число участников равно двум, в множественной - более двух.
3. Участники множественной игры могут образовывать коалиции, как постоянные, так и временные. По характеру взаимоотношений игроков игры делятся на бескоалиционные, коалиционные и кооперативные.
Бескоалиционными называются игры, в которых игроки не имеют право вступать в соглашения, образовывать коалиции, и целью каждого игрока является получение по возможности наибольшего индивидуального выигрыша.
Игры, в которых действия игроков направлены на максимизацию выигрышей коллективов (коалиций) без последующего их разделения между игроками, называются коалиционными.
4.1 Примеры игр
Игра 1. Зачет
Пусть игрок 1 - студент, готовящийся к зачету, а игрок 2 - преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: А1- хорошо подготовиться к зачету; А2 - не подготовиться. У преподавателя имеется тоже две стратегии: В1 - поставить зачет; В2 - не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей
Игра 2. Морра
Игрой “морра” называется игра любого числа лиц, в которой все игроки одновременно показывают (“выбрасывают”) некоторое число пальцев. Каждой ситуации приписываются выигрыши, которые игроки в условиях этой ситуации получают из “банка”. Например, каждый игрок выигрывает показанное им число пальцев, если все остальные игроки показали другое число; он ничего не выигрывает во все остальных случаях. В соответствии с приведенной классификацией данная игра является стратегической; в общем случае, множественной (в этом случае игра может быть бескоалиционной, коалиционной, и кооперативной) конечной.
В частном случае, когда игра парная - это будет матричная игра (матричная игра всегда является антагонистической).
Пусть два игрока «выбрасывают» одновременно один, два или три пальца. При четной сумме выигрывает первый игрок, при нечетной - второй. Выигрыш равен сумме «выброшенных пальцев». Таким образом, в данном случае каждый из игроков имеет по три стратегии, а матрица выигрышей первого игрока (проигрышей второго) имеет вид:
|
В1 |
В2 |
В3 |
||
|
А1 |
2 |
-3 |
4 |
|
|
А2 |
-3 |
4 |
-5 |
|
|
А3 |
4 |
-5 |
6 |
где Аi - стратегия первого игрока, заключающаяся в «выбрасывании» i пальцев;
Вj - стратегия второго игрока, заключающаяся в «выбрасывании» j пальцев.
Что должен делать каждый из игроков, чтобы обеспечить себе максимальный выигрыш?
Игра 3. Борьба за рынки
Некая фирма А, имея в своем распоряжении 5 условных денежных единиц, пытается удержать два равноценных рынка сбыта. Ее конкурент (фирма В), имея сумму равную 4 условным денежным единицам, пытается вытеснить фирму А с одного из рынков. Каждый из конкурентов для защиты и завоевания соответствующего рынка может выделить целое число единиц своих средств. Считается, что если для защиты хотя бы одного из рынков фирма А выделит меньше средств, чем фирма В, то она проигрывает, а во всех остальных случаях - выигрывает. Пусть выигрыш фирмы А равен 1, а проигрыш равен (-1), тогда игра сводится к матричной игре, для которой матрица выигрышей фирмы А (проигрышей фирмы В) имеет вид:
|
В0 |
В1 |
В2 |
В3 |
В4 |
||
|
А0 |
1 |
-1 |
-1 |
-1 |
-1 |
|
|
А1 |
1 |
1 |
-1 |
-1 |
-1 |
|
|
А2 |
-1 |
1 |
1 |
-1 |
-1 |
|
|
А3 |
-1 |
-1 |
1 |
1 |
-1 |
|
|
А4 |
-1 |
-1 |
-1 |
1 |
1 |
|
|
А5 |
-1 |
-1 |
-1 |
-1 |
1 |
Здесь Аi - стратегия фирмы А, заключающаяся в выделении i условных денежных единиц на защиту первого рынка; Вj - стратегия фирмы В, заключающаяся в выделении j условных денежных единиц на завоевание первого рынка.
4.2 Матричные игры
Наиболее разработанной в теории игр является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций), называемая матричной игрой.
Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие антагонистические интересы: выигрыш одного игрока равен проигрышу второго. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, можем интересоваться только выигрышем а игрока А. Естественно, игрок А хочет максимизировать а, а игрок В - минимизировать а. Для простаты отождествим себя мысленно с одним из игроков (пусть это будет игрок А), тогда будем называть игрока В - “противник” (разумеется, каких-то реальных преимуществ для А из этого не вытекает).
Пусть у игрока А имеется m возможных стратегий А1, А2, ..., Аm, а у противника - n возможных стратегий В1, В2, ..., Bn (такая игра называется игрой m х n).
Обозначим через aij выигрыш игрока А, в случае, если он воспользуется стратегией Аi, а игрок В - стратегией Вj. Предполагается, что выигрыш aij известен. Тогда мы можем составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши.
|
Bj Ai |
B1 |
B2 |
. |
Bn |
|
|
A1 |
a11 |
a12 |
... |
a1n |
|
|
A2 |
a21 |
a22 |
... |
a2n |
|
|
... |
... |
... |
... |
... |
|
|
Am |
am1 |
am2 |
... |
amn |
Если такая таблица составлена, то говорят, что игра G приведено к матричной форме. Отсюда рассматриваемая игра и получила название матричная. Само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и невыполнимую, из-за необозримого множества возможных стратегий игроков и трудности определения выигрышей aij.
Рассмотрим некоторые задачи, решение которых сводится к решению матричных игр.
Игра 1. Вариант игры «Морра»
Игра состоит в том, что каждый из двух игроков независимо друг от друга выбирает определенную сторону монеты (“герб” или “решка”), затем одновременно называют свой выбор. Если игроки выбрали одну и ту же сторону монеты, то второй игрок платит первому одну гривну, если разные, то первый платит второму такую же сумму. Легко видеть, что матрица выигрышей (платежная матрица) этой игры имеет вид
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
1 |
-1 |
|
|
A2 |
-1 |
1 |
Здесь стратегии А1 и В1 - игроки А и В выбирают “герб”, а А2 и В2 - игроки А и В выбирают “решку”.
Нетривиальность сформулированной задачи, как и любой матричной игры, состоит в том, что каждый из игроков делает свой выбор независимо друг от друга.
Игра 2. Борьба за рынки
Фирмы А и В производят одинаковый товар и в настоящее время каждая «контролирует» 50% рынка. Улучшив качество товара, обе фирмы собираются развернуть рекламные кампании. При этом, приобретение новых покупателей одной фирмой сопровождается потерей этих покупателей другой фирмой. Исследование показало, что 60% потенциальных покупателей получают информацию через телевидение, 30% - через газеты и 10% - через радиовещание.
Задача каждой фирмы - выбрать стратегию рекламной кампании.
В данной игре у каждого из игроков по три стратегии:
А1, В1 - рекламировать товар через телевидение;
А2, В2 - через газеты;
А3, В3 - через радиовещание.
Поскольку это игра с нулевой суммой, то матрицу выигрышей фирмы А можно представить в следующем виде:
|
B1 |
B2 |
B3 |
||
|
A1 |
0 |
30 |
50 |
|
|
A2 |
-30 |
0 |
20 |
|
|
A3 |
-50 |
-20 |
0 |
где aij - количество покупателей товара фирмы А в процентах, на которое оно увеличивается, если фирма А применяет стратегию Аi , а фирма В - стратегию Вj.
4.3 Принцип максимина в антагонистических играх. Седловая точка
Как отмечалось, важнейшим вопросом в теории игр (в том числе и матричных) является вопрос о выборе оптимальных стратегий для каждого из игроков.
Оптимальной стратегией игрока в матричной игре называется такая, которая обеспечивает ему максимальный выигрыш. Если игра повторяется неоднократно, то оптимальная стратегия должна обеспечивать максимальный средний выигрыш.
При выборе этой стратегии основой рассуждений является предположение, что противник является, по меньшей мере, так же разумен, как и мы сами, и делает все, чтобы добиться такой же цели.
Расчет на разумного противника - лишь одна из возможных позиций в конфликте, но в теории игр именно она кладется в основу.
При этом для выбора оптимальной стратегии используют принцип максимина: выбирай ту стратегию, чтобы при наихудшем для нас поведении противника получить максимальный выигрыш. Другими словами, принцип максимина предполагает выбор той стратегии, при которой наш минимальный выигрыш для различных стратегий максимален. Отсюда и название «принцип максимина».
Как видно, принцип максимина - это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.
Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А3. Но при этом противник может выбрать стратегию В3, и игрок А получит выигрыш, равный всего трем.
Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение i в каждой строке (минимум строки). Из всех значений i (правый столбец) выделим наибольшее. Ему соответствует стратегия А4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.
Эта величина - наш гарантированный выигрыш. Он называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его . В нашем примере = aij =5.
Теперь станем на точку зрения игрока В и порассуждаем за него. Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наихудшее для него поведение игрока А.
Припишем к платежной матрице (рис.2.2) нижнюю строку и в ней запишем наихудшее для игрока В возможные результаты (максимумы столбцов j.
Очевидно, осторожный противник должен выбрать стратегию, при которой величина j минимальна. Эта величина называется верхней ценой игры (или “минимаксом” - минимальный из максимальных проигрышей). Будем обозначать ее . В нашем примере = aij = 7.
Подобные документы
Способы решения системы уравнений с двумя переменными. Прямая как график линейного уравнения. Использование способов подстановки и сложения при решении систем линейных уравнений с двумя переменными. Решение системы линейных уравнений методом Гаусса.
реферат [532,7 K], добавлен 10.11.2009Определение системы с двумя переменными, способ ее решения. Специфика преобразования линейных уравнений с двумя переменными. Способ сложения и замены переменных в этом виде уравнений, примеры их графиков. Алгоритм нахождения количества системы уравнений.
презентация [226,6 K], добавлен 08.12.2011Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.
курсовая работа [132,2 K], добавлен 10.01.2014Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлен 21.05.2010Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Изучение общих сведений о матричных и антагонистических играх. Понятие позиционной игры, дерева, информационного множества. Рассмотрение принципа максимина и принципа равновесия. Оптимальность по Парето. Позиционная неантагонистическая игра, ее свойства.
курсовая работа [1,4 M], добавлен 17.10.2014История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
курсовая работа [166,7 K], добавлен 17.07.2002Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011
