5. ТЕОРИЯ ИГР И СТАТИСТИЧЕСКИХ РЕШЕНИЙ

5.1. Матричная игра с нулевой суммой

Экономико-математическое моделирование осуществляется в условиях:

Определенности;

Неопределенности.

Моделирование в условиях определенности предполагает наличие всех необходимых для этого исходных нормативных данных (матричное моделирование, сетевое планирование и управление).

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

Моделирование в условиях неопределенности соответствует полному отсутствию некоторых необходимых для этого данных (теория игр).

Математические модели принятия оптимальных решений в конфликтных ситуациях строятся в условиях неопределенности.

В теории игр оперируют следующими основными понятиями:

Стратегия;

Функция выигрыша.

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

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

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

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

где - величина платежа игроку I, выбравшему ход , от игрока II, выбравшего ход .

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

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

Задается платежная матрица ;

Игрок I независимо от игрока II выбирает одну из строк этой матрицы, например, -ую;

Игрок II независимо от игрока I выбирает один из столбцов этой матрицы, например, - ый;

Элемент матрицы определяет, сколько получит игрок I от игрока II. Разумеется, если , то речь идет о фактическом проигрыше игрока I.

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

Пример

Рассмотрим игру .

Задана платежная матрица:

.

Пусть игрок I независимо от игрока II выбирает 3-ю строку этой матрицы, а игрок II независимо от игрока I выбирает 2-ой столбец этой матрицы:

Тогда игрок I получит 9 единиц от игрока II.

5.2. Оптимальная чистая стратегия в матричной игре

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

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

.

Игрок II рассуждает аналогично и может наверняка обеспечить себе минимальный проигрыш:

.

Всегда справедливо неравенство:

Величину называют нижней ценой игры .

Величину называют верхней ценой игры .

Оптимальные стратегии и называются чистыми , если для них выполняются равенства:

,

.

Величину называют чистой ценой игры , если .

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

Для седловой точки выполняются условия:

т. е. элемент является наименьшим в строке и наибольшим в столбце.

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

Чистая стратегия игрока I может быть представлена упорядоченным набором чисел (вектором), в котором все числа равны нулю, кроме числа, стоящего на - ом месте, которое равно единице.

Чистая стратегия игрока II может быть представлена упорядоченным набором чисел (вектором), в котором все числа равны нулю, кроме числа, стоящего на - ом месте, которое равно единице.

Пример

.

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

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

Игрок II рассуждает аналогично и выберет в качестве хода 1-ый столбец:

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

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

5.3. Оптимальная смешанная стратегия в матричной игре

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

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

Смешанной стратегией игрока I называют такой упорядоченный набор чисел (вектор), который удовлетворяет двум условиям:

1) для , т. е. вероятность выбора каждой строки платежной матрицы неотрицательна;

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

Смешенной стратегией игрока II будет упорядоченный набор чисел (вектор), удовлетворяющий условиям:

Величина платежа игроку I, выбравшему смешанную стратегию

от игрока II, выбравшему смешанную стратегию

,

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

.

Оптимальными называют смешанные стратегии

и ,

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

т. е. при оптимальной смешанной стратегии выигрыш игрока I наибольший, а проигрыш игрока II наименьший.

Если в платежной матрице нет седловой точки, то

,

т. е. существует положительная разность (нераспределенная разность )

- ³ 0,

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

Пример

Рассмотрим игру , заданную платежной матрицей:

.

Определим, есть ли седловая точка:

, .

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

.

5.4. Отыскание оптимальных смешанных стратегий

для игр 2×2

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

Пусть вероятность выбора игроком I первой строки платежной матрицы

равна . Тогда вероятность выбора второй строки равна .

Пусть вероятность выбора игроком II первого столбца равна . Тогда вероятность выбора второго столбца равно .

Величина платежа игроку I игроком II равна:

Экстремальная величина выигрыша игрока I и проигрыша игрока II соответствует условиям:

;

.

Таким образом, оптимальные смешанные стратегии игроков I и II соответственно равны:

5.5. Геометрическое решение игр 2× n

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

Основные этапы нахождения решения игры сводятся к следующему.

На плоскости введем систему координат. На оси отложим отрезок . Из левого и правого концов этого отрезка проведем перпендикуляры.

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

такими выигрышами игрока I при выборе стратегии будут и , а при выборе стратегии будут и .

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

Находим оптимальную смешанную стратегию игрока I

,

которая соответствует точке на нижней границе выигрыша игрока I с максимальной ординатой.

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

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

,

где вероятность находится так же, как в игре :

5.6. Решение игр m × n

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

Пусть задана платежная матрица размерности :

.

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

Для каждого выбранного хода игроком II выигрыш игрока I определяется зависимостями:

Разделим обе части неравенств на и введем новые обозначения:

Равенство

Примет вид:

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

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

Аналогично строится задача для игрока II как двойственная:

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

Решая задачи симплекс-методом, получаем:

,

5.7. Особенности решения матричных игр

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

Можно ли упростить платежную матрицу;

Имеет ли платежная матрица седловую точку.

Рассмотрим возможность упрощения платежной матрицы:

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

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

Наиболее простым решением игры является наличие в упрощенной платежной матрице седловой точки, которая отвечает следующему условию (по определению):

Пример

Дана платежная матрица:

.

Упрощение платежной матрицы:

Наличие седловой точки:

5.8. Игра с природой

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

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

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

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

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

Пример

Матрица выигрышей:

.

Матрица рисков:

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

Максимизация выигрыша;

Минимизация риска.

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

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

- в условиях неопределенности , когда такая функция распределения вероятностей неизвестна.

5.9. Решение задач теории статистических решений

в условиях риска

При принятии решений в условиях риска игроку I известны вероятности наступления состояний природы.

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

.

При решении этой задачи с матрицей риска получаем такое же решение, соответствующее минимальному среднему риску :

.

5.10. Решение задач теории статистических решений

в условиях неопределенности

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

Максиминным критерием Вальда;

Критерием минимального риска Севиджа;

Критерием пессимизма - оптимизма Гурвица;

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

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

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

.

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

Аналогичный предыдущему подход с позиции крайнего пессимизма для матрицы риска:

.

Рассмотрим критерий пессимизма - оптимизма Гурвица .

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

где степень пессимизма ;

при - крайний оптимизм,

при - крайний пессимизм.

Рассмотрим принцип недостаточного основания Лапласа .

Полагается, что все состояния природы равновероятны:

,

.

Выводы по пятому разделу

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

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

Отыскание оптимальных смешанных стратегий для игр 2×2 производится вычислением оптимальных вероятностей по известным формулам. С помощью геометрического решения игр 2×n определение оптимальных смешанных стратегий в них сводится к отысканию оптимальных смешанных стратегий для игр 2×2. Для решения игр m×n используют метод линейного программирования для нахождения оптимальных смешанных стратегий в них.

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

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

Решение задач теории статистических решений в условиях риска показывает, что игроку I целесообразно выбрать ту стратегию, для которой среднее значение (математическое ожидание) выигрыша, взятое по строке платежной матрицы, максимально, или (что то же самое) среднее значение (математическое ожидание) риска, взятое по строке матрицы рисков, минимально. При принятии решений в условиях неопределенности используют следующие критерии: максиминный критерий Вальда, критерий минимального риска Севиджа, критерий пессимизма-оптимизма Гурвица, принцип недостаточного основания Лапласа.

Вопросы для самопроверки

Как определяются основные понятия теории игр: ход, стратегия и функция выигрыша?

В виде чего представляется в матричной игре функция выигрыша?

Почему матричную игру называют с нулевой суммой?

Как представляется процесс игры в матричную игру?

Какая игра называется игрой m×n?

Какая стратегия матричной игры называется оптимальной?

Какая оптимальная стратегия матричной игры называется чистой?

Что означает седловая точка платежной матрицы?

Какая оптимальная стратегия матричной игры называется смешенной?

Как представляется смешанная стратегия игрока?

Что представляет собой величина платежа игроку I от игрока II, выбравшим смешанные стратегии?

Какие смешанные стратегии называют оптимальными?

Что означает нераспределенная разность?

С помощью какого метода находятся оптимальные смешанные стратегии для игр 2×2?

Каким образом находятся оптимальные смешанные стратегии для игр 2×n?

