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

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Введение

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной.

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

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

1. Предмет теории игр

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

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

Всякая теоретико-игровая модель должна отражать, кто и как конфликтует, а также, кто и в какой форме заинтересован в том или ином исходе конфликта.

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

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

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

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

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

(1.1)

линейный язык матрица программирование

где - равен выигрышу первого (будем обозначать его А) и проигрышу второго (игрока В) при применении ими i-й и j-й чистых стратегий соответственно.

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

1.1 Нижняя и верхняя цены игры. Принцип минимакса

Итак, рассмотрим матричную игру с платежной матрицей

(1.2)

Где i-я строка соответствует А_i-й стратегии игрока А;

j-й столбец соответствует В_j-й стратегии игрока В.

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

Очевидно, находится в одной из строк матрицы Н, пусть в i₀, тогда стратегия называется максиминной.

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

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

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

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

Рассмотрим пример нахождения и .

Пример (п. 1.1)

Пусть игра задана матрицей

Определим нижнюю и верхнюю цены игры.

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



В этом примере нижняя и верхняя цены игры совпадают:

1.2 Вполне определённые игры

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

(1.3)

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

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

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

Решением игры в примере (п. 1.1) (1.3) является выбор стратегий игроком и игроком , при этом цена игры V = 3.

1.3 Игры, не содержащие седловой точки. Смешанные стратегии

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

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

. (1.4)

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

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

. (1.5)

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

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

Для ответа на этот вопрос введём вероятность (относительную частоту) применение игроком А i-й стратегии, и - вероятность применения j-й стратегии игроком В. Совокупности этих вероятностей определяют векторы

, где и , где .

Эти векторы или наборы вероятностей выбора чистых стратегий называются смешанными стратегиями игроков.

В частности, решение игры с седловой точкой даётся векторами и , среди компонент которых , и , .

Для получения ограничений на средний выигрыш или проигрыш рассмотрим математическое ожидание выигрыша первого игрока

. (1.6)

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

. (1.7)

Аналогично, при выборе первым игроком некоторой стратегии второму игроку следует выбирать стратегию такую, что

. (1.8)

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

Основная теорема теории игр (доказана фон Нейманом в 1928 году) утверждает:

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

. (1.9)

Число называют ценой игры.

Примечание. Нулевая сумма означает, что выигрыш одного игрока равен проигрышу другого.

Из основной теоремы следует, что каждая конечная игра имеет цену и она лежит между нижней и верхней ценами игры (1.8).

И, если один из игроков придерживается своей оптимальной стратегии, то выигрыш (проигрыш) его остаётся неизменным независимо от тактики другого игрока, если, конечно, последний не выходит за пределы своих «полезных» стратегий, иначе выигрыш (проигрыш) возрастает.

Это означает выполнение неравенств

, (1.10)

,. (1.11)

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

2. Элементарные методы решения матричных игр , ,

2.1 Игра

Наиболее простой матричной игрой является игра , в которой игроки имеют по две чистых стратегии.

Пусть матрица такой игры

. (2.1)

Если седловой точки нет, то решением игры являются смешанные стратегии (2.2)

. (2.3)

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

Кроме того, .

Решение этих уравнений даёт:

, (2.4)

, (2.5)

. (2.6)

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

(2.7)

Ее решение даётся формулами

(2.8)

(2.9)

Пример (п. 2.1)

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

Седловой точки нет. Тогда, согласно формул: (2.4), (2.5), (2.6), (2.8) и (2.9), оптимальными стратегиями будут

, , цена игры .

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

Пример (п. 2.2)

Цех заготовитель поставляет в сборочный цех детали двух видов a и b. По договору между цехами оговорены ежедневно два срока поставки этих деталей, причём, при поставке в первый срок деталей вида «а» сборочный цех платит заготовительному премию 50 руб., при поставке же изделий «а» выплачивается премия 20 руб. При поставке же изделий вида «b» в первый срок премия составляет 30 руб., а во второй - 40 руб. Определить оптимальные стратегии поставок и получения деталей.

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

