Беклемишев - Дополнительные главы линейной алгебры (947281), страница 70

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

Текст из файла (страница 70)

Например, пусть в пунктах Аг, с' = 1, ..., т, может быть организовано производство некоторого продукта в размерах аг, что требует затрат )г. Потребители в пунктах В, имеют потребности Ьо 1== 1, ..., и, которые надо удовлетворить наиболее экономным способом с учетом затрат су на транспортировку от Ас до Вг.

Это приводит к задаче линейного программирования с целевой функцией 'У, 'соху+ 'У, 'с'су„ с,с с где у; == 0 или 1 в зависимости от того, организуется производство в пункте Аг или нет. Прн внешнем сходстве с транспортной задачей эта задача, называемая простейшей задачей раэмеисенияг производства, гораздо сложнее именно из-за условия целочисленности ус. Могло бы возникнуть мнение, что решение задачи дискретного линейного программирования получается при подходящем округлении решения задачи обычного линейного программирования, получаемой отбрасыванием условий целочисленности.

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

Однако существует несколько дискретных задач, решение которых можио получить, решая соответствующую линейную задачу. Ояи связавы с рзссмсгг1эем- 816 Гл, Р. системы неРАВенстВ и линейное пРОГРАммиРОВАние ными нами транспортной и сетевой задачами, и мы на одной из них сейчас остановимся. Задача о назначениях заключается в следующем. Пусть имеется и. должностей и столько же кандидатов на эти должности, причем каждый из кандидатов в разной степени удовлетворяет требованиям, предъявляемым для замещения какой-либо из должностей.

(Конечно, это могут быть не должности и кандидаты на них, а, скажем, строительные объекты и машины, на них используемые, и т. д.) Пусть ожидаемый эфо о о о а а б о о о Р о фЕКТ ОТ НВЗНВ1!ЕНИЯ С.ГО кандидата на (сю долж— -- *Р- о о о о о о о о о а о о сц с у=1 и Нуж но составить такой список назначений, чтобы ожидаемый эффект от о о о о а Р о о Р о о о ПРННЯТИЯ таКОГО СПИСКа был максимальным.

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

Введем переменные хц, и пусть хц — — 1, если с-й кандидат назначен на слю должность, и хц = О, если не назначен. Тогда ожидаемый эффект от принятия списка, задаваемого матрицей Х = = |1хсс |~, будет равен ~ гцхц. с,с (6) хсс=1, 'У, 'хц 1. С 1 ! (л хсс~О, Однако.эти услоцияс конечно, недостаточны и не гарантируют того, ((1з.рсе хсс равны нулю или единице. Эта сумма должна быть сделана максимальной при условии, что Х есть матрица перестановки, т.

е, каждая ее строка и каждый столбец содержат одну и только одну единицу, а остальные элементы— йули. Если Х вЂ” матрица перестановки, то выполнены условия з а пеиложзния линвиного пвогелмминовлния 317 Таким образом, решение задачи максимизации суммы (6) при условиях (7) дает решение задачи о назначениях, если его компоненты ха равны нулю илн единице, и бесполезно в противном случае. Заметим, что сформулированная задача отличается от транспортной задачи только тем, что требуется максимизация функции, а не ее минимизация.

Зто отличие, конечно, не имеет отношения к свойствам матрицы системы ограничений, и для этой матрицы справедливо предложение 2. Из предложения 2 немедленно следует свойство нелочисленности решений транспортной задачи: если ЧИСЛа а, И Ьт ЦЕЛЫЕ, тО ВСЕ ВЕРШИНЫ МНОГОГРаННИКа ет ДОПУСТИМЫХ точек транспортной задачи имеют только целые координаты. Заметим, что аналогичное свойство целочислеиности для задачи о максимальном потоке следует из предложения 3, если пропускные способности — целые числа. Итак, мы можем быть уверены, что для задачи с ограничениями (7) максимум функции (6) достигается в точке с целыми координатами. Если решение не единственно, среди решений будут н не целочисленные, но целочисленное решение обязательно существует. Белые ху неотрицательны, и суммы (7) равны единнце, Поэтому все ху равны либо нулю, либо единице.

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

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

Процесс принятия решений предполагается однократным, т. е. выигрыш определяется после того, как каждый участник игры принял решение один раз. Решения, принимаемые игроками, иазы- 318 ГЛ, Ч, СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕИНОЕ ПРОГРАММИРОВАНИЕ ваются стратегиями. В таких играх, как шахматы, противники делают по многу ходов, на каждом из которых принимается решение.

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

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

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

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

Эле. мент матрицы ау равен выигрышу, который получит первый игрок, еслР, он выберет стратегию с номером 1, а противник выберет стратегию с номером 1', Если бы мы поменяли игроков местами, то в матрице строки заменились бы столбцами, столбцы — строками, а элементы матрицы изменили бы знаки. Таким образом, матрица А заменилась бы на — Аг. Например, симметричная игра, в которой оба игрока находятся в одинаковом положении, должна иметь кососнмметрическую матрицу. Разумеется, для задания игры достаточно указать матрицу для первого игрока.

Так мы и поступим, хотя это вводит некоторую несимметричность в обозначения, Будет рассматриваться игра, заданная матрицей А размеров т х и с элементами ау. Первый игрок имеет т стратегий, второй — а. При этом мы можем считать, что игра состоит в том, что первый игрок выбирает строку матрицы, а второй независимо от него выбирает столбец. Еслй нй пересечении строки и столбца стоит элемент ау, то первый игрок получает ау, а второй получает — ау.

Характеристики

Список файлов книги