«В.П. ЧЕРНОВ МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ В ЭКОНОМИКЕ И МЕНЕДЖМЕНТЕ УЧЕБНОЕ ПОСОБИЕ 2 И3ДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ЭКОНОМИКИ И ФИНАНСОВ 2010 ББК 22.161 Ч 47 Чернов В.П. Математические ...»

МИНИСТЕРСТВО ОБРА3ОВАНИЯ И НАУКИ РОССИЙСКОЙ

ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРА3ОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРА3ОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ЭКОНОМИКИ И ФИНАНСОВ»

КАФЕДРА ЭКОНОМИЧЕСКОЙ КИБЕРНЕТИКИ

И ЭКОНОМИКО-МАТЕМАТИЧЕСКИХ МЕТОДОВ

В.П. ЧЕРНОВ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И

МЕТОДЫ

В ЭКОНОМИКЕ И

МЕНЕДЖМЕНТЕ

УЧЕБНОЕ ПОСОБИЕ

И3ДАТЕЛЬСТВО

САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

ЭКОНОМИКИ И ФИНАНСОВ

ББК 22. Ч Чернов В.П.

Математические модели и методы в экономике и менеджменте:

Учебное пособие. – СПб.: Изд-во СПбГУЭФ, 2010. – 235 с.

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

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

Материалы пособия использовались в преподавании магистрантам и слушателям программ МВА Высшей экономической школы Санкт-Петербургского государственного университета экономики и финансов.

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

Рецензенты:

д-р техн. наук, проф. Г.В. Савинов Засл. работник ВШ РФ, д-р экон. наук, проф. Н.Н. Погостинская ISBN 978-5-7310-2584- © Издательство СПбГУЭФ,

ВВЕДЕНИЕ

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

Современные исследования экономических проблем тесно переплелись с математическими расчетами, математическим аппаратом анализа. Они основываются на экономико-математическом моделировании.

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

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

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

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

Раздел 1. Линейные модели планирования Материал раздела направлен на то, чтобы студент умел:

- провести компьютерный расчет и графический анализ безубыточного объема производства в Excel;

- средствами Excel подобрать параметры, выводящие на заданные характеристики безубыточности;

- связать построение производственного плана с прогнозом спроса и доступными ресурсами;

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

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

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

- провести компьютерную оптимизацию плана средствами Excel;

- определить характеристики надежности (устойчивости) оценок плана средствами Excel;

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

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

Анализ безубыточности (Break-even Point Analysis, BEP Analysis) позволяет определить тот объем производства (и продаж), который покрывает издержки, связанные с этим производством. Тем самым определяются необходимые производственные мощности.

В простом и наиболее распространенном варианте анализа все зависимости предполагаются линейными.

Для проведения такого анализа совокупные издержки C (Total Cost) классифицируются на две группы:

постоянные издержки F (Fixed Cost), не зависящие от объема производства, переменные издержки V (Variable Cost), прямо пропорциональные объему производства.

Коэффициентом пропорциональности являются удельные переменные издержки v (переменные издержки в составе единицы продукции). Они называются также маржинальными издержками (Marginal Cost).

Выручка R (Revenue) пропорциональна объему продаж. Коэффициентом пропорциональности является цена p (price) единицы продукции.

Разность M между выручкой и переменными издержками называется маржинальным доходом (Contribution Margin):

Таким образом, если Q – объем производства (и продаж) в натуральных единицах, то Прибыль (Profit) определяется равенством Условие безубыточности (и бесприбыльности) соответствует нулевой прибыли:

Отсюда точка безубыточности BEP (Break-even Point) в натуральной шкале определяется равенством:

Эта формула определяет точку безубыточности BEP, то есть тот объем производства Q* (в натуральных единицах), который покрывает совокупные затраты.

Точку безубыточности BEP можно выразить и в рублях. Для этого следует умножить обе части последнего равенства на цену p. После простых преобразований получим:

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

Точку безубыточности BEP можно выразить и в процентах. Для этого разделим обе части последнего равенства на объем выручки R.

Получим:

Формула показывает, каков должен быть объем производства в процентах от выручки, чтобы полностью покрыть все затраты. Критическим значением здесь является 100%. Если то производство безубыточно, но и бесприбыльно. Если то предприятие производит и продает достаточный объем продукции, покрывает все издержки и получает прибыль. Если же то предприятие терпит убытки.

Например, если BEP(%) = 70%, то уже 70% объема производства достаточно для покрытия соответствующих затрат, связанных с этим объемом производства. Если же BEP(%) = 120%, то объем производства должен быть увеличен на 20%, чтобы достичь уровня безубыточности.

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

Требуется дать ответ на следующие вопросы.

1. Определите удельные переменные (маржинальные) затраты для каждого вида оборудования.

2. При каком объеме производства два вида оборудования оказываются равновыгодными?

