Постановка задачи целочисленного программирования

Автор: | 06.01.2018

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

В общем виде математическая модель задачи целочисленного программирования имеет вид:

Определить максимальное (минимальное) значение функции:

Постановка задачи целочисленного программирования

при ограничениях

Постановка задачи целочисленного программирования

Постановка задачи целочисленного программирования

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

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

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

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

2. Определение оптимального плана задачи целочисленного программирования (метод Гомори).

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

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

Базис СБаз. В С1 С2 Сr Сr+1 Cn
х1 х2 хr хr+1 хn
х1 C1 b1 h1,r+1 h1n
х2 C2 b2 h2,r+1 h2n
xr Cr br hr,r+1 hrn
Δj Z(х0) Δr+1 Δn

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


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

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

Дробную часть чисел Постановка задачи целочисленного программирования и Постановка задачи целочисленного программирования обозначим Постановка задачи целочисленного программирования и Постановка задачи целочисленного программирования , она определяется следующим образом:

Постановка задачи целочисленного программирования , Постановка задачи целочисленного программирования

Примеры:

Постановка задачи целочисленного программирования

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

Постановка задачи целочисленного программирования

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

Примечание.1) Если Постановка задачи целочисленного программирования - дробное число, а все Постановка задачи целочисленного программирования - целые числа, то задача линейного программирования не имеет целочисленного решения.

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

1.Понятие об игровых моделях.

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

1) доход производителя некоторого продукта зависит не только от цены на этот продукт, но и от того, сколько продукта решит купить покупатель по данной цене;

2) при выборе ассортимента товаров, выпускаемых данным предприятием, необходимо учитывать, какой ассортимент товаров будут выпускать другие предприятия. Иначе может оказаться, что товары, выпущенные данным предприятием, не найдут сбыта;

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

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

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

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

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

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

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

Наибольшее практическое значение имеют парные игры. Обозначим игроков через А и В. Предполагается, что результат игры (выигрыш) определяется некоторым числом.

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

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

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

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

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

Постановка задачи целочисленного программирования

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

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

Постановка задачи целочисленного программирования

Величина Постановка задачи целочисленного программирования -гарантированный выигрыш игрока А – называется нижней ценой игры. Стратегия обеспечивающая получение Постановка задачи целочисленного программирования называется максиминной.

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

Постановка задачи целочисленного программирования

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

Теорема. Нижняя цена игры всегда не превосходит верхней цены игры. Постановка задачи целочисленного программирования .

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

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

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

Смешанной стратегией Постановка задачи целочисленного программирования игрока А называется применение им чистых стратегий Постановка задачи целочисленного программирования с вероятностями Постановка задачи целочисленного программирования соответственно, причем Постановка задачи целочисленного программирования Постановка задачи целочисленного программирования

Аналогично определяется смешанные стратегии Постановка задачи целочисленного программирования игрока В, как применение чистых стратегий Постановка задачи целочисленного программирования с вероятностями Постановка задачи целочисленного программирования соответственно, причем Постановка задачи целочисленного программирования

Основная теорема теории игр (Теорема Неймана).

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

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

Теорема об активных стратегиях:

Если один из игроков придерживается своей активной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

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

Рассмотрим матричную игру 2x2. Платежная матрица такой игры имеет вид:

Постановка задачи целочисленного программирования

Если седловой точки нет, то решением являются смешанные стратегии Постановка задачи целочисленного программирования , которые находятся из решения систем уравнений:

(1) Постановка задачи целочисленного программирования и Постановка задачи целочисленного программирования (2)

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

2. Решение игр с помощью линейного программирования.

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

Пусть игра mxn задана платежной матрицей

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

и не имеет седловой точки. Тогда для отыскания оптимальной стратегии игрока А рассмотрим систему

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

Разделим на v>0 и обозначим Постановка задачи целочисленного программирования , (i=1,2,…,m). (3)

Тогда имеем систему:

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

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

Постановка задачи целочисленного программирования Z=x1+x2+…+xm

при условии, что выполняются ограничения (4).

Решая задачу симплекс методом находим хi (i=1,2,..,m), Z= Постановка задачи целочисленного программирования , а затем pi=vixi.

Аналогично для игрока В получаем двойственную задачу линейного программирования:

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

Постановка задачи целочисленного программирования , где Постановка задачи целочисленного программирования

Итак, решение игры mxn свелось к решению двойственной пары задач линейного программирования. Согласно теоремам теории игр это решение всегда существует.

3.Критерии выбора решений в условиях неопределенности.

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

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

1. Критерий Байеса.

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

Постановка задачи целочисленного программирования ,

где Постановка задачи целочисленного программирования – вероятности состояний природы, причем Постановка задачи целочисленного программирования .

2. Критерий Лапласа.

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

Постановка задачи целочисленного программирования

Критерием принятия решения является максимум математического ожидания выигрыша, то есть Постановка задачи целочисленного программирования

Если распределение вероятностей состояний природы неизвестно, то используются следующие критерии:

3. Максимальный критерий Вальда.

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

Постановка задачи целочисленного программирования

4. Критерий минимального риска Сэвиджа.

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

Постановка задачи целочисленного программирования

где Постановка задачи целочисленного программирования .

5. Критерий Гурвица

Выбирается стратегия, при которой достигается

Постановка задачи целочисленного программирования ,

где Постановка задачи целочисленного программирования - степень оптимизма

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

Мы не можем признать окончательное решение, выбранное по какому-либо одному критерию. Поэтому необходимо проанализировать решения, полученные по указанным критериям, и выбрать доминирующий ответ.

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *