Утверждено

Учёным советом

экономического факультета

5 мая 1998 г., пр. № 3

Модель В. Леонтьева. Линейное программирование

Учебно- методическое пособие по дисциплине “Математическое моделирование в экономике” для для студентов III курса очной и заочной форм обучения

(специальность — 060800 Экономика и управление на предприятии СКС)

Санкт-Петербург

1999

Кафедра высшей математики

Автор

доцент кафедры высшей математики, кандидат физико-математических наук
А. М. Махов

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

Рецензенты:

профессор кафедры экономики и управления на предприятии Санкт-Петербургского
государственного университета водных коммуникаций, доктор экономических наук
Н. М. Громова;

заведующий лабораторией вычислительных систем и проблем защиты информации Санкт-Петербургского института информатики и автоматизации Российской академии наук, профессор кафедры информатики Российского государственного педагогического университета им. А. И. Герцена, доктор технических наук В. И. Воробьев

 Введение

     Согласно программе дисциплины “Математическое моделирование в экономике” студенты должны выполнить индивидуальное домашнее задание [1]. Оно состоит из двух частей: расчёта баланса в модели Леонтьева и решения оптимизационной задачи линейного программирования. Настоящее учебно- методическое пособие, таким образом, состоит из двух частей, в каждой из которых даются краткие теоретические сведения из соответствующих заданиям экономических приложений теории исследования операций, приводятся примеры решения подобных задач и излагаются рекомендации по использованию стандартного офисного компьютерного обеспечения в их решении. При выполнении задания могут быть полезны также [2-11].

I. Модель “затраты- выпуск” (модель В. Леонтьева)

I.1. Краткие теоретические сведения

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

Первое условие применения открытой линейной балансовой модели - моделируемый экономический объект состоит из нескольких (n штук) взаимосвязанных процессов (отраслей), то- есть имеет структуру. В каждом из процессов (с номером i) получается некоторый продукт (полный объём продукта - x_i), часть которого расходуется в этом же и некоторых других процессах. Оставшиеся после этого объёмы продуктов (конечные объёмы продуктов или объёмы конечного потребления y_i) являются конечными, выходными результатами для всей модели. Свойство наличия баланса состоит как раз в том, что полные объёмы всей продукции складываются только из объёмов её конечного потребления и объёмов потребления продукции в производственных процессах (межотраслевых потоков). Примером такой взаимосвязи в социально- культурной сфере может служить, например, предоставление услуг по рекламе новых фильмов рекламной отраслью кино- видео индустрии, и наоборот, выполнение кино- видео индустрией  заказов рекламных агентств. При этом у обеих этих отраслей имеются значительные сторонние заказы, т.е. объёмы конечного потребления.

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

Третье условие - количество каждого продукта (с номером j), расходуемого при получении единицы результирующего продукта номер i, не зависит от конкретных объёмов произведённых продуктов (нет оптовых скидок) и является постоянной величиной a_ji. Все эти величины образуют квадратную (n´n) матрицу технологических, или структурных коэффициентов (коэффициентов прямых материальных затрат) А=(a_ji)_n´n. величина трудозатрат на единицу i-й продукции также является постоянной величиной K_i и измеряется в человекочасах. ω - стоимость человекочаса - одинакова для всех отраслей.

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

Приближения:

1)     в случае моментального баланса все интенсивности не зависят от времени, при расчёте баланса за весь период они могут произвольно меняться, но информация об этом теряется.

2)     Все коэффициенты модели (a_ji, K_i, ω) от времени не зависят (она статическая).

3)     Модель линейная (см. выше).

Решим в этой модели прямую задачу, то есть попытаемся найти уравнения баланса – выражения для вычисления объёмов конечного потребления, полный объём трудозатрат и цены на продукцию. Для этого рассмотрим, что происходит с полным объёмом j-й продукции x_j. Он расходуется на производство продукции других видов (в том числе и на воспроизводство j-й продукции) а также на конечное потребление (т.е. собственно потребление и накопление). Так как, согласно свойству линейности, количество j-го продукта, расходуемого при получении единицы i-го продукта является постоянной величиной a_ji, то для производства всего объёма i-го продукта потребуется a_ji×x_i, а для производства всех видов продукции - единиц  j-й продукции. Вместе с конечным потреблением это даёт полный объём x_j: При изменении j от 1 до n это выражение даёт первую группу из n уравнений баланса. Ещё одно выражение получается для полного объёма трудозатрат z при суммировании полных объёмов трудозатрат на каждый вид продукции (произведений K_i×x_i) по всем видам продукции: Третья группа из n балансовых уравнений – уравнения для цен на единицу продукта – получается на базе трудовой теории стоимости. Цена единицы  j-й продукции P_j складывается из издержек производства (цены ресурсов – i-ых продуктов, израсходованных на производство - a_ijP_i) и прибавленной стоимости ωК_j: Приведём полученную выше полную систему из 2n+1 уравнений баланса в натуральном выражении:

.                     (1)

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

(2)

Уравнения баланса в форме (1), (2) позволяют по известным полным объёмам продукции и ценам на неё определить объёмы конечного потребления, величины трудозатрат на единицу продукции и полный объём трудозатрат, связанный с количеством занятых в производстве. Если последний действительно является величиной, искомой в процессе анализа экономической системы, то первые два (, ) являются как раз отправной точкой этого анализа. С точки зрения анализа поведения экономической системы важной является задача, обратная к решённой выше, т.е. задача определения полных объёмов продукции, цен на неё и числа занятых в производстве по известным технологическим и демографическим характеристикам системы, прямо связанным с объёмами конечного потребления и величинами трудозатрат на единицу продукции, то есть определение , z и через и . В силу того, что уравнения (2) являются матричной формой системы линейных уравнений с постоянными коэффициентами по отношению к переменным и , они могут быть решены с использованием стандартного аппарата линейной алгебры. При этом далее здесь значки векторов у векторных переменных будут опущены, так как любой n- мерный вектор может быть представлен, как матрица – столбец размера (n´1). Решая уравнения (2) и используя соотношение , получим:

(3)

Здесь Е=(d_ij)_n´n – единичная матрица, а обратная матрица (Е-А)^-1 и транспонированная к ней являются неизменными при любых изменениях демографической ситуации (вектор Y) и вычисляются по общему правилу: , где |Е-А| - определитель, а - присоединённая к (Е-А). Приведённое здесь выражение обратной матрицы через ряд является альтернативным способом её вычисления, позволяющим организовать процесс приближённого вычисления (Е-А)^-1 с помощью быстро сходящегося ряда. Это выражение отражает процесс установления равновесия в рассматриваемой экономической системе. матрицы (Е-А)^-1 и {(Е-А)^-1}^Т могут измениться только в случае изменения структуры производства (матрицы А), т.е. технологической революции. Более того, структура цен, как следует из третьего уравнения (3), также может измениться только в случае изменения технологии производства, принятой в обществе, т.е. изменения А и К. Изменение же величины почасовой оплаты ω, принятой во всём экономическом объекте, приведёт лишь к пропорциональному изменению всех цен, без изменения соотношения между ними. Отдельно замечу, что матрица (Е-А)^-1 обязательно существует, и получаемый из (3) Х имеет экономический смысл (его компоненты положительны) в случае, когда все элементы А неотрицательны и суммы их по столбцам не больше 1, причём хотя бы одна строго меньше. Таким образом, для гарантии получения Х из (3), вообще говоря, может быть необходим подбор специальной системы единиц измерения объёмов Х и Y, в которой матрица А удовлетворяет упомянутым условиям.

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

I.2. Пример выполнения задания №1

Конкретные условия примера выполнения домашнего задания взяты из [1] для Сидорова И. П.:

, , , w=$5.

В рассматриваемых отраслях действует 40 часовая рабочая неделя, 4 недели в году – отпуск.

Произвести расчёт баланса в модели Леонтьева для четырёх  отраслей социально- культурной сферы, выполнив пункты 1)-6) задания [1] и найдя вектора

.

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

1) экономический смысл структурных коэффициентов

Перечислим все исходные данные задачи с указанием их экономического смысла. В рассматриваемых отраслях социально- культурной сферы существуют следующие технологические соотношения - при оказании одной услуги по организации досуга используется: 0,095 услуг этого же типа (a₁₁=0,095); 0,09 тура (a₂₁=0,09); 0,085 фильма, т.е. для получения 200 досуговых заказов необходимо отснять 17 фильмов (в данном случае рекламных), (a₃₁=0,085); для получения 100 досуговых заказов необходимы 8 заказов на рекламные услуги (a₄₁=0,08); трудозатраты – 100 человекочасов (K₁=100 ч.час./шт.). при организации одного тура необходимы: заказ 0,05 досуговой услуги (a₁₂=0,05); 0,08 тура – в среднем 8 сопровождающих на 100 туристов (a₂₂=0,08); 0,095 отснятого фильма (a₃₂=0,095); оказывается 0,09 рекламных услуг (a₄₂=0,09); трудозатраты – 10 человекочасов (K₂=10 ч.час./шт.). при производстве одного фильма в среднем заказывается: 0,025 досуговых услуг (a₁₃=0,025); 0,015 туров (a₂₃=0,015); 0,05 фильмов (a₃₃=0,05); оказывается 0,08 рекламной услуги (a₄₃=0,08); трудозатраты – 500 человекочасов (K₃=500 ч.час./шт.). при оказании одной рекламной услуги заказывается: 0,08 досуговой услуги (a₁₄=0,08); 0,05 тура (a₂₄=0,05); 0,025 фильма (a₃₄=0,025); оказывается 0,015 рекламной услуги (a₄₄=0,015); трудозатраты – 3 человекочаса (K₃=3 ч.час./шт.). Требуется решить прямую задачу планирования, т.е. найти величины полного годового объёма оказания услуг и цены единицы услуги для каждой из четырёх отраслей СКС при условии того, что конечное потребление составит 1900000 досуговых услуг (y₁), 100000 туров (y₂), 50000 фильмов (y₃) и 16 млн. рекламных услуг (y₄).

2) уравнения межотраслевого баланса в натуральном выражении

Составим теперь уравнения межотраслевого баланса в натуральном выражении в явном виде согласно (1), при этом диагональные коэффициенты результирующей линейной системы при искомых объёмах x_i будут равны (1- a_ii):

.

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

3) матрица (Е-А)^-1

Вычисление матрицы (Е-А)^-1 может быть произведено вручную с помощью приведённой выше формулы, однако даже в рассматриваемом случае эта процедура чрезвычайно громоздка, по- этому здесь приводятся только окончательные результаты компьютерных расчётов, проведённых в одном из двух описанных ниже (§II.3.) подходов:

(Е-А)^-1= .

Зная эту матрицу, можно переходить к определению векторов Х и Р.

4) Определение вектора полного объема оказанных услуг и вектора цен

вектора полного объема оказанных услуг и цен легко определить с использованием первого и третьего выражения из (3):

шт.;

5) Определение численности занятых в отраслях СКС

Для определения численности занятых в отраслях СКС используем второе выражение из (3), тогда полный объём трудозатрат z, связанный с количеством занятых в этих отраслях, будет равен:

Число занятых в этих отраслях СКС N_зан. можно определить, разделив z на годовой объём рабочего времени одного занятого в вышеупомянутых отраслях СКС – 40×(52-4)=1920 ч.час.:  N_зан.=9,138×10⁸/₁₉₂₀=475.900 чел.

6) Оформление отчёта

Отчет о выполнении задания должен содержать титульный лист, формулировку задачи с конкретными числовыми данными и пункты выполнения задания, аналогичные вышеизложенным в §I.2. При выполнении пунктов I.2.3), I.2.4)  должно  быть указано,      как   были    найдены  (Е-А)^-1, Х и Р. Если они найдены без применения компьютерных средств, то должны быть приведены промежуточные выкладки, если были использованы компьютерные программы, то необходимо указать, какие. При этом отчёт может быть представлен в электронном виде в формате того приложения, в котором были произведены вычисления.

I.3. рекомендации по использованию компьютерного обеспечения

При выполнении задания рекомендуется пользоваться компьютерными приложениями типа математических пакетов общего назначения или крупноформатных электронных таблиц. Отчет о выполнении задания может быть оформлен в них целиком в электронном виде. выигрыш от использования вышеупомянутых приложений очевиден при выполнении пунктов I.2.3)-5), т.е. при вычислении (Е-А)^-1, Х, Р и N_зан.. Из математических пакетов общего назначения наиболее пригоден в этом отношении MathCad, как обладающий пользовательским интерфейсом, близким к обычной форме записи математических выражений. Этот пакет можно рекомендовать для выполнения данного задания в первую очередь, т.к. он допускает прямое использование матричных выражений в форме (3) при условии задания численных значений элементов матриц А, Y и K. При этом пользователь вообще не участвует в процедуре программирования – он просто вводит исходные числовые матрицы, формулы (3) и получает результат! Внешний вид экрана MathCad-а с рабочим листом, содержащим все вычисления из вышеприведённого примера, приведён на рис. 1.

 Пример расчета в балансовой модели с использованием MathCad-а находится в файле Balance.MCD каталога ММЕ сетевого сервера в специализированном компьютерном классе. Менее удобны, но всё же пригодны для проведения матричных операций крупноформатные электронные таблицы. Среди этого класса приложений выделяется Excel, как часть чрезвычайно широко распространённого в настоящее время офисного пакета MSOffice. Основные проблемы применения этого приложения в операциях с матрицами заключены в существовании двух типов групповых операций в КЭТ Excel – операций с интервалами, к которым большинство пользователей КЭТ привычно, и групповых операций (операций с массивами), интерфейс которых не является общеизвестным, но именно к ним относятся операции транспонирования, присутствующие при расчётах в балансовой модели. Пример расчета в балансовой модели с использованием КЭТ Excel находится в файле Balance.xls каталога ММЕ сетевого сервера в специализированном компьютерном классе. Возможны, конечно, и другие варианты, однако здесь мы ограничимся только наиболее удобным и наиболее распространённым. Для ознакомления с правилами работы в пакете MathCad можно порекомендовать выполнить лабораторную работу, электронная гипертекстовая версия указаний к выполнению которой находится на вышеупомянутом сервере в каталоге MathCadEx в файле Mcad_lb.doc. Для ознакомления с правилами работы в пакете Excel можно порекомендовать воспользоваться русскоязычным Help, встроенным в эту программу: при всей его громоздкости он достаточно информативен и эффективен. Необходимо отметить, что в файлах примера приведены только вычисления и минимальные комментарии к ним, причём решаемая задача – баланс в семиотраслевой модели Леонтьева, что позволяет выполнить работу по аналогии, но не прямой подстановкой своих данных в лист примера! При этом пункты I.2.1) и I.2.2) в файлах примера отсутствуют, как не содержащие вычислений, а пример их выполнения приведён здесь выше. Также необходимо обратить внимание на различие результатов, полученных в обоих подходах. Причина этого двояка: во- первых, в листе КЭТ Excel количество видимых значащих цифр числа определяется размером области, отведённой для размещения этого числа и его форматом. Поэтому простейший вариант получения результата “большей точности”, это увеличения размера всех ячеек рабочего листа. Однако есть вторая часть – вопрос точности промежуточных математических вычислений каждого приложения. В принципе возможен контроль точности в каждом приложении путём анализа и модификации исходных параметров приложения, однако чаще всего эта процедура достаточно сложна для массового пользователя и, кроме того, задаваемый уровень точности определяется в приложениях по алгоритмам, которые в принципе не известны пользователю, что не позволяет полностью им доверять. По этому, в ситуациях, когда точность должна быть выше четвёртой значащей цифры числа, самым простым способом контроля погрешности является использование двух приложений различных разработчиков. Замечу, что четыре значащие цифры, это уровень точности, обусловленный стандартным представлением числа одним словом при не слишком большом объёме вычислений при использовании алгоритмов без быстрого накопления ошибок. Последнее условие является общим требованием ко всем коммерческим программам, однако выполнено ли оно в каждом конкретном приложении, как отмечено выше, это очень большой вопрос! Яркий тому пример – различие результатов решения одной и той же задачи в пакетах MathCad и Excel. При вычислении полного числа занятых результат составил, соответственно, 10.003.000 и 9.969.688 человек, погрешность результата оказалась, как и следовало ожидать, в третьей - четвёртой значащей цифре:

(Δ=2×^{(10.003.000-9.969.688)}/_{( 10.003.000+9.969.688)}»0,3%).

Наиболее вероятная причина ошибки – использование различных алгоритмов вычисления обратной матрицы в этих пакетах.

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

II.1. краткие теоретические сведения

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

Постановка задач

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

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

     Решение двойственной к ней задачи отвечает на следующий вопрос:

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

Прямая задача линейного программирования может быть связана со следующей ситуацией. Имеются n способов получения прибыли (оказание n видов услуг) с объёмами x_i (число штук i-й оказанных услуг)_. При этом используются m видов ресурсов, запас j-го из которых равен b_j . При этом расход каждого ресурса j и величина прибыли в каждом из процессов i линейно зависят от количества оказанных услуг i-го вида с коэффициентами a_ji и c_i , соответственно. Матрица А=(a_ji)_m´n по смыслу аналогична такой же из первой части и также называется матрицей технологических, или структурных коэффициентов. Тогда оптимальный по критерию максимума получения прибыли план может быть получен из решения следующей прямой задачи линейного программирования:

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

(4.1)

Двойственная к задаче (4) задача имеет следующий вид (z_j – искомые предельные цены):

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

Основные понятия модели

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

Целевая функция L(x) – математическое выражение, связывающее факторы (параметры) модели. Экономический смысл целевой функции отражает критерий оптимальности – показатель, имеющий экономическое содержание и служащий формализацией конкретной цели управления, например: максимизация прибыли (строка 1 в (4)), максимизация качества продукции или минимизация издержек (5.1).

Система ограничений модели – пределы, ограничивающие область допустимых (приемлемых, осуществимых) решений, фиксирующие основные внутренние и внешние свойства объекта, связанные с целью оптимизации. Уравнения связи (типа f_j(x)<b_j)– математическая формализация системы ограничений (строки 2 и 3 в (4), (5.2 , 5.3) ). Система ограничений отражает экономический смысл уравнений связи.

Система, состоящая из целевой функции и уравнений связи, - задача экономико- математического моделирования (ЭММ). В случае, когда целевая функция и уравнения связи линейны, а переменные управления меняются непрерывно, задача ЭММ называется задачей линейного программирования (ЛП). Основное свойство множества допустимых планов (МДП) задачи ЛП - оно является выпуклым многогранником. Выпуклым называется множество, которому принадлежат все отрезки, соединяющие любые две точки этого множества. Если задача ЛП имеет решение, то оно находится в вершине МДП. Планы, находящиеся в вершинах МДП, называются базовыми. Задачи линейного программирования делятся на задачи с ограничениями в форме неравенств (общая задача ЛП) и в форме равенств (каноническая задача ЛП). При математической формализации экономических задач с помощью линейной модели получаются общие задачи ЛП – например, (4), (5). Любой общей задаче путём введения дополнительных переменных может быть сопоставлена каноническая задача. Так, задаче (4) путём введения в каждое неравенство типа “расход ресурса £ запас ресурса” (строка 2 в (4)) дополнительной переменной x_n+j (неизрасходованный остаток j-го ресурса) сопоставляется следующая каноническая:

При этом размерность задачи (6) – число переменных плана - по сравнению с (4) увеличилась с n до n+m.

При решении задачи (4) важное значение имеют коэффициенты ресурсоотдачи, среди которых здесь будут использованы дифференциальные и приростные. Дифференциальный коэффициент ресурсоотдачи k_ji показывает стоимость оказанных при использовании единицы j-го ресурса i–ых услуг. Те виды услуг, для которых все k_ji оказываются наименьшими по всем видам услуг, являются наименее выгодными. Они не должны присутствовать в оптимальном плане. Это позволяет, путём принудительного обнуления объёмов оказания таких услуг снизить размерность задачи и, таким образом, упростить её решение. Вычисляются они следующим образом - k_ji=c_i/a_ji.

приростной коэффициент ресурсоотдачи К_j – это коэффициент пропорциональности между приращением значения целевой функции оптимального плана и вызвавшим это приращение изменением запасов j-го ресурса. Можно считать, что К_j показывают, на сколько увеличится значение целевой функции исходной задачи в оптимальном плане  при увеличении величины запаса j-го ресурса на единицу. С математической точки зрения является полной производной от оптимального значения целевой функции по величине запаса j-го ресурса: К_j=dL_opt/db_j.

Элементы теории двойственности

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

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

2.     Если задача (4) имеет бесконечный оптимальный план (целевая функция не ограничена сверху в МДП), то МДП задачи (5) - это пустое множество (задача допустимых планов не имеет). И наоборот, если задача (5) имеет бесконечный оптимальный план (целевая функция не ограничена снизу в МДП), то МДП задачи (4) - это пустое множество.

Способы решения

Поскольку решения задачи ЛП находятся в вершинах МДП, основным способом решения является метод перебора вершин МДП, который, однако, имеет разные модификации. Среди них следует упомянуть пригодный в любой ситуации метод полного перебора (определение координат всех вершин МДП и вычисление в каждой вершине значения целевой функции с выбором оптимального – наибольшего или наименьшего – значения). Этот метод является самым неэффективным, т.к. число вершин МДП – N -  удовлетворяет неравенству: N £ , а число сочетаний С – весьма быстро возрастающая функция размерности задачи. Однако задача одномерной оптимизации (n=1) легко разрешима в методе полного перебора, т.к. МДП для неё – отрезок, в одном из двух вершин которого и наблюдается оптимум. При малом (n=2) количестве переменных общей задачи ЛП (4) , когда МДП можно изобразить графически на плоскости, применим графический метод поиска решения, имеющий два варианта – градиентный метод и метод линий постоянного уровня, впрочем, чрезвычайно схожих, хоть и получаемых из совершенно различных подходов поиска оптимального решения в общем случае математического программирования. Порядок их следующий: 1) построение МДП; 2) поиск оптимального плана. Пункт 2) в градиентном методе выполняется путём построения вектора градиента целевой функции grad(L(x))=(c₁,c₂) и выбора вершины МДП, наиболее удалённой (для задачи максимизации) или ближайшей (для задачи минимизации) к началу координат вдоль направления градиента (эти два плана называются опорными). в методе линий постоянного уровня пункт 2) выполняется путём построения линии постоянного уровня целевой функции, во всех точках которой  у L(x) наблюдается одинаковое значение L₀ (это прямая с уравнением c₁x₁+c₂x₂=L₀). Одно из свойств задачи ЛП – параллельность всех её линий постоянного уровня. выбор вершины МДП, являющейся решением, производится при перемещении линии постоянного уровня от начала координат через МДП. Опорными являются первая и последняя вершины, через которые прошла перемещаемая линия. наиболее удалённая от начала координат вершина – решение для задачи максимизации, а ближайшая к нему - решение задачи минимизации. Подробнее см. в примере выполнения задания №2. Вообще говоря, подобная процедура могла бы быть пригодной в случае любой размерности, однако при n=3 грани МДП – плоскости, поверхность постоянного уровня целевой функции также плоскость в трёхмерном пространстве (см. рис. 2). Здесь точки А и В – опорные планы на минимизацию и максимизацию, a и b - поверхности постоянного уровня целевой функции. при большей размерности представить воображаемый вид МДП не возможно в принципе, т.к. грани МДП и поверхность постоянного уровня L(x) – гиперплоскости в n- мерном пространстве. При этом, однако, как было отмечено выше, можно проанализировать задачу (4) с помощью дифференциальных коэффициентов ресурсоотдачи и понизить её размерность. В случае снижения числа не равных нулю переменных до 2-х можно использовать графический метод.

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

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

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

В отличие от (6), первая строка (7) – целевая функция – имеет иной вид, к которому, однако, легко преобразовать исходную L(x), положив a_i= -c_i , a₀=0. Во второй строке (7) находятся ограничения в форме равенств, в которых присутствуют элементы матрицы , получаемой из упомянутой выше А простым присоединением к ней справа единичной матрицы размера m´m: =(А|Е). в задаче (7), аналогично первой части, можно ввести вектор переменных Х размера m+n ´1, вектор свободного члена В размера m ´1 и вектор коэффициентов целевой функции a размера m+n ´1, в котором a_i=0 при i>n. Тогда (7) можно записать в матричном виде:

симплекс- таблица строится (см. табл.1) из канонической задачи (7) следующим образом: 1) она содержит n+m+3 столбцов и m+2 строк; 2) первая строка является информационной и содержит заголовки столбцов четырёх типов – столбца имён базисных переменных, столбца их значений в конкретном базовом плане этой симплекс- таблицы, n+m столбцов переменных задачи x_i, столбца контрольных сумм (он не является обязательным и содержит построчные суммы всех числовых значений таблицы); последняя строка называется индексной и содержит параметры a₀,a_i целевой функции, а между ними расположены m строк параметров ограничений. Выше было упомянуто, что в симплекс- методе таблица каждой итерации соответствует какой-то вершине МДП. При этом в каждой такой вершине отличны от 0 только m из n+m переменных x_i. Они, как это принято в теории линейных систем, называются базисными, а остальные – свободными. Свободные переменные полагаются равными 0. В симплекс таблице действует следующее правило: базисные переменные перечислены в первом столбце, а их значения в данном базовом плане находятся во втором столбце. Этот план является оптимальным, если симплекс- таблица удовлетворяет критерию оптимальности: индексная строка содержит только положительные и нулевые значения.

Таблица №1. Симплекс- таблица общего вида (для случая исходного заполнения).

Итеративная процедура симплекс- метода состоит в последовательном преобразовании этой таблицы от одного базового плана к другому в случае возможности улучшения плана. Признаком наличия лучшего, по сравнению с достигнутым, плана является критерий возможности улучшения плана: если индексная строка симплекс- таблицы содержит отрицательные элементы, а в столбцах над ними имеются элементы a_ji, отношение b_j/a_ji для которых больше нуля, то данный план может быть улучшен. Если все отношения b_j/a_ji в столбцах над отрицательными элементами индексной строки меньше нуля или равны ¥ (a_ji=0), то задача не имеет конечного оптимального плана. Это критерий отсутствия оптимального плана. Улучшение плана производится путём введения в состав базисных переменных х_{l –} той переменной, в столбце которой находится наибольшее по модулю отрицательное a_l, и выведения из базиса той переменной х_k, для которой отношение b_k/a_kl  наименьшее положительное (если положительных нет, то неотрицательное). Столбец таблицы, содержащий х_l , строка таблицы с х_k и элемент a_kl, стоящий на их пересечении, называются ключевыми, или разрешающими. Для упрощения дальнейших уравнений принято ключевой элемент обозначать l. Процедура пересчёта всех элементов таблицы называется получением симплекс- таблицы следующей итерации, в ней действуют следующие простые правила: все элементы ключевой строки старой таблицы необходимо разделить на ключевой элемент. элементы всех остальных строк новой таблицы, включая индексную, получаются путём вычитания из соответствующих им элементов симплекс- таблицы предыдущей итерации разделённого на ключевой элемент произведения двух элементов старой таблицы, один из которых стоит на пересечении ключевой строки со столбцом, содержащим пересчитываемый элемент, а другой – на пересечении ключевого столбца и строки, содержащей пересчитываемый элемент. Это преобразование производится по нижеприведённым формулам:

для ключевой k-й строки -   

(9)

для остальных строк –

(10)

Здесь верхний индекс ^н – признак элемента новой симплекс- таблицы, его отсутствие – признак элемента симплекс- таблицы предыдущей итерации. Элементы столбца контрольных сумм рассчитываются также путём простого суммирования всех остальных элементов соответствующей строки новой таблицы. Верно полученной считается симплекс- таблица, в которой все элементы столбца контрольных сумм одинаковы в обоих подходах к их вычислению – и при суммировании, и по формулам (9), (10). Симплекс- таблица оптимального плана обладает следующими свойствами: отличны от нуля и равны значениям столбца плана только те переменные (х_i, i=1,n) оптимального плана, которые присутствуют в столбце базиса; находящиеся в столбце плана значения дополнительных переменных (х_i, i=n+1, m), присутствующих в столбце плана, это величины остатков не полностью расходуемых ресурсов с номерами i-n. Ненулевые элементы индексной строки делятся на две группы: a_i при i>n – это двойственные оценки дефицитных (не полностью расходуемых) в данном оптимальном плане ресурсов с номерами i-n. Т.е. это решение двойственной к исходной задачи! Т.о. симплекс- метод позволяет решать задачи (4) и (5) одновременно. Альтернативной к приведенной при постановке задач (4) и (5) интерпретацией двойственных оценок является тот факт, что эти оценки являются коэффициентами пропорциональности между приращением значения целевой функции оптимального плана и вызвавшими это приращение изменениями запасов ресурсов. То- есть они показывают (грубое объяснение), на сколько увеличится значение целевой функции исходной задачи в оптимальном плане  при увеличении величины соответствующего двойственной оценке запаса ресурса на единицу. Т.о., двойственные оценки – приростные коэффициенты ресурсоотдачи. Вторая группа a_i при i£n имеет менее полезное с экономической точки зрения значение – это величина превышения издержек оказания единицы не включённых в оптимальный план видов услуг с номером i над их ценой при условии расчёта издержек с использованием в качестве цен ресурсов их двойственных оценок. Во всяком случае, можно отметить следующее свойство – не равны нулю элементы индексной строки, соответствующие невыгодным (не включённым в оптимальный план) видам услуг или продукции и дефицитным ресурсам. В случае невыполнения этих требований при преобразованиях симплекс- таблицы были допущены ошибки.

II.2. Пример выполнения задания №2

Конкретные условия примера выполнения домашнего задания будут здесь взяты из табл.2.

Таблица №2: Исходные данные задачи.

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

1. При каких объёмах использования 3-х процессов получения прибыли (x₁ , x₂ , x_3.), в которых используются 3 вида ресурсов с известными предельными запасами этих ресурсов (b₁ , b₂ , b_3.), прибыль будет максимальна, если расход каждого ресурса и величина прибыли в каждом из процессов линейно зависят от x_i для этого процесса. Для определённости под используемыми процессами получения прибыли будем понимать оказание трёх видов  услуг, под объёмом x_i этих процессов будем понимать количество оказанных услуг соответствующего типа.

2. Как будет меняться оптимальный план при изменении b₂ - величины запаса второго ресурса.

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

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

Сформулируем теперь прямую задачу ЛП в форме (4) согласно нашим данным. Для этого вычислим величину прибыли, получаемой от оказания единицы каждого вида услуги (т.е. значение коэффициентов с_i из (4) для целевой функции в критерии максимизации прибыли). Эта прибыль есть разность между ценой услуги S_i (последняя строка табл.2) и величиной издержек при её оказании M_i, т.е. суммарной стоимостью ресурсов, расходуемых на единицу этой услуги. Т.е. с_i=S_i-M_i . Величина издержек может быть вычислена по следующей формуле : Здесь R_j - цена единицы  j-го ресурса (последний столбец табл.2). величина издержек и прибыли на одну услугу принимают следующие значения:

M₁= 4×1+2×2+1×3= 11 руб.,     с₁= 16-11= 5 руб.,

M₂= 6×1+1×2+3×3= 17 руб.,     с₂= 22-17= 5 руб.,

M₃= 8×1+3×2+4×3= 26 руб.,     с₃= 32-26= 6 руб.

Теперь можно записать формализованную в форме (4) прямую задачу ЛП:

(11)

2) исследование модели с помощью дифференциальных коэффициентов ресурсоотдачи

произведём исследование модели с помощью дифференциальных коэффициентов ресурсоотдачи k_ji для понижения размерности задачи. Процедура вычисления k₁₁ выглядит следующим образом – надо первый коэффициент целевой функции разделить на первый коэффициент первого ограничения - k₁₁=с₁/a₁₁=5/4=1,25. Аналогично для k₂₁ – надо первый коэффициент целевой функции разделить на первый коэффициент второго ограничения – k₂₁=с₁/a₂₁=5/2=2,5. В результате матрица коэффициентов К=(k_ji)_3´3 принимает следующий вид: Так как все наименьшие по строкам элементы находятся в К в третьем столбце – столбце дифференциальных коэффициентов ресурсоотдачи услуги третьего вида, то использование ресурсов при оказании услуги третьего типа наименее эффективно и в оптимальном плане значение х₃ должно быть равно 0. Таким образом, число переменных в задаче может быть понижено до двух:   х₁=х   и    х₂=у. Такая задача может быть решена  графически. Её формализованный вид:

(12)

3) графический метод решения задачи ЛП

Решим задачу (12) графическим методом. Для этого построим многогранник допустимых планов задачи (в данном двухмерном случае это многоугольник). Уравнения границ МДП получаются из 4-х последних строк (12) заменой в них знаков неравенства на “=”:

(13)

Это уравнения прямых, причём два последних – осей Оу и Ох. Построим эти прямые, пользуясь тем, что любую прямую можно провести, если известны две её различные точки. Одна из этих точек может быть получена как пересечение с осью Оу (при этом надо положить х=0 и найти у), а другая - как пересечение с осью Ох (при этом надо положить у=0 и найти х). Проиллюстрируем это на примере первого уравнения прямой в (13):

Точка пересечения с осью Ох имеет координаты (х,0)Þ 4х+6×0=2400Þ х=²⁴⁰⁰/₄=600.

Точка пересечения с осью Оу имеет координаты (0,у)Þ 4×0+6у=2400Þ у=²⁴⁰⁰/₆=400.

Таким образом, первая прямая проходит через точки (600,0) и (0,400).

Произведя аналогичные вычисления для оставшихся двух прямых из (13) и проведя необходимые графические построения, получим МДП, изображённый на рис.3 (он заключён между прямыми всех ограничений).

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

4×100+6×100=1000£2400,

2×100+1×100=300£800,

1×100+3×100=400£900,

100³0; 100³0.

Так как все они являются верными числовыми неравенствами, то МДП на рис.3 получен верно.

 найдём теперь оптимальный план методом линий постоянного уровня. Для этого построим линию постоянного уровня (как было отмечено выше в разделе описания способов решения задачи ЛП, все линии постоянного уровня данной задачи – параллельные прямые, а значит, достаточно построить одну). Представленная на рис.3 линия постоянного уровня проведена через точку пересечения прямой третьего ограничения с осью Ох с координатами (900,0). Значение целевой функции в этой точке равно 900×5+0×5=4500. Это и есть значение L₀ в уравнении линии постоянного уровня. Само уравнение принимает вид 5х+5у=4500. Для построения прямой достаточно найти точку её пересечения с осью Оу: 5×0+5у=4500Þ у=⁴⁵⁰⁰/₅=900. Т.о. координаты второй точки прямой постоянного уровня – (0,900). Через эти две точки она и проведена на рис.3. Так как все линии постоянного уровня параллельны, то сдвигая эту линию в направлении начала координат, можно получить любую другую линию постоянного уровня с значением L₀, меньшим 4500 (значение L₀ возрастает с удалением линии постоянного уровня вправо от начала координат, т.к. коэффициенты при х и у в данном случае положительны). Передвигая таким образом линию постоянного уровня, можно найти точку опорного плана на максимизацию, в которой она коснётся МДП. На рис.3 это точка с координатами (300,200). В ней и находится искомый оптимальный план, дающий максимальную прибыль в задаче (12). Эта точка действительно является оптимальной потому, что линии постоянного уровня целевой функции, проходящие выше неё, не имеют общих точек с МДП, содержащим допустимые планы задачи (12). Проходящие же ниже неё линии постоянного уровня имеют меньшие значения L₀, о чём свидетельствует и тот факт,  что они пересекают МДП не только в граничных, но и во внутренних точках, а оптимальные планы, как отмечалось выше, достигаются в задаче ЛП только в граничных точках.

Теперь найдём оптимальный план градиентным методом. Вектор градиента , как отмечалось выше, в случае двумерной задачи линейного программирования имеет координаты (с₁,с₂), и в задаче (12) – (5,5). На рис.3 изображён, из соображений масштаба, вектор 100grad(L)=(500,500). Видно, что наиболее удалённой от начала координат в направлении этого вектора оказывается уже найденная выше вершина (300,200) – она и есть решение. Для проверки этого достаточно через неё провести прямую, перпендикулярную вектору градиента – эта прямая будет линией постоянного уровня, пересекающей МДП в крайней точке, а сама эта точка – опорным планом на максимизацию.

Величина прибыли в оптимальном плане L_opt оказывается равной 5×300+5×200=2500 руб.

4) графический метод решения параметрической задачи

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

> (14)

Построим график зависимости прибыли от величины b₂. Для этого получим сначала, аналогично предыдущему пункту, МДП для ограничений (14) с фиксированными правыми частями, без учёта ограничения по второму ресурсу. Результат построения приведён на рис.4, а уравнения границ МДП имеют вид:

Рассмотрим теперь, как будет влиять появление ограничения по второму ресурсу на внешний вид МДП рис.4.

При этом будем помнить, что решаемая нами задача относится к классу линейных, а значит и получаемые зависимости также будут линейны. Напомню также, что оптимальный план нашей задачи должен находиться в вершине МДП, а значит изменение характера линейной зависимости прибыли от запаса второго ресурса возможно при появлении у МДП новых вершин, т.е. изменении его формы. Это означает, что при построении зависимости L_opt(b₂) имеет смысл рассматривать только те значения b₂, при которых прямая второго ограничения проходит через вершины МДП рис.4, т.е. точки О(0,0), А(0,300), В(300,200), С(600,0). Для проверки этого рассмотрим также дополнительную точку D(0,150), которая лежит по середине границы ОА МДП и не является вершиной. Вычислим значения b₂, при которых прямая ограничения второго ресурса с уравнением 2х+у=b₂ проходит через вышеупомянутые точки:

b₂(О)=2×0+1×0=0,

b₂(D)=2×0+1×150=150,

b₂(А)=2×0+1×300=300,

b₂(В)=2×300+1×200=800,

b₂(С)=2×600+1×0=1200.

Построим (см. рис.5 a.-d.) для каждого полученного значения b₂ (кроме точки О) МДП и решим для них задачу (14), т.е. найдём точки оптимальных планов именно для этих МДП! В точке О МДП содержит лишь её одну, а значит, эта точка с координатами (0,0) и есть единственный допустимый и оптимальный план задачи (14) с нулевым запасом второго ресурса. Результаты поиска оптимальных планов (см. рис.5), а также значения b₂ и L_opt сведём в таблицу №3. Приведённая в таблице 3 точка Е со значением b₂(Е)=1500 на рисунке отсутствует, для неё ограничение 2 сместилось за пределы МДП и не имеет с ним общих точек, ресурс второго типа стал избыточен и вид МДП определяется только первым и третьим ограничениями. Ситуация практически совпадает с рис.5 d и имеет тот же оптимальный план в точке С.

Таблица №3: зависимость прибыли от величины b₂.

график зависимости прибыли от величины b₂ приведён на рис.6.

Видно, что, как и было отмечено выше, величина прибыли в точке D лежит на прямой, соединяющий величины прибылей в О и А, в ней наклон зависимости L_opt(b₂) не меняется. Замечу также, что эта зависимость называется линией невозрастающей эффективности (см. ниже) и отражает закон невозрастания эффективности в случае экстенсивного расширения производства. При этом, как и отмечалось выше, изломы этой линии происходят в точках, соответствующих появлению новых вершин в МДП, т.е. изменению его формы. Первый излом при переходе от треугольного МДП к четырёхугольному, второй – от четырёх- к пятиугольному и третий при обратном переходе – от пяти- к четырёхугольному МДП.

Построим теперь график зависимости К₂ - приростного коэффициента эффективности вовлечения второго ресурса от величины b₂. Учтём при этом, что К₂=dL_opt/db₂ , а производная линейной функции – константа, равная тангенсу угла наклона графика функции. Тогда на отрезке изменения b₂ от 0 до 300 К₂=^(1500-0)/_(300-0)=5 ; на отрезке изменения b₂ от 300 до 800 К₂=^(2500-1500)/_(800-300)=2 ; на отрезке изменения b₂ от 800 до 1200 К₂=^(3000-2500)/_(1200-800)=⁵/₄=1,25; при b₂  больших 1200 К₂=0. Эта зависимость приведена на рис.7, видно, что эффективность вовлечения дополнительных запасов второго ресурса остаётся постоянной, либо падает, т.е. не возрастает.

5) симплекс- метод решения задачи

Решим полную исходную задачу симплекс- методом. Заполним симплекс- таблицу нулевой итерации (исходную) согласно правилам, приведённым выше в разделе алгоритма симплекс метода.  Результат приведён в табл.4.

Таблица №4: Симплекс- таблица нулевой итерации.

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

Результат – симплекс- таблица первой и остальных итераций – приведён в табл.5. Второй столбец контрольных сумм получен простым суммированием по строке, первый – по формулам преобразования элементов.

Таблица №5: Симплекс- таблицы остальных итераций.

На третьей итерации достигается оптимальный план, т.к. все элементы индексной строки в нём положительны. Значения ненулевых в нём переменных (базисных) находятся в столбце плана, т.е. x₁=300, x₂=200, а переменная x₃ в состав базисных в оптимальном плане не входит, т.е. она является свободной: x₃=0. Этот результат был получен здесь в пункте 3). Однако, в отличие от графического метода, симплекс- таблица, как уже было отмечено, содержит много дополнительных полезных сведений, в частности, из того, что в базисе оптимального плана присутствует переменная x₄- остаток ресурса первого типа, следует, что этот ресурс имеется в избытке, а остальные ресурсы в этом плане дефицитны. Однако значение этого остатка из столбца плана равно 0, а значит и первый ресурс на самом деле расходуется полностью, однако увеличение его запаса не приведёт к изменению оптимального плана, о чём свидетельствует равенство нулю его двойственной оценки из индексной строки.  Выполнены также и проверочные свойства симплекс- таблицы – одинаковы сосчитанные двумя способами все элементы столбцов контрольных сумм; не равен нулю третий элемент индексной строки, соответствующий невыгодному третьему виду услуги, и не равны нулю пятый и шестой элементы индексной строки, соответствующие дефицитным ресурсам второго и третьего видов. Т.о. весь процесс итераций произведен без ошибок.

6) Двойственная задача

Для ответа на третий вопрос задания сформулируем задачу линейного программирования, двойственную к исходной. Для этого получим расширенную матрицу (4.1) исходной задачи (11):

Теперь транспонируем её:

Составим двойственную к (11) задачу, как предложено выше в пункте “Элементы теории двойственности”, как задачу на минимизацию с ограничениями в форме неравенств со знаком “больше или равно” и вышеприведённой транспонированной расширенной матрицей:

(15)

Получим её решение из пункта оптимальной симплекс- таблицы пункта 5), пользуясь тем, что z_i=a_i+n, т.е. z₁=a₄=0, z₂=a₅=2, z₃=a₆=1. Дадим теперь  экономическую интерпретацию переменных и ограничений двойственной задачи (15). В полученном оптимальном плане значения двойственных (теневых) цен показывают, что для продолжения неубыточного процесса оказания услуг можно закупать дефицитные в полученном плане ресурсы второго и третьего типа по ценам, не превышающим 2 и 1 руб. за штуку, соответственно, а нелимитирующий ресурс первого типа, вообще говоря, при такой системе оценок закупаться не должен. Однако он в оптимальном плане израсходован полностью. Это означает, что при дополнительной закупке дефицитных ресурсов в новом плане первый ресурс станет дефицитным, однако прибыль в новом плане всё же будет положительной. На вопрос, до каких пределов имеет смысл увеличивать объёмы дефицитных ресурсов, как раз и отвечает решение параметрической задачи. Из пункта 4) решения следует, что объём ресурса второго типа имеет смысл увеличивать до 1200 шт., т.е. на 400 шт. (но только этого ресурса, без изменения объёмов других ресурсов!). С другой стороны, если сравнить приростной коэффициент эффективности вовлечения второго ресурса из пункта 4) со значением двойственной оценки этого ресурса, то, как и отмечалось выше, они равны в точке оптимального плана задачи (11). Экономический смысл ограничений (15) заключён в том, что при убыточном процессе оказания услуг, условия которого как раз и определяются в двойственной задаче, дополнительные издержки при оказании этих услуг по закупке дефицитных ресурсов (левые части неравенств второй – четвёртой строк (15)) должны быть не меньше прибыли, при этом извлекаемой.

7) Оформление отчёта

Отчет о выполнении задания должен содержать титульный лист, формулировку задачи с конкретными числовыми данными и пункты выполнения задания, аналогичные вышеизложенным в §II.2. При выполнении пунктов  II.2.3) – II.2.6),  должны  быть приведены вычисления, если, конечно, работа не была выполнена с использованием компьютерных средств. Если были использованы компьютерные программы, то необходимо указать, какие. При этом отчёт должен быть представлен в электронном виде в формате того приложения, в котором были произведены вычисления.

II.3. рекомендации по использованию компьютерного обеспечения

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

Перед изложением конкретных рекомендаций в данном разделе необходимо изложить некоторые исторические сведения. Наиболее широко компьютерные средства использовались при решении задач класса линейного программирования на том этапе развития ЭВМ в нашей стране, когда основным вычислительным инструментом являлись большие машины коллективного пользования (70-ые – 80-ые года ХХ века). Среди распространённых тогда ЭВМ наиболее выделяются в этом отношении машины единой серии (ЕС: ЕС-1033, … ЕС-1066). Связано это с тем, что на всех них была легально установлена единая русифицированная система виртуальных машин (СВМ) разработки фирмы IBM, в состав обязательно поставляемых системных библиотек которой входила математическая библиотека с широким набором операций группы математического программирования, хотя многие организации имели и собственные программные разработки в этой области. Лёгкость применения машин этого типа в экономических расчётах была обусловлена структурой штата обслуживающего персонала этих ЭВМ, в который входил программист, владеющий вышеупомянутым программным обеспечением. По- этому даже в случае полного отсутствия каких- либо навыков работы на ЭВМ у конкретного экономиста- практика была возможность с помощью программиста провести необходимые вычисления, поскольку именно программист производил процедуру математической формализации задачи, адаптации общего приложения к конкретному случаю и проводил вычисления. С заменой ЭВМ этого класса на персональные компьютеры,  работавшие под управлением операционных систем семейства DOS фирмы Microsoft (конец 80-х - начало 90-ых годов ХХ века), ситуация с возможностью их применения конкретным экономистом для случая решения задач оптимизационного класса, и в том числе задач ЛП, существенно ухудшилась. Причин тому две. Во- первых, экономист- практик теперь чаще всего не имел возможности получить квалифицированную консультацию по вопросам формализации задачи и применения программных продуктов для ПК без существенных дополнительных расходов по оплате этих консультаций. Во- вторых, программные продукты, способные производить вычисления такого рода, уже не входили в состав операционной системы и распространялись отдельно, причём были весьма примитивными. Так что возникала задача поиска программы, способной проводить необходимые вычисления, причём с доступным неспециалисту в области программирования интерфейсом. Среди программ этой группы стоит упомянуть пакет EURECA, в котором алгоритм решения задач оптимизации с ограничениями в форме неравенств (частным случаем которого является задача ЛП) присутствовал и имел достаточно простой интерфейс. Следующий шаг – переход к ПК под управлением операционных систем группы Windows – привёл к новому осложнению ситуации. Теперь знание компьютерных средств является необходимым требованием к  любому специалисту, а специалисту экономического профиля – в первую очередь. В настоящее время основные офисные программные средства типа пакета MSOffice в ряде случаев содержат готовые алгоритмы решения задач оптимизации. Однако интерфейс этих алгоритмов всё же нельзя назвать достаточно “прозрачным”. Так, в приложении Excel из пакета MSOffice присутствует общая процедура решения задач линейного, выпуклого, нелинейного и частично- целочисленного программирования. Вид её диалоговых окон при решении задачи ЛП приведён на рис.9,10.

При этом она содержит ряд обязательных параметров, смысл которых в конкретных задачах не всегда ясен. кроме того, использование общих алгоритмов в конкретных задачах не всегда рационально, например в целочисленном программировании, где применение реализованного в приложении Solver общего метода ветвей и границ (алгоритма Гомори) может привести к полному перебору или даже превышению над полным перебором в случае задачи с булевыми переменными. Применение этой автоматизированной процедуры к решению задачи ЛП можно найти на последнем рабочем листе в книге примера выполнения задания [1] в файле LinProgr.xls. С другой стороны, такие приложения, как крупноформатные электронные таблицы (КЭТ), имеют интерфейс, в котором многие алгоритмы оптимизации могут быть весьма просто реализованы самим пользователем, если, конечно, они ему знакомы. Прекрасный тому пример – табличный алгоритм симплекс- метода. Для случая КЭТ он будет здесь рассмотрен ниже. В случае математических пакетов общего назначения типа MathCad-а существуют определённые трудности. Во- первых, использование подобных программ в этом случае возможно при наличии в них соответствующих процедур, которые обычно не входят в базовый комплект поставки и распространяются отдельно. Во- вторых, интерфейс этих процедур требует от пользователя минимального знакомства с языками программирования, в частности с понятием подпрограммы.

разберём теперь случай применения КЭТ, в частности КЭТ Excel из пакета MSOffice для реализации алгоритма симплекс- метода. Возможны, конечно, и другие варианты, однако здесь мы ограничимся только наиболее распространённым в настоящее время офисным вычислительным средством. При этом для понимания нижеизложенного необходимо знание основных понятий КЭТ: рабочий лист, ячейка листа, её адрес, слой значения и слой формул ячейки, а также понятие об основных встроенных функциях и групповых операциях КЭТ. Пример решения всей вышеприведённой задачи в этой программе находится в файле LinProgr.xls каталога ММЕ сетевого сервера в специализированном компьютерном классе. Там, на листе симплекс- метода и реализована вышеописанная процедура. Удобство применения КЭТ в этой ситуации заключается в наличии двух типов адресов ячеек листа КЭТ, используемых при проведении вычислений, т.е. написании формул. Это абсолютный, не изменяемый при копировании адрес строки (число) или столбца (буква), признаком которого является наличие перед адресом символа $. Второй тип адреса – относительный - , применяемый программой по умолчанию, при копировании формулы изменяется на столько строк и столбцов, на сколько эта формула была перемещена в листе от своего исходного положения. Для симплекс- метода это позволяет в каждой симплекс- таблице писать формулы только для двух ячеек – первой ячейки разрешающей строки и первой ячейки любой другой строки. После этого путём фиксации в этих формулах адреса ключевых строки и столбца с последующим копированием формул во всю таблицу сразу получается полная таблица новой итерации. Процедура построения самих формул выглядит с использованием “мыши” довольно просто: в рассчитываемую ячейку вводится знак “=” , после чего формула строится простым указанием мышью (со щелчком на выбранной ячейке) на участвующие в вычислениях ячейки предыдущей итерации (см. рис.8) с введением между адресами ячеек знаков необходимых арифметических операций “-“, “*”, “/” и, как было выше отмечено, символа $ перед адресами ключевых столбца и строки (см. рис.11), с последующим копированием формул в строку.

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

литература

1.   Махов А.М. Контрольные задания для самостоятельной учебной работы студентов экономического факультета СПбГУП по дисциплине “Математическое моделирование в экономике”. СПб.: Изд. СПбГУП. 1998.

2.   Гагин А.А. Исследование эффективности использования производственных ресурсов с помощью методов линейного программирования. Учебно- методическое пособие для студентов экономического факультета. СПб.: Изд. СПбГУП. 1993. - 78 с.

3.   Губин Н.М., Добронравов А.С., Дорохов Б.С. Экономико- математические методы и модели в планировании и управлении в отрасли связи. . М.: “Радио и связь”. 1993. - 376 с .

4.   Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в   упражнениях и задачах. М.”Высшая школа”. ч.1. -320 с.

5.   Леонтьев В. Экономические эссе. М.: “политическая литература”. 1990.– 413 с.

6.   Дегтярёв Ю.И. Методы оптимизации. М.: “Советское радио”. 1980. -   272 с.

7.   Карманов В.Г. Математическое программирование. М.: Наука. 1980. -  256 с.

8.   Юдин Д.Б., Гольштейн Е.Г.  Линейное программирование (теория, методы и приложения). М.: Наука. 1969. -  424 с.

9.   Данциг Дж. Линейное программирование (его применения и обобщения). М.: “Прогресс”. 1966. -  600 с.

10. Ермольев Ю.М. и др. Математические методы исследования операций. Киев. “Вища школа”. 1979. - 312 с.

11. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. М.: Наука. 1991. -  448 с.

Редактор И. А. Гусева

Компьютерная верстка Л. В. Климкович

Корректор Е. В.Карасева

© СПбГУП, 1999

© Гипермедийная версия: Махов А.М., 2001.