3. Какой вид оборудования выгоднее и насколько при годовой производственной программе 1500 изделий?

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

5. Какая отпускная цена обеспечит при этом расчетную прибыль в 6. Для условий предыдущего пункта определите точку безубыточности в трех шкалах: BEP(нат.), BEP(руб.) и BEP(%).

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

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

9. Изобразите графики зависимости затрат и выручки от объема выпуска для обоих видов оборудования.

Исходные данные по видам оборудования Затраты на наладку и эксплуатацию 16000 (руб. / год) Пример 1.1. Компьютерный анализ безубыточности На схеме 1.1 представлены выполненные в Excel таблицы и графики по анализу безубыточности. Схема сверху вниз состоит из трех блоков. Верхний блок разделен на две части: левую и правую.

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

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

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

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

Основой среднего блока на этой схеме является последовательность не объемов, а процента продаж. Процент продаж отмечен и по оси абсцисс на графике.

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

Эта схема тоже автоматически пересчитывается при любом изменении исходных данных.

На рис. 1.3 проведены расчеты по сравнению двух видов оборудования по данным задания 1.1.

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

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

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

Определите в Excel в соответствии с рис. 1.1 с помощью процедуры «Подбор параметра»:

1. Объем продаж Q, при котором прибыль равна 0 и равна 2. Цену p, при которой прибыль равна 0 и равна 200000 руб.

3. Маржинальные затраты v, при которых прибыль равна 0 и 4. Постоянные затраты F, при которых прибыль равна 0 и равна Определите в Excel в соответствии с рис. 1.2 с помощью процедуры «Подбор параметра»:

5. Объем выручки R, при котором прибыль равна 0 и равна 6. Объем совокупных затрат C, при котором прибыль равна 0 и 7. Отдельно объем выручки R, размер общих затрат С и величину доли постоянных затрат, при которых безубыточный объем продаж равен 1800 руб.

A B C D E F