С помощью какого метода находятся оптимальные смешанные стратегии для игр m×n?

В чем заключаются особенности решения матричных игр?

Что означает упрощение платежной матрицы и при каких условиях оно может быть осуществлено?

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

Какие задачи теории игр относятся к задачам теории статистических решений?

Как платежная матрица преобразуется в матрицу рисков?

Какие две постановки задачи о выборе решений возможны в матричной игре с природой?

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

Какую стратегию целесообразно выбрать игроку I при решении задачи теории статистических решений в условиях риска?

Какими критериями принятия решений можно воспользоваться при решении задач теории статистических решений в условиях неопределенности?

Примеры решения задач

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

Обозначим заданную матрицу через и введем переменные . Будем также использовать матрицу (вектор) . Тогда и , т. е. .

Рассчитывается обратная матрица :

Находятся значения:

.

Рассчитываются вероятности:

Определяется средний доход от реализации:

.

2. Фирма «Фармацевт» - производитель медикаментов и биомедицинских изделий в регионе. Известно, что пик спроса на некоторые лекарственные препараты приходится на летний период (препараты сердечно-сосудистой группы, анальгетики), на другие – на осенний и весенний периоды (антиинфекционные, противокашлевые).

Затраты на 1 усл. ед. продукции за сентябрь-октябрь составили: по первой группе (препараты сердечно-сосудистые и анальгетики) – 20 р.; по второй группе (антиинфекционные, противокашлевые препараты) – 15 р.

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

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

РЕШЕНИЕ. Фирма располагает двумя стратегиями:

В этом году будет теплая погода;

Погода будет холодная.

Если фирма примет стратегию и в действительности будет теплая погода (стратегия природы ), то выпущенная продукция (3050 усл. ед. препаратов первой группы и 1100 усл. ед. второй группы) будет полностью реализована и доход составит

3050×(40-20)+1100×(30-15)=77500 р.

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

1525×(40-20)+1100×(30-15)-20×()=16500 р.

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

1525×(40-20)+3690×(30-15)=85850 р.

При теплой погоде доход составит

1525×(40-20)+1100×(30-15)-() ×15=8150 р.

Рассматривая фирму и погоду в качестве двух игроков, получим платежную матрицу

,

Цена игры лежит в диапазоне

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

Найдем решение игры.

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

Оптимальный план производства лекарственных препаратов составит

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

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

Критерий Вальде:

Критерий Гурвица: для определенности примем , тогда для стратегии фирмы

для стратегии

фирме целесообразно использовать стратегию .

Критерий Сэвиджа. Максимальный элемент в первом столбце – 77500, во втором столбце – 85850.

Элементы матрицы рисков находятся из выражения

,

откуда , ,

Матрица рисков имеет вид

,

целесообразно использовать стратегию или .

Следовательно, фирме целесообразно применять стратегию или .

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

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

Пусть известно для рассматриваемой задачи, что вероятности теплой и холодной погоды равны и составляют 0,5, тогда оптимальная стратегия фирмы определяется так:

Фирме целесообразно использовать стратегию или .

Задания для самостоятельной работы

1. Предприятие может выпускать три вида продукции (А, Б и В), получая при этом прибыль, зависящую от спроса. Спрос в свою очередь может принимать одно из четырех состояний (I, II, III и IV). В следующей матрице элементы характеризуют прибыль, которую получит предприятие при выпуске -ой продукции и -ом состоянии спроса:

Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин.
Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления.
С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок). В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов (по видам и содержащимся в них питательным веществам). Задача о смесях может найти применение и в литейном производстве (состав металлургической шихты). Этим же методом решаются транспортная задача, задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.
Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу - значит выбрать из всех допустимо возможных (альтернативных) вариантов лучший, Оптимальный. Важность и ценность использования в экономике метода линейного программирования состоят в том, что оптимальный вариант выбирается из весьма значительного количества альтернативных вариантов. При помощи других способов решать такие задачи практически невозможно.

В качестве примера рассмотрим решение задачи рациональности использования времени работы производственного оборудования.
В соответствии с оперативным планом участок шлифовки за первую неделю декабря выпустил 500 колец для подшипников типа А, 300 колец для подшипников типа Б и 450 колец для подшипников типа В. Все кольца шлифовались на двух взаимозаменяемых станках разной производительности. Машинное время каждого станка составляет 5000 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении различных колец характеризуется следующими данными (табл. 6.5).
Таблица 6.5
Следует определить оптимальный вариант распределения операций по станкам и время, которое было бы затрачено при этом оптимальном варианте. Задачу выполним симплексным методом.
Для составления математической модели данной задачи введем следующие условные обозначения: jc, х2, хъ, - соответственно количество колец для подшипников типов Л, Б, В, производимых на станке I; х4, х5, х6, - соответственно количество колец для подшипников типов А, Б, В, производимых на станке II.
Линейная форма, отражающая критерий оптимальности, будет иметь вид:
min а(х) = 4x,-f 10x2-f 10x3-f 6x4-f 8х5+20х6 при ограничениях
4х, -f 10х2 -f 10;t3 lt; 5000
6х4 -f 8х5 -f 20х6 ~lt; 5000
х, = 500
х2 +х5 = 300
х3 +х6 = 450
Xj^0,j=l, ..., 6