Таблица 2.1. Матрица игры заданная таблицей

	I срок	II срок
Детали «а» Детали «b»	50 30	20 40

Значит, ,

,

,

, следовательно, седловой точки нет. Для нахождения оптимальных стратегий применим формулы (2.4), (2.5), (2.6), (2.8) и (2.9):

; ;

; ;

(руб.).

Таким образом, цех-изготовитель поставляет детали вида а и b с вероятностями , , при этом гарантированная премия 35 рублей, а сборочный цех получает эти детали в сроки I и II с вероятностями , и выплачивает 35 рублей премии заготовительному цеху ежедневно. Полученные вероятности и определяют оптимальные стратегии

, .

Примечание. Игры допускают простое графическое толкование и решение, следующее из него. Действительно, пусть игра задана матрицей (2.1). На оси абсцисс отложим отрезок 0D, равный 1, и условимся считать, что левый конец отрезка - стратегии А₂, тогда промежуточная точка N с координатой x соответствует некоторой смешанной стратегии первого игрока, причём, , , так как при имеем и , и при имеем и .

Вводя ось 0y, можно построить прямую, отвечающую стратегии второго игрока, её уравнение (при каждом x, y даёт значение выигрыша игрока А, когда В применяет стратегию В₁). Отметим, что для построения В₁ достаточно провести из концов отрезка 0D прямые, не перпендикулярные ему, на левой прямой отложить , на правой - и, соединив их получим прямую В₁В_1, отвечающую стратегии В₁ рис. 2.1. Затем аналогично строим стратегию В₂ (её уравнение ). Заметим, что при каждом x точки на прямых В₁В₁ и В₂В₂ отвечают выигрышем первого игрока при применении вторым игроком стратегий В₂ и В₁ соответственно. Откуда следует, что ломаная В₂КВ₁ рис. 2.2 отвечает нижней границе выигрыша игрока А, а значит в точке её максимума, то есть цена игры и точка N отвечает оптимальной стратегии игрока А: .

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

; (2.10)

. (2.11)

В справедливости формул (2.10) и (2.11) легко убедиться, подставив значения LB₂ и LB₁, , и значение , тогда получим формулы, совпадающие с (2.10) и (2.11).

Аналогично, меняя ролями x и y, можно построить решение для игрока А.

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Рис. 2.1. Графическое рис. 2.2. Графическое толкование игры толкование игры

2.2 Решение игры

Пусть игра задана матрицей

.

Строим прямые, соответствующие стратегиям игрока В рис. 2.3.

Ломаная соответствует нижней границе выигрыша, точка К на ней даёт решение игры: , , .

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

, .

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

2.3 Решение игры

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

Пусть игра задана матрицей

.

Решение задачи находим для игрока В рис. 2.4.

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

, , .

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

, .

Матрица оптимальных стратегий имеет вид . Тогда решение можно найти по формулам (2.4), (2.5), (2.6), (2.8) и (2.9).

Следовательно, решение игры таково:

, , .

2.4 Решение матричных игр

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

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

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

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

Пример (п. 2.3)

Магазин может завести в различных пропорциях товары четырёх типов . Их реализация и прибыль магазина зависят от вида товара и состояния спроса.

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

Таблица 2.2. Матрица прибыли

Тип товара	Спрос
	В1	В2	В3	В4	В5
А1 А2 А3 А4	200 300 400 700	400 400 500 300	600 600 600 500	400 500 500 200	700 800 800 100

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

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

Следовательно, имеет смысл анализировать игру , заданную табл. 1.4. Решение этой матрицы даёт оптимальную стратегию завоза товаров , т.е. нужно завести товара третьего типа и товара четвёртого типа, а товары первого и второго типов не завозить, при этом средняя гарантированная прибыль (цена игры) .

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

.

Нужно выбрать тип технологической линии, при которой прибыль будет наибольшей.

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

3. Линейное программирование

линейный язык матрица программирование

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

В самом общем виде задача математически записывается так:

; , (3.1)

где ;

- область допустимых значений переменных ;

- целевая функция.

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

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

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

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

1. Задачи линейного программирования, если и линейны.

2. Задачи целочисленного программирования, если ставится условие целочисленности переменных .

3. Задачи не линейного программирования, если форма носит не линейный характер.

3.1 Задачи линейного программирования

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

(3.2)

, , ; (3.3)

, ; (3.4)

, , . (3.5)

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

В частном случае, если O, то система (3.3) - (3.4) состоит только из линейных неравенств, а если , то - из линейных уравнений.

Если математическая модель задачи линейного программирования имеет вид:

; (3.6)

, ; ; (3.7)

, , (3.8)

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

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

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

1. Если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции.

2. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1.

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

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

3.2 Построение экономико-математических моделей задач линейного программирования

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

Пример (п. 3.1)

Определение оптимального ассортимента продукции.

Предприятие изготовляет два вида продукции - П₁ и П₂, которая поступает в оптовую продажу. Для производства продукции используют два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П₁ и П₂ дан в табл. 3.1.

Опыт работы показал, что суточный спрос на продукцию П₂ никогда не превышает 2 ед. в сутки.

Таблица 3.1. Расход сырья на единицу продукции

Сырьё	Расход сырья на ед. продукции	Запас сырья, ед.
	П1	П2
А В	2 3	3 2	9 13

Оптовые цены единицы продукции равны: 3 д. е. - для П₁ и 4 д. е. для П₂.

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

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

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

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

3. В чём состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

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

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

Доход от реализации единиц продукции П₁ и единиц продукции П₂ составит .

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

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

Пример (п. 3.2)

Использование мощностей оборудования.

Предприятие имеет моделей машин различных мощностей. Задан план по времени и номенклатуре: T - время работы каждой машин; продукции j-го вида должно быть выпущено не менее N_j единиц.

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

Другими словами, задача для предприятия состоит в следующем: требуется определить время работы i-й машины по выпуску j-го вида продукции , обеспечивающие минимальные затраты на производство при соблюдении ограничений по общему времени работы машин T и заданному количеству продукции N_j.

По условию задачи машины работают заданное время Т, поэтому данное ограничение можно представить в следующем виде:

, . (3.9)

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

, . (3.10)

Задача решается на минимум затрат на производство:

. (3.11)

Необходимо также учесть не отрицательность переменных .

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

, ; (3.12)

, ; (3.13)

;

(3.14)

Пример (п. 3.3)

Минимизация дисбаланса на линии сборки.

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

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

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

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

Пусть - недельный фонд времени (в часах), выделяемый на заводе для производства узла . Тогда объёмы производства узла будут следующими:

, . (3.15)

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

. (3.16)

Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод .

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

Максимизируем

; (3.17)

, ; (3.18)

для всех и .

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

. (3.19)

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

, ; (3.20)

, ; (3.21)

для всех и ; .

Пример (п. 3.4)

Задача составления кормовой смеси, или задача о диете.

Пусть крупная фирма (Условно назову ее «Суперрацион») имеет возможность покупать различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных компонентов (ингредиентов).

Лабораторией фирмы установлено, что продукция должна удовлетворять по крайней мере некоторым минимальным требованиям с очки зрения с точки зрения питательности (полезности). Перед руководством фирмы стоит задача определить количество каждого i-го сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и её питательности.

Решение

Введём условные обозначения:

- количество i-го сырья в смеси;

- количество видов сырья;

- количество ингредиентов в сырье;

- количество ингредиента j, содержащегося в единице i-го вида сырья;

- минимальное количество ингредиента j, содержащегося в единице смеси;

- стоимость единицы сырья I;

- минимальный общий вес смеси, используемый фирмой.

Задача может быть представлена в виде

, (3.22)

при следующих ограничениях:

на общий расход смеси:

; (3.23)

на питательность смеси:

, ; (3.24)

на не отрицательность переменных:

, . (3.25)

Пример (п. 3.5)

Задача составления жидких смесей.

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

Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m-видов. Обозначим подлежащее определению количество литров i-го химического компонента, используемого для получения j-го продукта через . Будем предполагать, что

, , .

Первая группа ограничений относится к объёмам потребляемых химических компонентов:

, , (3.26)

где - объём i-го химического компонента, которым располагает фирма в начале планируемого периода.

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

, . (3.27)

где - минимальный спрос на продукцию в течение планируемого периода.

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

или . ,

где - некоторая заданная константа.

Обозначим через доход с единицы продукции , запишем целевую функцию:

. (3.28)

Пример (п. 3.6)

Задача о раскрое или минимизации обрезков.

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

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

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

В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j-м варианте раскроя. Определим переменную следующим образом: - количество стандартных рулонов, разрезаемых по варианту , .

Целевая функция - минимум отходов при раскрое

(3.29)

Ограничение на удовлетворение спроса потребителя

, , . (3.30)

Пример (п. 3.7)

Многостойный коммерческий арбитраж.

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

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

Таблица 3.2. Многосторонний коммерческий арбитраж

Валютный номинал	Тип трансакции	Возмож- ность рынка
	1	2	3	4	5	6	7	8	9
I II III IV V VI
Размер трансакции

При трансакции продажа единицы валютного наминала (ценных бумаг) II позволяет приобрести валютного наминала I. При трансакции взамен единицы валютного наминала I можно получить единиц валютного наминала III и валютного наминала VI. Остальные трансакции расшифровываются аналогично. Значения могут быть дробными. Заметим, что при любой трансакции каждый из валютных номиналов можно обменять на валютный номинал I. Следует обратить внимание на правило выбора знака перед показателями в табл. 3.2. Чтобы отличить куплю от продажи, буду соответственно использовать знаки «плюс» и «минус» перед показателями, характеризующими данную трансакцию.

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

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

.

Пример (п. 3.8)

Транспортная задача.

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

.

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

Введу переменную - количество груза, перевозимого от i-го поставщика j-му потребителю.

Ограничения задачи выглядят следующим образом:

· потребности всех потребителей должны быть удовлетворены полностью:

(3.31)

или в общем виде:

,

· груз от поставщика должен быть вывезен полностью:

(3.32)

или в общем виде:

, ;

· условие не отрицательности переменных:

, , .

Целевая функция должна минимизировать суммарные затраты на перевозку:

. (3.33)

Количество поставщиков и потребителей в общем случае может быть произвольным .

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

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

2. Линейная функция может стремиться как к максимуму, так и к минимуму.

3. Переменные в задачах всегда неотрицательны.

Из любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программирования.

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

Графический способ решения задачи линейного программирования целесообразно использовать для:

· решения задач с двумя переменными, когда ограничения выражены неравенствами;

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

Запишем задачу линейного программирования с двумя переменными:

целевая функция:

 (3.34)

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

(3.35)

(3.36)

Каждое из неравенств (3.35) - (3.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ; ; ; . В том случае, если система неравенств (3.35) - (3.36) совместна, область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей - выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений с заменой знаков неравенств на знаки равенств.

Областью допустимых решений системы неравенств (3.35) - (3.36) может быть:

· выпуклый многоугольник;

· выпуклая многоугольная неограниченная область;

· пустая область;

· луч;

· отрезок;

· единственная точка.

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

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

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (3.35) - (3.36) и семейство параллельных прямых (3.34), то задача определения максимума функции сведётся к нахождению в допустимой области точки, через которую проходит прямая из семейства , и которая соответствует наибольшему значению параметра .

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

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

Заканчивая рассмотрение геометрической интерпретации задачи (3.34) - (3.36), отмечу, что при нахождении её решения могут встретится случаи, изображенные на рис. 3.1 - 3.4.

Рис. 3.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 3.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Рис. 3.1. Оптимум Рис. 3.2. Оптимум Функция Z Функция Z достижим в точке А достигается в любой точке [AB]

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

71

Размещено на http://www.allbest.ru/

Рис. 3.3. Оптимум Рис. 3.4. Область допустимых

Функция Z недостижим решений - пустая область

На рис. 3.3 изображен случай, когда максимум недостижим, а на рис. 3.4 - случай, когда система ограничений задачи несовместна. Отмечу, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения её максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении её минимального значения.

Для практического решения задачи линейного программирования (3.34) - (3.36) на основе её геометрической интерпретации необходимо следующее:

1. Построить прямые, уравнения которых получается в результате замены в ограничениях (3.34) - (3.36) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений задачи.

3. Определить многоугольник решений.

4. Построить вектор .

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

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

4. Симплекс-метод

Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причём в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи симплекс-методом распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б¹ с таим расчётом, чтобы значение функции Z уменьшилось, т.е. . Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б^(k), для которого есть искомый минимум для линейной функции Z, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

4.1 Алгоритм симплекс-метода

Рассмотрю систему ограничений и линейную форму вида:

(4.1)

(4.2)

, . (4.3)

Используя метод Жордана-Гауса, приведём записанную систему к виду, где выделены базисные переменные.

Введём условные обозначения:

- базисные переменные;

- свободные переменные.

(4.4)

. (4.5)

По последней системе ограничений построим табл. 4.1.

Таблица 4.1. Симплекс-таблица

Свободные неизвестные Базисные неизвестные	Свободный член

Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

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

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

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

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

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

Таблица 4.2. Симплекс-таблица

Свободные неизвестные Базисные неизвестные	Свободный член

6. Элемент табл. 4.2 соответствующий разрешающему элементу табл. 4.1, равен обратной величине разрешающего элемента.

7. Элементы строки табл. 4.2, соответствующие элементам разрешающей стоки табл. 4.1, получаются путём деления соответствующих элементов табл. 4.1 на разрешающий элемент.

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

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 4.2, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент табл. 4.2 будет равен соответствующему элементу табл. 4.1 минус дробь в знаменателе который стоит разрешающий элемент, а в числителе произведение элементов из двух неиспользованных вершин прямоугольника.

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

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

5. Методы нахождения опорного решения задачи линейного программирования.

5.1 Метод искусственного базиса

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

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

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

(5.1)

Перепишем систему (5.1) в другом виде. Для этого введём искусственные переменные так, чтобы был выделен базис. Тогда система примет вид

 (5.2)

Системы (5.1) и (5.2) будут эквивалентны в том случае, если все , для будут равны 0. Кроме того, считаю, что все для . В противном случае соответствующие ограничения из системы (5.1) умножим на - 1. Для того чтобы были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменные перешли в свободные неизвестные.

В этом случае система (5.2) после преобразования примет вид:

(5.3)

От системы (5.2) к системе (5.3) всегда можно перейти шагами симплекс-метода. При таком переходе в качестве линейной формы рассматривают функцию

, (5.4)

равную сумме искусственных переменных. Переход заканчивают, когда и все искусственные переменные переведены в свободные неизвестные.

Анализ вариантов решений

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

2. Если , а часть осталась в базисе, то для перевода их в свободные необходимо применять специальные приёмы.

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

Рекомендуется вводить минимум искусственных переменных.

5.2 Второй алгоритм отыскания опорного плана

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

(5.5)

(5.6)

, , , .

Построим первую таблицу Жордана-Гаусса для задач (5.5) и (5.6). Для единообразия вычислительной процедуры к исходной таблице приписываем строку целевой функции:

(5.7)

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