Удельные переменные затраты (на 27 1 500 000р.

31 500 000р.

Рис. 1.1. Расчет безубыточности по четырем характеристикам:

Объему продаж, Цене, Удельным переменным затратам,

A B C D E F

20 5 000р.

24 3 500р.

25 3 000р.

27 2 500р.

28 2 000р.

31 1 000р.

Рис. 1.2. Расчет безубыточности по трем характеристикам:

Выручке, Общим затратам и Доле постоянных затрат

A B C D E F G H I J K L M

9 Таблица соответствия продаж, затрат, выручки и прибыли Таблица соответствия продаж, затрат, выручки и прибыли 29 35 000р.

38 15 000р.

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

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

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

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

(Планирование и Анализ Рационального Использования Средств) Петербургская фирма «Сфера» занимается производством кондитерских изделий: различных сортов печенья, бисквитов, кексов и др.

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

Спрос на продукцию фирмы подвержен сезонным колебаниям.

Наибольшее падение спроса наблюдается летом. Подъемы спроса заметны в праздничные периоды (Новый год, 8 марта, 1 сентября…).

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

Необходимые характеристики для анализа условий работы фирмы «Сфера» по производству двух основных продуктов – песочного печенья (Печенье) и бисквитных изделий (Бисквиты) представлены в табличной форме (табл. 1.2–1.6).

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

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

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

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

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

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

Производственный план для фирмы «Сфера» должен быть представлен двумя числами, соответствующими объемам выпуска двух видов продукции: Печенья и Бисквитов.

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

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

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

Построим математическую модель задачи. Составление модели начинается с введения переменных. Переменные являются элементами языка, на котором будет сформирован производственный план. Такой план в данном случае – это пара величин, соответствующих объемам производства (количеству килограммов) продукции одного и другого вида. Обозначим посредством x1 объем производства Печенья, посредством x2 – объем производства Бисквитов. Следует найти наилучший (оптимальный) производственный план.

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

Это неравенство показывает, что суммарные расходы муки на Печенье в количестве x1 кг и на Бисквиты в количестве x2 кг (левая часть неравенства) не должны превосходить доступные запасы Муки (правая часть неравенства). Аналогичные неравенства можно написать для Масла, Яйца и Сахара:

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

Ограниченность производственных мощностей может быть выражена в форме неравенств:

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

Такая система неравенств образует систему ограничений задачи.

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

Например, план (500; 1000), согласно которому нужно изготовить 500 кг Печенья и 1000 кг Бисквитов, – это допустимый план. Чтобы проверить его допустимость, достаточно подставить значения x1 = и x2 = 1000 в систему ограничений и убедиться, что каждое из неравенств выполнено. Разумеется, допустимым будет и всякий план с меньшими неотрицательными объемами производства, так что допустимых планов в нашей модели бесконечно много.

С другой стороны, рассмотрим план (1000; 1000), в котором объем производства Печенья удвоен, а объем производства Бисквитов оставлен прежним. Этот план – недопустимый. Он не удовлетворяет третьему и четвертому неравенствам системы. Для его выполнения требуется 780 кг яйца и 500 кг сахара, что превышает допустимые значения. И хотя этот план удовлетворяет другим неравенствам, остальных ресурсов хватает, все же выполнить этот план в тех условиях, которые указаны в задаче, не удастся. Конечно, недопустимым будет и всякий план с большими объемами производства продукции. Недопустимых планов бесконечно много.

Сосредоточим внимание на допустимых планах. Каждому из них соответствует свой размер выручки. Например, для плана (500; 1000) выручка составит:

В общем случае формулу для определения выручки z можно представить в следующем виде:

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

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

при условиях:

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

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

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

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

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

Пронумеруем все виды ресурсов числами от 1 до m, буквой i будем обозначать номер вида ресурса. Таким образом, i удовлетворяет неравенству 1 i m. Заметим, что ресурсы разных видов могут измеряться в различных единицах (тоннах, кубометрах, человеко-часах, рублях, штуках и др.).

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

Из этих ресурсов предприятие способно изготавливать различную продукцию (в нашей ситуации – Печенье и Бисквиты). Обозначим буквой n общее число видов продукции, которые может выпустить предприятие из имеющихся ресурсов. Занумеруем все виды продукции числами от 1 до n. Буквой j будем обозначать номер вида продукции, так что выполняется неравенство 1 j n. Продукция, как и ресурсы, может измеряться в различных единицах.

Пусть cj – цена, по которой предприятие реализует каждую единицу продукции j-го вида. Индекс j около буквы c указывает, что цена разных видов продукции может быть различной.

Производство продукции требует затрат ресурсов. Объем затрат зависит от вида ресурса, вида продукции и количества единиц продукции. Обозначим посредством aij норму затрат ресурса i-го вида на производство продукции j-го вида. Другими словами, aij – это количество ресурса i-го вида, затрачиваемое при производстве единицы продукции j-го вида.

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

Построим математическую модель задачи. Сначала введем переменные. Посредством xj обозначим искомый объем выпуска продукции j-го вида. Математическую модель можно теперь записать в следующей форме:

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

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

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

Рассмотрим, например, первое неравенство. В правой его части указана величина b1, общий объем запаса ресурса первого вида. В левой его части находятся величины aij с одним и тем же первым индексом i=1 и различными вторыми индексами. Каждая такая величина a1j указывает количество ресурса одного и того же первого вида, затрачиваемого на производство одной единицы продукции j-го вида. Величина aij умножается на объем xj произведенной продукции j-го вида. Такое произведение показывает затраты ресурса первого вида на производство всего количества произведенной продукции j-го вида. Затем все эти затраты ресурса суммируются по всем видам продукции. Таким образом, в левой части первого неравенства – суммарные затраты первого вида ресурса на производство всех видов продукции в соответствующих объемах. В правой части неравенства – общее количество первого вида ресурса, имеющееся в наличии. Само неравенство требует, чтобы расходуемый объем первого ресурса был не больше объема запаса этого ресурса. Аналогичный смысл имеют другие неравенства системы ограничений. Каждое из них относится к своему виду ресурса.

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

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

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

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

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

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

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

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

Например, недельный спрос на каждый вид продукции фирмы «Сфера» (Печенье и Бисквиты) ограничен величиной 3000 кг. К уже построенной математической модели следует добавить два неравенства:

как это и было сделано выше.

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

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

Рассмотрим теперь ситуацию, когда вся выпускаемая продукция или ее часть реализуется комплектами. Предположим, что в комплект входит kj единиц продукции j-го вида (если какая-то продукция в комплект не входит, то соответствующее kj равно 0). Пусть цена комплекта равна h. Построим модель для определения оптимального производственного плана в этих условиях.

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

.....................................................

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

Таким образом, следует рассчитать не только объемы производимой продукции, но и объемы приобретаемых ресурсов, которые будут вовлечены в производственный процесс. Обозначим эту неизвестную пока величину дополнительного объема i-го ресурса посредством ui.

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

Модель в результате этих изменений примет следующий вид:

.....................................................

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

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

Результаты деятельности предприятия (доходы, материальные запасы) в одних периодах времени влияют на условия деятельности в других, последующих периодах. Дополнительные ограничения, сцепляющие друг с другом модели разных периодов, как раз и выражают такие связи между результатами, полученными в одних периодах, и условиями деятельности – в других.

Мы рассмотрели основную, базовую модель оптимального использования ресурсов и различные ее модификации. Эти модификации могут объединяться и использоваться совместно. Разумеется, существуют и другие, не рассмотренные здесь условия и ситуации построения производственного плана. Они также могут быть промоделированы аналогичным образом.

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

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

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

Дадим необходимые определения.

Функция n переменных x1, x2,... xn называется линейной функцией, если она представима в виде линейной комбинации переменных, то есть в виде суммы переменных с постоянными коэффициентами Иногда линейной называют также функцию вида отличающуюся от предыдущей постоянным слагаемым d.

Равенство а также неравенства называются линейным равенством и линейными неравенствами, если функция является линейной.

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

Функция, экстремальное значение которой требуется отыскать, называется целевой функцией. Система равенств и неравенств называется системой ограничений.

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

Значение целевой функции на оптимальном плане называется оптимумом.

Решить задачу линейного программирования – значит найти ее оптимальный план и оптимум.

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

Как обычно, посредством A обозначим матрицу системы ограничений:

Посредством X и B обозначим соответственно столбец неизвестных задачи (план задачи) и столбец свободных членов (правых частей системы ограничений):

Наконец, посредством C обозначим вектор-строку коэффициентов целевой функции:

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

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

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

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

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

Множество решений этого уравнения соответствует прямой на координатной плоскости. Чтобы изобразить прямую, достаточно найти две ее точки. Найдем точки на осях координат. Для этого положим в уравнении x2 = 0. Получим x1 = 1650. Изобразим соответствующую точку на оси 0x1 (точка А1 на рис. 1.4). Теперь положим в уравнении x = 0. Получим x2 = 2750. Изобразим соответствующую точку А2 на оси 0x2.

Соединим точки А1 и А2 прямой линией. Мы получили граничную прямую искомой полуплоскости.

Эта прямая делит координатную плоскость на две полуплоскости.

Для определения полуплоскости, соответствующей множеству решений неравенства, выберем точку, не лежащую на граничной прямой (например, начало координат), и подставим ее координаты в наше неравенство. Получим 0 825. Неравенство верное. Следовательно, искомой полуплоскостью является та, которая содержит начало координат и, тем самым, лежит слева от граничной прямой.

Если бы мы вместо начала координат взяли, например, точку с координатами (2000; 0), лежащую правее и выше нашей прямой, и подставили бы ее координаты в левую часть неравенства, то получили бы 1000 825. Неравенство неверно, следовательно, выбранная точка не принадлежит искомой полуплоскости. Искомой оказывается все та же левая полуплоскость.

Теперь найдем полуплоскость, соответствующую второму неравенству системы ограничений. Ее граничная прямая проходит через точку В1 с координатами (1600; 0), лежащую на оси 0x1, и через точку с координатами (0; 8000) на оси 0x2. Для удобства изображения заменим вторую точку другой точкой, лежащей на той же прямой.

Для этого положим x2 = 3000. Тогда из уравнения прямой получаем x1 = (480 – 0,06*3000) / 0,3 = 1000. В качестве B2 возьмем точку с координатами (1000, 3000). Соединим прямой линией точки В1 и B (рис. 1.5).

Рис. 1.5. Граничные прямые по ресурсам Мука и Масло Из двух возможных полуплоскостей опять следует выбрать ту, которая содержит начало координат.

Аналогично строятся границы по остальным ресурсам (рис. 1.6). Границе по Яйцу соответствует прямая C1C2, границе по Сахару – прямая D1D2, границе по Труду – прямая E1E2, по Оборудованию 1 – прямая F1F2, по Оборудованию 2 – прямая G1G2. Каждый раз следует выбрать ту полуплоскость, которая содержит начало координат.

Условия ограниченности недельного спроса (x1, x2 ограничены величиной 3000) определяют горизонтальную и вертикальную границы чертежа. Неотрицательность переменных x1 и x2 соответствует первой координатной четверти. Таким образом, четыре стороны квадрата соответствуют ограничениям модели.

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

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

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

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

Точки, удовлетворяющие всем ограничениям, – это точки нашего шестиугольника. Его границы соответствуют сырьевым ресурсам.

Линии Труда и Оборудования 1 и 2 (прямые E1E2, F1F2, G1G2) оказываются в стороне. Это означает, что при реализации любого допустимого плана данной задачи трудовые ресурсы и производственные мощности не будут, по существу, ограничивать наши возможности, так как они в более жесткой форме ограничены запасами сырья. Следовательно, если у нас появится возможность изменить доступные объемы ресурсов, то ее следует направить в первую очередь на изменение запасов сырья.

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

Во-первых, область допустимых планов непуста и ограничена.

Следовательно, оптимальный план существует.

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

и определение оптимального плана Обратимся к целевой функции. Ее градиент есть вектор (32; 27).

Для решения задачи следует изобразить этот вектор в виде стрелки с началом в точке (0; 0) и концом в точке (32; 27).

Такая стрелка является короткой и поэтому плохо различимой на чертеже. Однако длина этой стрелки не играет никакой роли при решении задачи. Важно лишь ее направление. Если обе координаты точки (32; 27) умножить или разделить на одно и то же положительное число, то изменится лишь длина стрелки, но не ее направление. Поэтому на результате решения задачи это не скажется.

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

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

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

В своем крайнем положении линия уровня проходит через точку L.

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

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

Рис. 1.8. Построение оптимального плана Составляем систему уравнений:

Решив эту систему, получаем компоненты оптимального плана: x = 1250 и x2 = 667. Таким образом, оптимальный план X*max равен:

Он предписывает выпустить 1250 кг Печенья и 667 (точнее, 666,667) кг Бисквитов.

Для определения оптимума следует подставить компоненты оптимального плана в целевую функцию задачи. Оптимум Z*max определяется равенством:

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

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

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

Задание 1.3. Модификации графического анализа Предположим, что спрос на печенье ограничен и составляет кг за плановый период.

1. Введите это условие в математическую модель задачи.

2. Изобразите это условие на чертеже.

3. Определите новый оптимальный план и оптимум.

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

4. Введите это условие в математическую модель задачи.

5. Изобразите это условие на чертеже.

6. Определите новый оптимальный план и оптимум.

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

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

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

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

Для задачи производственного планирования ограничения соответствуют ресурсам. Равенство левой и правой частей ограничения, его активность означает полное использование данного ресурса. Строгое неравенство – неполное использование ресурса.

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

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

Предположим, что доступный объем Муки незначительно увеличился с 825 кг до 825 + (например, на 1 кг, так что = 1). Это соответствует небольшому сдвигу прямой A1A2 на рис. 1.8 вправо. Область допустимых планов расширилась, производственные условия стали свободнее, и это может привести разве лишь к увеличению выручки.

Оптимальный план, оставаясь на пересечении тех же границ по Муке и Сахару (линий A1A2 и D1D2) сместится по прямой D1D2 направо-вниз.

Это соответствует увеличению производства Печенья (смещение направо) при одновременном уменьшении производства Бисквитов (смещение вниз). В результате несложных расчетов получим новый план, предписывающий производить больше Печенья на 3,333 кг и меньше Бисквитов на 2,222 кг. Дополнительная выручка при этом равна 46,67 руб.

Таким образом, если запас Муки изменится на величину, то выручка изменится на величину 46,67 руб. Дополнительная единица ресурса позволяет увеличить выручку на 46,67 руб. Эта величина 46, руб. и есть теневая цена Муки.

Аналогичный расчет показывает, что теневая цена Сахара составляет 43,33 руб. Теневые цены всех остальных ресурсов равны 0. Действительно, остальные ресурсы в нашей ситуации избыточны, так что их приращение не вызовет изменение оптимального плана и оптимума.

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

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

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

Критические границы и допустимые изменения ресурса Если в нашем примере постепенно увеличивать запас Муки, то оптимальный план будет смещаться, оставаясь на пересечении границ по Муке и Сахару (по линии D1D2 на рис. 1.8). Так будет продолжаться до тех пор, пока он не дойдет до точки N – точки пересечения границ по Сахару и Маслу (линий D1D2 и B1B2). В точке N пересекутся три границы: по Муке, Маслу и Сахару.

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

На рис. 1.9 укрупненно представлен фрагмент рис. 1.8 (изменены шкалы значений по горизонтальной и вертикальной оси, но сохранены обозначения A1A2, B1B2 …, соответствующие ресурсам). Смещенная линия A1A2 по ресурсу Мука, в своем верхнем критическом положении изображена штрих-пунктирной линией, проходящей через точку N.

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

Для этого следует решить соответствующую систему уравнений В результате получим Подставим эти значения в левую часть неравенства, определяющего ограничение по Муке:

Полученная величина 900 и является верхней критической границей по ресурсу Мука. Таким образом, исходный объем Муки, равный 825 кг, можно увеличить на 75 кг без изменения статуса ограничений и без изменения теневой цены ресурса. Величина 75 кг в этом примере является допустимым увеличением Муки.

Нижняя критическая граница и, соответственно, допустимое уменьшение вычисляются аналогично. В нашем примере при уменьшении объема Муки оптимальный план будет смещаться налево-вверх по границе Сахара (линия D1D2 на рис. 1.9). Критическим будет такая величина объема ресурса Мука, при которой линия Муки пройдет через точку пересечения K границ по Сахару и Яйцу (линии C1C2 и D1D2).

Это нижнее критическое положение границы изображено рис. 1. штрих-пунктирной линией, проходящей через точку K.

При дальнейшем уменьшении доступного объема Муки произойдет изменение статуса некоторых ограничений. Именно, связанными ресурсами станут Мука и Яйцо, а Сахар станет несвязанным, и его теневая цена будет равна 0.

Для вычисления координат точки K решим соответствующую систему уравнений:

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

Величина 695,455 есть нижняя критическая граница ресурса Мука.

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

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

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

Критические границы ресурсов соответствуют границам устойчивости статуса ограничений при изменении их правых частей.

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

Обратимся к нашему примеру. Цена Печенья составляет 32 руб.

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

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

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

Критическая величина цены, при которой происходит переход оптимального плана из одной точки в другую, соответствует положению, когда линия уровня целевой функции параллельна прямой А1А2 (а градиент, соответственно, перпендикулярен этой прямой). Условием параллельности прямых является пропорциональность коэффициентов при переменных в двух уравнениях: линии уровня целевой функции и границы по Муке. Составим пропорцию с неизвестной ценой c1 первого продукта (Печенья):

Отсюда получаем c1 = 45. Таким образом, при увеличении цены Печенья с первоначальных 32 до 45 руб. за кг (и при сохранении цены Бисквитов) оптимальный план остается неизменным, по-прежнему следует производить 1250 кг Печенья и 666,667 кг Бисквитов. Если же цена поднимется выше 45 руб., то оптимальным планом станет точка M, находящаяся на пересечении границ по Муке и Маслу (линий A1A2 и B1B2). Ее координаты можно определить решением системы уравнений:

откуда x1 = 1575, x2 = 125.

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

Так, план L соответствует выручке:

План M соответствует той же величине выручки:

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

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

решив которую получим c1 = 18.

Мы получили нижнюю критическую границу цены Печенья, равную 18 руб. Допустимое уменьшение первоначальной цены Печенья, равной 32 руб., составляет 14 руб.

Таким образом, при произвольных изменениях цены Печенья между нижней и верхней критическими границами, то есть между 18 и 45 руб., оптимальный план остается прежним: по-прежнему следует производить 1250 кг Печенья и 666,667 кг Бисквитов. При выходе цены за верхнюю или нижнюю критические границы оптимальный план изменится, вместе с ним изменится и статус ресурсов.

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

Расчеты показывают, что верхняя критическая граница цены Бисквитов равна 48 руб., так что допустимое увеличение составляет 21 руб.

При преодолении этой границы оптимальный план переходит из точки L в точку K.

Нижняя критическая граница цены Бисквитов равна 19,20 руб., допустимое уменьшение составляет 7,80 руб. При переходе через эту границу оптимальный план переходит из точки L в точку M.

Критические границы цен соответствуют границам устойчивости оптимального плана при изменении коэффициентов целевой функции.

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

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

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

В последовательности преобразований модели выделяют этапы.

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

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

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

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

Приведем ее к канонической форме. Получим:

Новые переменные x3, … x9 имеют смысл неиспользованных объемов ресурсов. Переменные x10, и x11 – объемы неудовлетворенного спроса. Каждая такая переменная присутствует лишь в одном ограничении, причем коэффициент при ней равен 1.

Такой набор переменных, где в каждом ограничении присутствует ровно одна переменная из набора и каждая переменная из набора присутствует ровно в одном ограничении, причем с коэффициентом 1, называется базисным набором переменных. Переменные, входящие в этот набор, называются базисными переменными. Остальные переменные задачи называются небазисными. В нашем случае базисные переменные – это x3, … x11. Небазисные переменные – это x1, x2.

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

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

В нашем примере текущий опорный план имеет следующие компоненты:

x1 = 0, x2 = 0, x3 = 825, x4 = 480, x5 = 720, x6 = 450, x7 = 200, x8 = 40 x = 40, x10 = 3000, x11 = 3000.

В векторной записи это 11-мерный вектор X0:

X0 =(0; 0; 825; 480; 720; 450; 200; 40; 40; 3000; 3000).

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

Очевидно, план X0 является допустимым, он удовлетворяет всем ограничениям системы. Чтобы получить его образ в системе координат с переменными x1, x2, достаточно изобразить точку, определяемую его первыми двумя компонентами. Плану X0 соответствует точка (0; 0), начало координат, одна из вершин области допустимых планов.

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

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

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

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

На основе этого ограничения устанавливается критерий (признак) оптимальности текущего опорного плана. Это ограничение часто называют критериальным.

Рассмотрим значение целевой функции z на опорном плане X0. Для этого подставим значение компонент плана X0 в критериальное (m + 1) -е ограничение. Получим z0 = 0. Является ли это значение максимально возможным? Другими словами, мешает ли что-нибудь увеличению значения z?

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

Заметим сразу, что если бы все переменные xj, входили бы в критериальное ограничение с неотрицательными коэффициентами, то увеличить значение z было бы невозможно. Это означает, что текущий опорный план был бы оптимальным. Тем самым мы получили критерий оптимальности текущего опорного плана.

Рассмотрим увеличение значения z и одновременное компенсирующее увеличение значения одной из переменных, например, x1.

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

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

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

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

В первое равенство x1 входит с коэффициентом 0,5. Коэффициент положителен. Для того чтобы выполнялось первое равенство, рост x должен компенсироваться уменьшением других переменных. Но значение переменной x2 и так равно 0. Отрицательными значения переменных быть не могут.

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

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

Первое ограничение дает возможность роста переменной x1 до величины 1650. Другими словами, доступные объемы первого ресурса (Муки) позволяют, при наличии достаточных объемов других ресурсов, произвести 1650 кг первого продукта (Печенья).

Отметим, что если бы коэффициент при x1 был отрицателен или равен 0, то такое равенство не формировало бы ограничение на рост значений переменной x1.

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

Рассуждая аналогичным образом, получим новую верхнюю границу роста значений переменной x1:

Остальные ограничения дают следующие границы роста переменной x1:

x1 = 4000; x1 = 2250; x1 = 2858; x1 = 2667 x1 = 5333; x1 = 3000, x1 =.

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

min{1650; 1600; 4000; 2250; 2858; 2667; 5333; 3000} = 1600.

Значение переменной x1 может быть поднято до величины 1600.

Из критериального ограничения следует, что значение целевой функции z при этом вырастает от 0 до 51200.

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

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

Мы анализировали возможности роста переменной x1. Столбец коэффициентов при этой переменной в процессе преобразований называется разрешающим столбцом. Этот столбец представлен ниже.

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

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

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

Для этого сначала разрешающая строка (разрешающее равенство) делится на разрешающий элемент. В нашем случае вторая строка делится на 0,3.

Мы не будем здесь и в дальнейшем дописывать неравенства, требующие неотрицательности переменных xj. Эти требования будут постоянно подразумеваться.

Первое преобразование системы ограничений Приступим к преобразованию системы ограничений методом Гаусса. Разделим вторую строку на 0,3. Получим:

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

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

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

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

В новой записи переменные x1, x3, x5, … x11 являются базисными, x2 и x4 – небазисными. В наборе базисных переменных произошло изменение: переменная x4 вышла из этого набора, а переменная x1 вошла вместо нее в набор.

Преобразованной системе ограничений соответствует новый текущий опорный план X1:

X1 = (1600; 0; 25; 0; 432; 130; 88; 16; 28; 1400; 3000).

Этому плану соответствует новое значение целевой функции Если обратиться к графикам, то план X1 соответствует вершине B1.

При переходе от X0 к X1 мы перешли от вершины О (начала координат) к соседней вершине B1. Этой вершине соответствует производственный план, предписывающий произвести 1600 кг первого продукта (Печенья) и 0 кг второго (Бисквитов). При этом выручка, значение целевой функции, равно 51200, то есть равно z1. Значения переменных x3, … x в плане X1 соответствуют остаткам ресурсов или неудовлетворенному спросу.

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

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

min{125; 8000; 766; 500; 1158; 5333; 2074; 3000} = 125.

Наименьшим является первое отношение. Следовательно, первая строка становится разрешающей строкой, а число 0,2 – разрешающим элементом.

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

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

Новым текущим опорным планом будет X2, X2 = (125; 1575; 0; 0; 362; 98; 79; 16; 26; 1425; 2875), предписывающий изготовление 125 кг Печенья и 1575 кг Бисквитов и соответствующий точке M на чертеже (рис. 1.8). Остальные компоненты плана соответствуют неиспользованным объемам ресурсов и неудовлетворенному спросу.

Реализация этого плана принесет выручку 53775 руб. При этом в критериальной строке присутствует отрицательный коэффициент (при переменной x4), так что выручка не максимальна и план не оптимален.

Преобразование системы ограничений методом Гаусса приводит к изменению набора базисных переменных (из него выйдет переменная x6 и войдет переменная x4). Новым опорным планом станет X3:

X3 = (667; 1250; 0; 95; 65; 0; 53; 17; 21; 1750; 2333).

Этот план является оптимальным, поскольку в критериальной строке отсутствуют отрицательные элементы. Он предписывает изготовление 667 кг Печенья и 1250 кг Бисквитов. План соответствует точке L на чертеже (рис. 1.8). При этом полностью используется Мука и Сахар, остаются недоиспользованными Масло и Яйцо, а также трудовые ресурсы, производственные мощности. Неудовлетворенный спрос составляет 1750 кг по Печенью и 2333 кг по Бисквитам.

Выручка при этом составит 58000 руб. Это максимальная выручка, доступная в нашей ситуации.

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

В левой части такой таблицы имеются три столбца. Столбец «№»

содержит номера строк таблицы. Столбец «Xб» содержит список базисных переменных в соответствии со строками. Столбец «Сб» содержит список коэффициентов, с которыми базисные переменные входят в целевую функцию.

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

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

Строки таблицы соответствуют ограничениям задачи. Критериальная строка имеет номер m+1. Приведенные нами преобразования системы ограничений методом Гаусса сводятся к преобразованию таблиц этим же методом. Последовательно возникающие системы ограничений соответствуют последовательным таблицам. В нашем примере это таблицы 1.7–1.10. Отмечен разрешающий элемент, играющий ключевую роль в процессе преобразований.

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

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

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

Симплексная таблица для такой задачи – это таблица, заполненная следующим образом (табл. 1.11).

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

Дальнейшая часть таблицы, кроме критериальной строки, заполнена той числовой информацией, которая непосредственно представлена в математической модели. А именно: в столбце «В» указаны свободные члены ограничений, а в столбцах «x1».... «xn» – коэффициенты при переменных в системе ограничений. Над обозначением переменной «x1».... «xn» указаны соответствующие коэффициенты, с которыми эти переменные входят в целевую функцию.

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

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

Это полностью соответствует заполнению симплексной таблицы в рассмотренном примере.

Столбцы таблицы, соответствующие базисным переменным (базисные столбцы таблицы), имеют характерную особенность. В таком столбце присутствует ровно одна 1, на остальных местах в столбце стоят 0. Единица находится именно в той строке, в которой в столбце «Хб»

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

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

Текущее значение целевой функции равно d (элементу на пересечении критериальной строки и столбца «В»).

Критерий оптимальности текущего опорного плана Для выяснения вопроса об оптимальности текущего опорного плана следует рассмотреть величины j, находящиеся в критериальной строке. Если окажется, что все, j 0 ( j 1, n), то текущий опорный план является оптимальным планом, а текущее значение целевой функции является оптимумом. В этом случае задача решена.

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

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

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

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

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

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

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

Отметим, что переменная xq, является небазисной. Если бы она была базисной, то q было бы равно 0.

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

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

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

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

Процесс решения задачи на этом заканчивается.

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

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

Преобразование левой части таблицы В таблице ее левая и правая часть преобразуются по отдельным правилам. В левую часть входят первые три столбца таблицы. В правую часть входят все остальные столбцы (начиная со столбца «В»).

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

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

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

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

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

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

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

Тогда для разрешающей строки Для произвольной i-й строки, кроме разрешающей (i р) и критериальной, выполняются равенства Для критериальной строки Легко проверить, что в соответствии с этими формулами элементы разрешающего столбца преобразуются в элементы базисного столбца:

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

В текущем опорном плане небазисные компоненты равны 0, тем самым они неотрицательны. Базисные компоненты равны элементам столбца «В» во всех строках, кроме критериальной. Они тоже должны быть неотрицательными.

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

Действительно, для разрешающей строки выполняется равенство По условию bp 0. Поскольку apq – разрешающий элемент, то apq 0. Отсюда следует, что bp 0.

Для остальных строк таблицы По условию bi 0. Только что было доказано, что bp 0. Если aiq 0, то из формулы сразу следует, что bi 0.

Рассмотрим противоположный случай, когда aiq 0. Доказываемое утверждение bi 0 равносильно неравенству которое, в свою очередь, равносильно то есть Поскольку по предположению aiq 0, то можно разделить обе части последнего неравенства на эту величину, сохранив его смысл:

Последнее неравенство верно. Его справедливость следует непосредственно из правила выбора разрешающего элемента по наименьшему отношению.

Таким образом, мы доказали, что при преобразовании симплексной таблицы элементы столбца «В» во всех строках, кроме критериальной, остаются неотрицательными (хотя сами их численные значения, конечно, изменяются).

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

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

Заметим, что обычно элементы столбца «В» (кроме, возможно, критериального) не просто неотрицательны, а строго положительны.

Случай, когда такой элемент равен 0, возможен, но встречается достаточно редко.

Новой симплексной таблице соответствует новый текущий опорный план. Этому плану соответствует новое значение целевой функции. Оно вычисляется по формуле:

Как мы выяснили ранее, bp 0. Кроме того, по определению разрешающего столбца имеем:

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

Обычно bp 0. Случай, когда bp = 0, встречается крайне редко.

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

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

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

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

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

Процесс решения задачи на этом заканчивается.

Последовательность преобразований таблиц и сопровождающих их рассуждений образует алгоритм симплекс-метода. Он может быть представлен в виде блок-схемы (рис. 1.10).

Предварительная подготовка модели Заполнение исходной симплексной таблицы Выполнен ли да Задача решена.

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

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

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

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

Обоснование сходимости основано на следующем рассуждении.

Каждой симплексной таблице соответствует свой базисный набор переменных. В задаче участвует конечное число (n) переменных. В базисном наборе участвует конечное число (m) этих же переменных.

Следовательно, количество всевозможных базисных наборов конечно.

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

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

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

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

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