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

Задачи на оптимизацию: общие сведения

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

В зависимости от свойств функций задачи на оптимизацию можно разделить на два вида:

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

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

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

ЗЛП: формулировка, классификация

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

Общей ЗЛП называют задачу вида

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

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

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

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

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

ЗЛП: примеры

Задача о смесях

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

Задача о распределении ресурсов

Предприятие осуществляет выпуск n различных изделий, для производства которых требуется m различных видов ресурсов. Запасы используемых ресурсов ограничены и составляют соответственно b 1 , b 2 ,…, b m у.е. Кроме того, известны технологические коэффициенты a ij , которые показывают какое количество единиц i -го ресурса необходимо для производства одной единицы изделия j -го вида (). Прибыль, которую получает предприятие при реализации изделия j -го вида, составляет c j ден.ед. Необходимо составить план выпуска продукции, прибыль предприятия при реализации которого будет наибольшей.

Условия задач о смесях и распределении ресурсов часто записываются в виде таблиц.

Ресурсы	Потребности			Запасы
Ресурсы	B 1	…	B n	Запасы
A 1				b 1
…				…
A m				b m
Прибыль	c 1	…	c n

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

графический метод (в случае малого числа переменных в математической модели);
симплекс-метод (в случае числа переменных в математической модели больше двух).

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

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

В общем случае решение транспортной задачи выполняется в несколько этапов:

I этап: построение первоначального опорного плана;
II этап: проверка опорного плана на оптимальность;
III этап: уточнение опорного плана, если он не является оптимальным.

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

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

— для занятых клеток,
— для незанятых клеток.

Если план не является оптимальным, то выполняется построение цикла и перераспределение перевозок.

Заключение

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

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

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

Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 176 с.
Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 407 с.

Решение методов оптимизации на заказ

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

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

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

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

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

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

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

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

Модель экономической задачи оптимизации состоит из 3-х частей:

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

II. Система ограничений.

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

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

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

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

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

Кафедра статистики

и информационных систем

в экономике

Б2.Б4 методы оптимальных решений

Методические указания по дисциплине

Направление подготовки 080100 Экономика

Профили подготовки

Финансы и кредит

Налоги и налогообложение

Бухгалтерский учет, анализ и аудит

Экономика предприятий и организаций

Квалификация (степень) выпускника

Бакалавр

Составитель: ст.преподаватель Сагадеева Э. Ф.

Рецензент: к.с.н., доцент кафедры математики Гильманова Г. Х.

Ответственный за выпуск: зав. кафедрой статистики и информационных систем в экономике, к.э.н., доцент Аблеева А.М.

Введение
1. Геометрическая интерпретация задач линейного программирования
2. Симплексный метод решения задачи линейного программирования
3. Основные понятия теории двойственности
4.Двойственный симплекс-метод
5. Симплексный метод с искусственным базисом
6. Целочисленное программирование. Метод Гомори
7. Дробно-линейное программирование
8. Задачи нелинейного программирования. Метод множителей Лагранжа
9. Задания для самостоятельной работы
10. Тестовые задания
11. Задания для выполнения расчетно-графической работы и контрольной работы заочников
12. Фонд контрольных вопросов
13. Билеты к экзамену
14. Библиографический список

Введение

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

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

Сформулируем общую задачу линейного программирования.

Пусть дана система m линейных уравнений и неравенств с n переменными (система ограничений):

(1)

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

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

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

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

Каноническая	Стандартная	Общая
1) Ограничения
Уравнения	Неравенства	Уравнения и неравенства
2) Условия неотрицательности
Все переменные	Все переменные	Часть переменных
3) Целевая функция
(max или min )

Здесь: – переменные задачи;– коэффициенты при переменных в целевой функции;– коэффициенты при переменных в основных ограничениях задачи; – правые части ограничений.

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

Действительно, путь необходимо исследовать на экстремум линейную функцию

Z = С 1 х 1 +С 2 х 2 +... +С N x N

при линейных ограничениях

a 11 x 1 + a 22 x 2 + ... + a 1N Х N = b 1

a 21 x 1 + a 22 x 2 + ... + a 2N Х N = b 2

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

a М 1 x 1 + a М 2 x 2 + ... + a М N Х N = b М

Так как Z - линейная функция, то Z = С j , (j = 1, 2, ..., n), то все коэффициенты линейной функции не могут быть равны нулю, следовательно, внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть на границе области, но исследовать точки границы невозможно, поскольку частные производные являются константами.

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

Методы оптимальных решений

СОДЕРЖАНИЕ

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

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

Таблица 1.График самостоятельной работы по дисциплине «Методы оптимальных решений»

Содержание	Сроки сдачи	Критерии оценки
1.Изучение теоретического материала
2. Решение заданий кон-трольной работы	За 1,5 месяца до сессии	Каждое задание оцени-вается по десятибалль-ной системе
3. Подготовка к итоговой атт естации	Во время сессии

1. ВВЕДЕНИЕ. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

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

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

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

Под принятием решений в курсе «Методы оптимальных решений» понимают сложный процесс, в котором можно выделить следующие основные этапы:

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

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

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

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

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

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

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи (1-й этап); уточняется или строится заново математическая модель (2-й этап); решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

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

В математическом программировании можно выделить два направления.

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

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

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

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

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

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

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

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

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

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

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

2. ГЕОМЕТРИЧЕСКОЕ ИСТОЛКОВАНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования (ЗЛП):

найти вектор X = (x 1 ,x 2 ,...,x n) максимизирующий линейную форму

F = Σ c j x j → max (2.1)

J=1

и удовлетворяющий условиям:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

Линейная функция F называется целевой функцией задачи.

Перепишем эту задачу в векторной форме:

Найдем тах функции:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2.5)

x j ≥0 , j = 1,…,n (2.6)

где P 1 , …, P n и P 0 - m-мерные вектор столбцы, из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

B 1 a 11 a 12 a 1n

P 0 = (b 2) ; P 1 = (a 21) ; P 2 = (a 22) ;……. P n = (a 2n) ; (2.7)

… … … …

B n a m1 a m2 a mn

План X = (x 1 ,x 2 ,...,x n) называется опорным планом основной ЗЛП, если положительные коэффициенты х j стоят при линейно независимых векторах Р j .

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

Теорема

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

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

Выводы:

Непустое множество планов основной ЗЛП образует выпуклый многогранник;

Каждая вершина этого многогранника определяет опорный план;

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

Двумерный случай ЗЛП

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

F = c 1 x 1 + c 2 x 2 (2.8)

при условиях

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1,2) (2.10)

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

Для определения данной вершины построим линию уровня c 1 x 1 +c 2 x 2 =h, (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора С=(с 1 ,с 2) до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

Этапы решения ЗЛП геометрическим методом:

1. Построить прямые по уравнениям (2.9), (2.10).

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

3. Найти многоугольник решений.

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

5. Построить прямую c 1 x 1 +c 2 x 2 =h, проходящую через многоугольник решений.

6. Передвинуть прямую c 1 x 1 +c 2 x 2 =h в направлении вектора С.

7. Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Пример 1.

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

Таблица 2.1

В иды сырья	Нормы расхода сырья (кг) на одно изделие		Общее количество сырья (кг)
В иды сырья	А	В	Общее количество сырья (кг)
1	12	4	300
2	4	4	120
3	3	12	252
Прибыль одного изделия от реализации (руб.)	30	40

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

Решение:

х1 – выпуск изделий вида А

х2 – выпуск изделий вида В

Тогда ограничения задачи:

Общая прибыль от реализации изделий вида А и В составит: F = 30х 1 + 40x 2

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

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

Найдем координаты точки В – пересечения прямых:

Решив эту систему уравнений, получим: x 1 = 12 ; x 2 = 18

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

F max = 30·12+40·18 = 1080 руб.

Пример 2.

Решить ЗЛП

max(min)F = 2x 1 +3x 2 ;

Решение. Для построения области допустимых решений строим в системе x 1 Ox 2 соответствующие данным ограничениям-неравенствам граничные прямые:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2 ≥ 0.

Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяет ли эта пробная точка ограничению-неравенству. Если удовлетворяет, то данное неравенство выполняется в по-луплоскости, содержащей пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат О(0; 0). Для нашего примера область допус-тимых решений - множество точек четырехугольника АВСD (рис. 6).

Строим вектор с = (с 1 ; с 2) = (2; 3). Так как он необходим лишь для вы-яснения направления возрастания целевой функции, иногда для большей на-глядности удобно строить λс(λ > 0). Перпендикулярно к вектору с проводим линию уровня F=0. Параллельным перемещением прямой F=0 находим край-нюю точку В. в которой целевая функция принимает максимальное значение и точку А, в которой достигается минимальное значение.

Координаты точки В определяются системой

Откуда Fmax = F (A) = 32/9

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задачи 1.1-1.10 решить графически.

Задача со многими переменными

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

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

Сделать это можно, последовательно, исключая переменные или мето-дом Жордана-Гаусса. Рассмотрим метод Жордана-Гаусса.

Таблица 1

x 1

x 2

x 3

x 4

x 5

-1

(-3) 1 , (-1) 3,4

Таблица 2

x 2

-2

-1

-3

-4

-2

-1

-3

(2) 1 , (-1) 2 ,(1) 3

Таблица 3

x 2

x 4

-4

-1

-2

-1

-4

(-1) 2 , (1) 3 ,(2) 4

Таблица 4

x 5

x 2

x 4

-2

(-1) 2 , (1) 3 ,(2) 4

Отбросим в уравнениях-ограничениях неотрицательные разрешенные неизвестные

x 2 , x 4 , x 5 и заменим знак равенства знаками неравенства, по-лучим вспомогательную задачу линейного программирования с двумя переменными:

F (x) = 2 x 3 +2 → max

F (x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

F max = 2 при x 1 = 0; x 3 = 0

3. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

3.1. Геометрическая интерпретация симплексного метода

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

Симплексный метод состоит в:

1) определении первоначального допустимого базисного решения задачи;

2) переходе к лучшему решению;

3) проверке оптимального допустимого решения.

3.2. Табличная интерпретация симплексного метода

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

Найти оптимальное решение

X = (x 1 ,x 2 ,...,x n) (3.1)

удовлетворяющее системе ограничений (уравнений)

Σa ij x j = b i (i=1,m) (3.2)

j=1

и условиям x j ≥ 0 (j=1,n)

и дающее экстремальное значение целевой функции

Z(x) = Σ c j x j (3.3)

j=1

Пусть найдено первоначальное неотрицательное базисное решение системы (3.2), где х 1, х 2 , х 3 … х m - базисные неизвестные, а х m+1 , x m+2 , …, x n – свободные неизвестные.

Тогда система (3.2) превращается в разрешенную систему

(3.4)

Данной системе соответствует неотрицательное базисное решение вида

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

Подставим полученное решение в целевую функцию

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

и преобразуем ее таким образом, чтобы она зависела только от свобод-ных неизвестных х m+1, х m+2 , … х n

Все базисные неизвестные х 1, х 2 , х 3 … х m выразим через свободные х m+1, х m+2 , … х n и подставим в целевую функцию.

Тогда целевая функция примет вид (3.6)

Введем понятие оценки Δ j свободных неизвестных

(3.7)

Тогда целевая функция примет вид

(3.8)

Введем в рассмотрение векторы C = (c 1 , c 2 , …, c m) и B = (a 1j , a 2j , …, a mj) (j=m+1,n), тогда равенство (3.7) можно записать в векторной форме

Δ j =CB j -c j (3.9)

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

Результаты проведенных преобразований, записанные виде системы, можно занести в следующую симплексную таблицу:

Б.Н.	C	B	c 1	c 2	...	c m	c m+1	...	c j	...	c n
Б.Н.	C	B	x 1	x 2	...	x m	x m+1	...	x j	...	x n
x 1	c 1	β 1	1	0	...	0	a 1(m+1)	...	a 1j	...	a 1n
x 2	c 2	β 2	0	1	...	0	a 2(m+1)	...	a 2j	...	a 2n
...	...	...	...	...	...	...	...	...	...	...	...
x m	c m	β m	0	0	...	1	a m(m+1)	...	a mj	...	a mn
L(X)	Δ j ≥0	Δ 0	0	0	...	0	Δ m+1	...	Δ j	...	Δ n

первом столбце записаны базисные неизвестные x 1 ,x 2 , …, x m ; в столбце C записаны коэффициенты из целевой функции, соответствующие этим базисным неизвестным; в столбце B - свободные члены уравнений системы, совпадающие с положительными компонентами первоначального неотрицательного базисного решения X 0 . Под неизвестными x 1 ,x 2 , …, x n в столбцах записаны коэффициенты из системы.

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

В оценочной строке неравенство Δ j ≥0 и означает критерий оптимальности опорного плана.

Алгоритм решения ЗЛП симплекс-методом.

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Выяснить, имеется ли хотя бы одно отрицательное число Δ j

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

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

5. По формулам (3.7) – (3.9) определить положительные компоненты нового опорного плана, коэффициенты разложения векторов Р j по векторам нового базиса и числа. Все эти числа записываются в новой симплекс- таблице.

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

Пример 3.1.

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

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

Решение:

Составим математическую модель. Обозначим:

х 1 – выпуск изделий вида А;

х 2 – выпуск изделий вида В;

х3 – выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет:

F = 9x 1 +10x 2 +16x 3

По экономическому содержанию переменные х 1 , х 2 , х 3 могут принимать только неотрицательные значения:

x 1 ,x 2 ,x 3 ≥0

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

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

Запишем преобразованную систему уравнений в векторной форме:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

где

Поскольку среди векторов Рj имеется три единичных вектора, то дляданной задачи можно записать опорный план Х=(0, 0, 0, 360, 192, 180) определяемый системой единичных векторов Р 4 , Р 5 , Р 6 , которые образуют базис трехмерного пространства.

Составляем симплексную таблицу I итерации и подсчитываем значения F 0 , z j -c j .

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

F 0 = (С,P 0)=0; z 1 =(С,P 1)=0; z 2 =(С,P 2)=0; z 3 =(С,P 3)=0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

Для векторов базиса z j -c j = 0 (j=4,5,6).

Максимальное отрицательное число Δ j стоит в 4-ой строке столбца Р 3 . Следовательно, в базис введем вектор Р 3 . Определим вектор, подлежащий исключению из базиса, для этого находим Θ 0 = min(b i /a ij) для a i3 >0 т.е. Θ = min (360/12 ; 192/8; 180/3) =192/8 =24.

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

Следовательно, вектор Р 5 подлежит исключению из базиса. Столбец вектора Р 3 и 2-я строка являются направляющими.

Составим таблицу II итерации. Сначала заполняем строку вектора, вновь введенного в базис, т.е. направляющую строку 2. Элементы этой строки получаются путем деления соответствующих элементов таблицы 1 наразрешающий элемент (т.е. 8). При этом в столбец С б записываем коэффи циент С 3 =16, стоящий в столбце вводимого в базис вектора Р 3

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

Вычислим элементы таблицы II, стоящие в столбце Р 0 .

Первый элемент - находим три числа

1) число, стоящее в т. 1 на пересечении столбца Р0 и 1-ой строки (360);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 1-ой строки (12);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

360-12·24 = 72

Второй элемент был вычислен ранее (Θ 0 = 192/8 =24)

Третий элемент -

1) число, стоящее в т. 1 на пересечении столбца Р0 и 3-ой строки (180);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 3-ой строки (3);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

180-3·24 =108

Значение F 0 в 4-ой строке этого же столбца можно найти двумя спосо бами:

1) по формуле F 0 =(C,P 0) = 0·72+16·24+0·108 = 384;

2) по правилу треугольника:

Вычислим элементы вектора Р 1 т.2. Первые два числа берем из столб цов Р 1 и Р 3 т.1,

а третье число – из т.2 на пересечении 2-ой строки и столбца Р1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Число z 1 -c 1 в 4-й строке столбца вектора P 1 таблице 2

можно найти двумя способами:

1) по формуле z 1 -с 1 =(C,P 1)-c 1 имеем:

0·9+16·3/ 4+0·11/ 4-9 =3

2) по правилу треугольника получим:

-9-(-16) 3/ 4 = 3

Аналогично находим элементы столбца вектора P 2 .

Элементы столбца вектора Р 5 вычисляем по правилу треугольника.

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

При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0;12 и 1/8. Следовательно, искомый элемент равен

0 – 12 (1/8) = -3/2.

Элемент, стоящий в 3-й строке данного столбца, равен

0 - 3 (1 /8) = -3/8.

По окончании расчета всех элементов таблица II в ней получены но вый опорный план и коэффициенты разложения векторов Р j через базисные векторы P 4 , P 3 , P 6 и значения F 0 " Δ j ".

Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108).

Найденный на II итерации план задачи не является оптимальным.

этой строки стоит отрицательное число – 2. Это видно и из 4-й строки таблицы 2, поскольку в столбце вектора P 2 .

Значит, в базис следует ввести вектор P 2 , т. е. в новом плане следует предусмотреть выпуск изделий В.

При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется min (b i "/a i 2") для a i2 ">0 т.е. находим Θ 0 = min(72/9; 24·2/1; 108·2/3) = 72/9=8.

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

Составим таблицу для III итерации.

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

При этом в столбце С б данной строки записываем с 2 =10.

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

В результате в таблице III получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов Р j через базисные векторы P 1 , P 2 и P 3 соответствующие значения F 0 "" и Δ j .

Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, таблицы 3 . В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и F max =400.

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 €.

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

Пример 3.2

Заполнить первоначальную симплексную таблицу для следующей ЗЛП:

Решение:

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

-во вторую строку запишем неизвестные x 1 ,x 2 , …, x 5 ;

-в первой строке над ними – соответствующие коэффициенты 3, -2, 1,4,-1 из целевой функции;

-под неизвестными x 1 ,x 2 , …, x 5 , заполним столбцы, составленные из соответствующих коэффициентов левых частей уравнений исходной системы;

-в столбец запишем свободные члены уравнений 3,1,5;

-в первый столбец Б.п. поместим неизвестные x 2 ,x 3 , x 5 , так как под ними стоят единичные столбцы, и поэтому их будем считать базисными; базисные неизвестные располагаются в таком порядке, чтобы единицы в столбцах находились на пересечении одинаковых неизвестных;

-в столбец запишем коэффициенты -2,1,-1, из целевой функции при выбранных базисных неизвестных x 2 ,x 3 , x 5 ;

-заполним оценочную строку следующим образом: под столбцом B поместим число Δ 0 , вычисленное по формуле (3.5); под базисными неизвестными x 2 ,x 3 , x 5 - нули, которые можно получить и из равенства (3.9); под свободными переменными x 1 , x 4 - запишем значения, полученные из равенства (3.9).

Результаты выполнения этих действий запишем в следующую таблицу:

Выберем в качестве разрешающего столбец х 4 , как самый «плохой» (ему соответствует наибольшая по модулю отрицательная оценка). Далее введем разрешающую строку следующим образом: для положительных коэффициентов столбца х 4 вычислим отношения b i /a i4 запишем их в графу θ.

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

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

Таким образом, уже в таблице второго шага критерий оптимальности выполнен. Мы получили оптимальный план Х(0;0;11/2;3/2;13/2), max L(X) =5.

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Краткий курс лекций

Саратов 2012

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

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

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

УНИВЕРСИТЕТ имени Н. И.ВАВИЛОВА»

_____________________________________________________

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Краткий курс лекций

Саратов 2012

УДК 517(075.8)

ББК 22.161.

Издание осуществлено при поддержке

программы TEMPUS JP, грант Европейской

Комиссии 159188-TEMPUSPL-TEMPUS-JPCR

Терехова оптимальных решений. (краткий курс лекций): Учебное пособие /сост.: , – Саратов: Изд – во ФГБОУ ВПО «Саратовский ГАУ»., 201с.

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

Предназначено для студентов направления подготовки 110100.62 Агрохимия и агропочвоведение (профиль Агроэкология), 280100.68 «Природообустройство и водопользование», для бакалавров направления “Экономика предприятий и организаций” профиль“ Экономика предприятий и организаций (агропромышленного комплекс а)”, “Бухгалтерский учёт и аудит”, “Пищевая промышленность”, “Финансы и кредит”, а также для магистров, аспирантов, преподавателей, научных сотрудников.

ISBN , 2012

ВВЕДЕНИЕ

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

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

ЛЕКЦИЯ 1

Исследование операций. Экономико-математические модели.

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

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

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

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

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

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

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

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

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

https://pandia.ru/text/78/095/images/image004_15.gif" width="529" height="371">

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

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

Приведем следующую общую классификацию ЭММ .

По целевому назначению ЭММ делятся на теоретико-аналитические и прикладные. Теоретико-аналитические ЭММ предназначены для исследования общих свойств и закономерностей экономических процессов. Прикладные ЭММ используются при решении конкретных экономических задач .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЛЕКЦИЯ 2

Балансовые модели. Модель Леонтьева многоотраслевой экономики.

Продуктивные модели.

В экономике существует баланс между отдельными отраслями. Рассмотрим простой вариант модели межотраслевого баланса – модель «затраты-выпуск».

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

xi ‑ общий объем продукции отрасли i за плановый год ‑ так называемый валовой выпуск отрасли i ;

xij ‑ объем продукции отрасли i, расходуемый отраслью j в процессе производства;

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

Указанные величины сведем в таблицу.

Производственное

потребление

Конечное

Потребление

Балансовый характер этой таблицы выражается в том, что при любом выполняется соотношение

означающее, что валовой выпуск xi расходуется на производственное потребление, равное https://pandia.ru/text/78/095/images/image011_6.gif" width="64" height="57">остаются постоянными в течение ряда лет, что объясняется примерным постоянством используемой технологии производства.

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

https://pandia.ru/text/78/095/images/image014_8.gif" width="23" height="28 src="> называют коэффициентами прямых материальных затрат или коэффициентами материалоемкости . Они показывают сколько необходимо единиц продукции отрасли i для производства единицы продукции отрасли j , если учитывать только прямые затраты .

https://pandia.ru/text/78/095/images/image016_7.gif" width="85" height="24 src=">, (3)

https://pandia.ru/text/78/095/images/image018_6.gif" width="15" height="17"> называется вектором валового выпуска , вектор ‑ вектором конечного потребления , а матрица А ‑ матрицей прямых затрат. Соотношение (3) называется уравнением линейного межотраслевого баланса. Вместе с изложенной интерпретацией матрицы А и векторов https://pandia.ru/text/78/095/images/image019_9.gif" width="16" height="23 src="> это соотношение называют также моделью Леонтьева.

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

Задавая для каждой отрасли i валовой выпуск продукции можно определить объемы конечного потребления каждой отрасли https://pandia.ru/text/78/095/images/image023_7.gif" width="101" height="25 src=">,

где Е – единичная матрица;

Задавая величины конечного потребления каждой отрасли https://pandia.ru/text/78/095/images/image021_7.gif" width="19" height="25">:

где – матрица, обратная к матрице https://pandia.ru/text/78/095/images/image020_9.gif" width="15" height="19"> и неотрицательны (это вытекает из экономического смысла А , https://pandia.ru/text/78/095/images/image019_9.gif" width="16" height="23 src=">). Для краткости будем записывать это так: .

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

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

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

Сформулируем критерии продуктивности матрицы https://pandia.ru/text/78/095/images/image028_5.gif" width="45" height="20 src="> продуктивна тогда и только тогда, когда матрица существует и неотрицательна.

Критерий II . Матрица https://pandia.ru/text/78/095/images/image025_6.gif" width="72" height="28 src="> в матричный ряд

В соотношении (4) матрицы называются матрицами коэффициентов косвенных затрат 2-го, 3-го и т. д. порядков. Их сумма образует матрицу коэффициентов косвенных затрат

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

Таким образом, из соотношений (4) и (5) имеем

т. е. матрица коэффициентов полных материальных затрат включает в себя матрицы коэффициентов прямых и косвенных затрат.

Рассмотрим примеры.

Пример 1. Исследовать на продуктивность матрицу

https://pandia.ru/text/78/095/images/image037_4.gif" width="48 height=19" height="19">:

https://pandia.ru/text/78/095/images/image039_4.gif" width="577" height="143 src=">

алгебраические дополнения для элементов матрицы

https://pandia.ru/text/78/095/images/image041_4.gif" width="189 height=55" height="55">;

https://pandia.ru/text/78/095/images/image043_3.gif" width="220 height=55" height="55">;

https://pandia.ru/text/78/095/images/image045_3.gif" width="221 height=55" height="55">;

https://pandia.ru/text/78/095/images/image047_5.gif" width="209" height="55 src=">;

https://pandia.ru/text/78/095/images/image049_3.gif" width="468" height="84 src=">

Полученная матрица неотрицательна и по Критерию I исходная матрица А продуктивная.

Пример 2. Для матрицы А коэффициентов прямых затрат из примера 1 и вектора конечного потребления

https://pandia.ru/text/78/095/images/image051_3.gif" width="80" height="84 src=">

а) Вектор валового выпуска вычислим по формуле

https://pandia.ru/text/78/095/images/image053_3.gif" width="483" height="84 src=">

б) Матрицу косвенных затрат В найдем из соотношения (2.6):

https://pandia.ru/text/78/095/images/image055_3.gif" width="409" height="84 src=">

Таким образом, при увеличении вектора конечного потребления на https://pandia.ru/text/78/095/images/image056_3.gif" width="88" height="84">.

ЛЕКЦИЯ 3,4,5

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

Модели линейного программирования.

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

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

Сформулируем в общем виде ЗМП:

https://pandia.ru/text/78/095/images/image058_3.gif" width="296" height="79"> (8)

https://pandia.ru/text/78/095/images/image060_3.gif" width="123" height="25"> – целевая функция , условия (8) – специальные ограничения , условия (9) – общие ограничения ЗМП.

Точку , координаты которой удовлетворяют ограничениям (8) и (9), называют допустимым решением ЗМП.

Множество всех допустимых решений ЗМП называют допустимым множеством .

Допустимое решение , удовлетворяющее соотношению (7), называют оптимальным решением ЗМП.

Если в ЗМП целевая функция и функции , – линейные, то имеем общую задачу линейного программирования (ЗЛП):

https://pandia.ru/text/78/095/images/image065_3.gif" width="356" height="79 src="> (11)

https://pandia.ru/text/78/095/images/image066_3.gif" width="336" height="25 src=">;

- стандартная ЗЛП, включающая в качестве ограничений (11) только неравенства, т. е.

https://pandia.ru/text/78/095/images/image068_3.gif" width="20" height="25">, и , из которого можно наладить производство двух видов товаров: https://pandia.ru/text/78/095/images/image072_2.gif" width="20" height="25 src=">. Запасы сырья, норма его расхода на производство единицы товаров, а также прибыль от реализации единицы каждого товара приведены в таблице 1 (цифры условные).

Таблица 1