Преобразуем условие задачи введением дополнительных (вспомогательных) и фиктивных переменных. Условие запишем так:
шіп lt;х(х) = 4дг, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Мх9 + Мх{0+Мх{,
Система уравнений, отражающая ограничительные условия машинного времени и количество произведенной продукции:
4х, + l(bc2 + 10х3 +х1 = 5000
6х4 + 8х5 + 20х6 + xs = 5000
Xj +х4 +х9 = 500
х2 +х5 +х10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Решение этой задачи представлено в табл. 6.6. Оптимальный вариант получен на седьмом этапе (итерации). Если бы на станке I производилось 125 колец подшипников типа А, 450 колец подшипников типа В, на станке II - 375 колец подшипников типа А и 300 колец подшипников типа Б, то при такой загрузке оборудования было бы высвобождено 350 мин машинного времени станка II. Общие затраты времени по оптимальному варианту составили бы 9650 мин, тогда как фактически затрачено 10000 мин машинного времени.
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.
Решение транспортной задачи распределительным методом было дано в третьем издании учебника «Теория экономического анализа» («Финансы и статистика», 1996).

Решение задачи рациональности использования станков симплексным методом

Базис	с	Ро	4	10	10	6	8	20	0	0	м	м	м
			Л	Рг	Ръ	Л	Р ъ		Pi	Р8	р*	Л 0	Л,
Л	0	5000	4	10	0	0	0	0	і	0	0	0	0
Р,	0	5000	0	0	0	6	8	20	0	1	0	0	0
Л	м	500	1	0	0	1	0	0	0	0	1	0	0
Л 0	м	300	ш	0	0	0	1	0	0	0	0	1	0
Л.	м	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250М	М-4	М-10	М-10	М-6	М-8	М-20	0	0	0	0	0
Pi	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
р*	0	5000	0	0	0	6	8	20	1	1	0	0	0
Ро	4	500	1	0	0	1	0	0	0	0	1	0	0
Ло	м	300	0	1	0	0	ш	0	0	0	0	1	0
Л.	м	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750Л/+2000	0	М-10	М-10	-2	М-8	О 2	0	0	-М + 4	0	0

Базис	С	Р0	4	Pi	10	6	8	20	0	0	м	м	М
			Pi	10	^3	л	Р5	р6	Pi	р«	р9	Pi 0	Рц
Pi	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
Р*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
Р5	8	300	0	1	0	0	1	0	0	0	0	1	0
РП	М	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450Л/+4400	0	-2	М-10	-2	0	М-20	0	0	-М+4	-М+8	0
Ръ	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
Р%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
Р5	8	300	0	1	0	0	1	0	0	0	0	1	0
Рц	М	150	0	-1	0	j4_ 10	0	1	_ J_ 10	0	4 10	0	1
zrCj		150Л/+7400	0	-M+S	0	- М-6 10	0	М-20	- ~М+1 10	0	-±м 10	- Af+8"	0

Базис	с	Л,	4	10	10	6	8	20	0	0			М	М	м
			Л	Рг	Л	л	PS	р6	Pi	рamp;			Р9	Ло	л.
Л	10	300	0	1	1	4	0	0	1		0		4	0	0
						“10			То				“ 10
р6	20	130	0	4	0	3	0	1	0		1		0	4	0
				~Ї0		10					20			10
л	4	500	1	0	0	1	0	0	0		0		1	0	0
Ps	8	300	0	1	0	0	1	0	0		0		0	1	0
Р\\	М	20	0	6	0	1	0	0	1		1		4	4	1
				10		~10			То		20		То	10
Zj-Cj		20М+10000	0		0	-м	0	0	м+\		-м+\		--М	-*М	0
				10		10			10	20			10	10
л	10	380	0	14	1	0	0	0	3		2		12	0	0
				10					10		10		10
р%	20	70	0	14	0	0	0	1	3		2		12	16	-3
				10					10		10		10	10
Л	4	300	1	6	0	0	0	0	1		1		-3		-10
											2
р5	8	300	0	1	0	0	1	0	0		0		0	1	0
Р4	6	200	0	-6	0	1	0	0	-1		1		4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1			-М	-М	-м

Базис		Лgt;	4	10	10	6	8	20	0	0	м	м	л/
	о		Л	Рг	ръ	Р*	Р5	Р6	Л	Рamp;	р9	Л 0	л.
Рг	10	450	0	0	1	0	0	1	0	0
Р%	0	350	0	7	0	0	0	5	3 5	1
Л	4	125	1	5 2	0	0	0	5 2	1 4	0
Ps	8	300	0	1	0	0	1	0	0	0
Р4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0

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

Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

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

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

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

· транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

· математические модели большого числа экономических задач линейны относительно искомых переменных;

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

· многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

В общем виде модель записывается следующим образом:

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

F = c1x1 + c2x2 + ... + cnxn → max(min);

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

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,

a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,

am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

требование неотрицательности:

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

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

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

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

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

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

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

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

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными , их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением , если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X 1 , X 2 , ..., X r , то решение {b 1 , b 2 ,..., b r , 0, ..., 0} будет опорным при условии, что b 1 , b 2 ,..., b r ≥ 0 .

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

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

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

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

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

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

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

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

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

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

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

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

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

История

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году .

Задачи

Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида :

при условиях

, .

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

,

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

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

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

Примеры задач

Максимальное паросочетание

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

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

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

Максимальный поток

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

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

,

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

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

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

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

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

Решающими переменными в данном случае являются - количества груза, перевезённого из -го склада на -й завод. Они удовлетворяют ограничениям:

Целевая функция имеет вид: , которую надо минимизировать.

Игра с нулевой суммой

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

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

, , (),

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

Алгоритмы решения

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

Первый полиномиальный алгоритм , метод эллипсоидов , был предложен в 1979 году советским математиком Л. Хачияном , разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки , первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году . Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

См. также

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

Примечания

Литература

• Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс», 2006. - С. 1296. - ISBN 5-8459-0857-4
• Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. - М .: Высшая школа, 1986. - 319 с. - ISBN 5-06-002663-9
• Карманов В. Г. Математическое программирование. - 3-е издание. - М .: Наука, 1986. - 288 с.
• Данциг Джордж Бернард «Воспоминания о начале линейного программирования»

Ссылки

• - Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
• Вершик А. М. «O Л. В. Канторовиче и линейном программировании »
• Большакова И. В., Кураленко М. В. «Линейное программирование. Учебно-методическое пособие к контрольной работе ».
• Барсов А. С. «Что такое линейное программирование », Популярные лекции по математике , Гостехиздат, 1959.
• М. Н. Вялый Линейные неравенства и комбинаторика . - МЦНМО , 2003.

Wikimedia Foundation . 2010 .

• Зальтен, Феликс
• Глагов, Мартина

Смотреть что такое "Линейное программирование" в других словарях:

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

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

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

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

15.1. Аналитические методы

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

Наилучшие в определенном смысле решения задач принято называть оптимальными . Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема. При постановке и решении задач оптимизации возникают два вопроса: что и как оптимизировать?

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

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

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

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

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

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

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

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

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

15.4. Общая задача линейного программирования

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

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

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

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

при условиях-ограничениях: