close

Вход

Забыли?

вход по аккаунту

Сьогодні вашій увазі тому, пише gazeta.ua.;pdf

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное учреждение
высшего профессионального образования
«Казанский (Приволжский) федеральный университет»
Елабужский институт
Факультет экономики и управления
Кафедра экономики и менеджмента
Ибатуллин Ринат Ривкатович
Экономико-математические методы в менеджменте
Краткий конспект лекций
Казань – 2014
Направление: 080200.62 «Менеджмент»
Учебный план: «Менеджмент» (очное, 2011)
Дисциплина: «Экономико-математические методы в менеджменте»
(бакалавриат, 2 курс, очное обучение).
Количество часов: 108 ч. (в том числе лекции – 22, практические занятия – 32, самостоятельная работа – 54), форма контроля: экзамен.
Аннотация: Курс посвящен основам математического аппарата, необходимого для решения теоретических и практических управленческих задач.
Основное внимание в курсе уделяется методам эконометрического и факторного анализа для контроля экономической ситуации и обоснования вариантов
перспектив развития предприятия.
Темы:
1. Предмет и задачи курса «Экономико-математические методы в менеджменте».
2. Графический метод решения задач линейного программирования.
Математическая модель решения задачи ЛП.
3. Симплекс-метод решения задач ЛП.
4. Метод искусственного базиса.
5. Двойственные задачи ЛП.
6. Математическая модель транспортной задачи.
7. Целочисленное программирование.
8. Элементы теории нелинейного динамического о программирования.
Ключевые
слова:
исследование
операций,
ция, модель, моделирование, линейное программирование
опера-
Автор курса: Ибатуллин Ринат Ривкатович, доцент кафедры информатики и дискретной математики, кандидат физико-математических наук, e-mail:
[email protected]
Дата начала эксплуатации: 1 октября 2014 г.
URL:
http://tulpar.kfu.ru/course/view.php?id=2100
Содержание
Тема 1. Предмет и задачи курса «Экономико-математические методы в
менеджменте» .............................................................................................................. 4
Лекция 1........................................................................................................................ 4
Тема 2. Линейное программирование ....................................................................... 9
Лекция 2........................................................................................................................ 9
Тема 3. Симплекс-метод решения задач ЛП .......................................................... 14
Лекция 3...................................................................................................................... 14
Тема 4. Метод искусственного базиса .................................................................... 22
Лекция 4...................................................................................................................... 22
Тема 5. Двойственные задачи ЛП ............................................................................ 26
Лекция 5...................................................................................................................... 26
Тема 6. Математическая модель транспортной задачи ......................................... 29
Лекция 6...................................................................................................................... 29
Тема 7. Целочисленное программирование ........................................................... 33
Лекция 7...................................................................................................................... 33
Тема 8. Элементы теории нелинейного динамического программирования...... 37
Лекция 8...................................................................................................................... 37
3
Тема 1. Предмет и задачи курса «Экономико-математические методы в
менеджменте»
Лекция 1
Аннотация. Данная тема раскрывает цели и задачи курса. Знакомит с
понятиями модели и моделирования, рассматриваются основные виды математического моделирования и процессы экономико-математического моделирования.
Ключевые слова. Модель, моделирование, исследование операций,
символическая модель, математическая модель, описательные модели, оптимизационные модели, эвристика, имитационное моделирование.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. Н.Ш. Кремер Исследование операций в экономике. 2007г.
2. Исследование операций в экономике. Под редакцией проф. Н.Ш. Кремера. М., «Банки и биржи», ЮНИТИ, 1997.
3. Хэмди А. Таха. Введение в исследование операций. Издательский дом
«Вильямс»,М., С-П, Киев, 2001.
Глоссарий
Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.
Модель – система, способная замещать оригинал так, что ее изучение
дает новую информацию об оригинале.
Моделирование – это процесс построения и исследования модели, способной заменить реальную систему и дать о ней новую информацию.
Символическая модель описывает структуру и функции оригинала с
помощью символов и соотношений между ними, выражающих определенные
зависимости, присущие оригиналу.
4
Математическая модель представляет собой систему математических
и логических соотношений, описывающих структуру и функции реальной системы.
Описательные модели экономических систем представляют собой
формализованную с помощью математического аппарата экономическую задачу и используются для более глубокого изучения состояния системы и взаимосвязи ее элементов.
Оптимизационные модели отражают в математической форме смысл
экономической задачи. Отличительной особенностью этих моделей является
наличие условия нахождения оптимального решения (критерия оптимальности), которое записывается в виде функционала.
Эвристика (в переводе с греческого - нахожу, придумываю, открываю) это совокупность неформальных методов решения задач (эвристических методов), основанных на прошлом опыте, интуиции решающего. Эвристические методы в общем случае не гарантируют получение наилучшего решения, поскольку они опираются не на доказательства, а на так называемые правдоподобные рассуждения.
Имитационное моделирование – экспериментирование с моделью реальной системы, в частности, вычислительный эксперимент, проводимый с помощью математической модели путем изменения различных исходных предпосылок.
Вопросы для изучения:
1.
2.
3.
4.
Цель и задачи исследования операций
Модели и моделирование
Процесс экономико-математического моделирования
Общая постановка задачи исследования операций
Цель и задачи исследования операций
Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами (система - это совокупность
взаимосвязанных, взаимодействующих элементов (людей, машин ...), выполняющих определенную задачу).
Управление любой системой реализуется как процесс, подчиняющийся
определенным закономерностям. Их знание помогает определить условия, не5
обходимые и достаточные для осуществления данного процесса. Для этого все
параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Т. о., цель исследования - количественное
обоснование принимаемых решений по организации управления.
При решении конкретной задачи управления применение методов ИО
предполагает:
 построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;
 изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия.
Для применения количественных методов исследования требуется
построить математическую модель операции. Составление модели операции
требует понимания сущности описываемого явления и знания математического
аппарата.
Модели и моделирование
В процессе создания систем приходится проводить многочисленные
исследования, эксперименты и расчеты, связанные с оценкой качества функционирования систем, с выбором лучшего варианта для ее создания. Выполнять
их непосредственно на реальной системе очень сложно, иногда занимает много
времени и экономически невыгодно. Существуют системы (экономика страны),
на которых просто невозможно ставить эксперименты с познавательной целью.
Значительно проще и дешевле создать модель системы и проводить на ней эксперименты.
Под моделированием понимается процесс построения и исследования
модели, способной заменить реальную систему и дать о ней новую информацию.
Модели, используемые на практике, условно можно разделить на два
типа: физические и символические.
Среди математических моделей важное место занимают ЭММ, представляющие собой математическое описание экономических процессов и явлений. Большинство ЭММ включает в себя систему уравнений и неравенств, состоящих из набора переменных и параметров. Переменные величины характеризуют, например, объем производимой продукции, капитальных вложений,
перевозок и т.п., а параметры - нормы расхода сырья, материалов, времени на
производство определенной продукции. Практически в каждой модели можно
выделить две группы переменных: 1) внешние переменные - их значения опре6
деляются вне данной модели и считаются в данной модели заданными; 2) внутренние переменные, значения которых определяются в результате исследования данной модели.
Выделяют описательные и оптимизационные ЭММ, которые используются на любых уровнях народнохозяйственной иерархии.
Процесс экономико-математического моделирования
Этот процесс состоит из нескольких взаимосвязанных этапов. Разбиение на этапы и выделение на каждом этапе присущих ему процессов условно:
на одном из выделенных этапов возможно совмещение процессов, относящихся
к разным этапам.
Первый этап - постановка задачи.
Данный этап начинается с выработки цели исследования. Для конкретной экономической системы цели исследования могут быть различными,
например, для предприятия можно задаться целью составить оптимальный план
выпуска продукции или перевозок грузов, либо найти оптимальный вариант
раскроя исходных материалов и т.д. Исходя из цели исследования необходимо
провести подробный анализ системы, выявить ее структуру и функции, изучить
особенности.
Второй этап - построение математической модели
На этом этапе проводится формализация задачи - построение математических зависимостей в виде уравнений, неравенств, функций и т.п. Формализованную с помощью математического аппарата запись экономической задачи
называют моделью задачи.
Третий этап - получение решения с помощью построенной модели.
Основные задачи данного этапа. Первая задача - сбор и обработка необходимой для модели достоверной исходной информации, определение числовых значений параметров и внешних переменных. На практике не всегда
удается собрать требуемую информацию, что приводит к невозможности использования модели в полученном виде. Тогда приходится возвращаться к постановке задачи и приспосабливать ее к имеющимся исходным данным.
Четвертый этап - применение полученных с помощью модели результатов на практике.
Сложность экономических процессов и явлений, другие особенности
экономических систем затрудняют не только построение моделей, но и проверку их адекватности - соответствия ЭММ рассматриваемой экономической системе, цели ее исследования. Любая модель любой системы предполагает абстрагирование от некоторых реальных свойств объекта и отражает лишь основ7
ные его свойства. На данном этапе проверяется, насколько принятые допущения правомерны и, следовательно, применима ли построенная модель для исследования моделируемой системы. В случае необходимости модель корректируется.
Общая постановка задачи исследования операций
Все факторы, входящие в описание операции, можно разделить на две
группы:
 постоянные факторы (условия проведения операции), на которые мы
влиять не можем. Обозначим их через 1, 2 ,... ;
 зависимые факторы (элементы решения) x1,x2,..., которые в известных
пределах мы можем выбирать по своему усмотрению.
Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z
можно записать в виде
Z = f(x1,x2,..., 1 , 2 ,...)
Все модели исследования операций могут быть классифицированы в
зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов.
Математическое программирование - область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с
ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой нужно найти в условиях
экономических возможностей, называют целевой, показателем эффективности
или критерием оптимальности. Экономические возможности формализуются
в виде системы ограничений. Все это составляет математическую модель.
Математическая модель задачи - это отражение оригинала в виде
функций, уравнений, неравенств, цифр и т.д.
Если критерий эффективности Z = f(x1,x2,...,xn) представляет линейную
функцию, а функции i ( x1 , x2 ,..., xn ) в системе ограничений (1) также линейны, то
такая задача является задачей линейного программирования. Если, исходя из
содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем
задачу нелинейного программирования. В частности, если указанные функции
8
обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.
Если в задаче математического программирования имеется переменная
времени и критерий эффективности (1.2) выражается не в явном виде как функция переменных, а косвенно - через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.
Из перечисленных методов математического программирования наиболее распространенном и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.
Контрольные вопросы:
1. Назовите цели и задачи исследования операций.
2. Дайте определения понятий модели и моделирование, экономикоматематические модели.
3. Назовите основные разделы математического программирования.
Дайте их краткую характеристику.
Тема 2. Линейное программирование
Лекция 2
Аннотация. Данная тема раскрывает ряд вопросов, посвященных линейному программированию как одному из разделов математического программирования; в частности, формулирует основные виды задач линейного
программирования, раскрывает отличия данных задач от классических задач
математического анализа; знакомит с различными формами записи данных задач, осуществляет их постановку и исследование структуры.
Ключевые слова. Математическое программирование, целевая функция, экстремум функции, сравнительные оценки, нелинейное программирование, линейное программирование, оптимальный план, задача линейного программирования.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
9
Источники информации:
1. П.Н. Коробов. Математическое программирование и моделирование экономических процессов. – М.: ДНК, 2006. – 376 с.
2. Камилл Ахметов. Практика управления проектами. – М.: Русская
Редакция, 2004. – 272 с.
3. В.А. Охорзин. Оптимизация экономических систем. Примеры и алгоритмы в среде Mathcad. – М.: Финансы и статистика, 2005. – 144 с.
4. Г.В. Шадрина. Управленческий анализ. – М.: Альфа-Пресс, 2008. –
320 с.
5. В.В. Покровский. Математические методы в бизнесе и менеджменте. – М.: Бином. Лаборатория знаний, 2008. – 112 с.
6. А.Р. Урубков, И.В. Федотов. Методы и модели оптимизации управленческих решений. – М.: Дело АНХ, 2011. – 240 с.
Глоссарий
Математическое программирование – это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограничениями. В отличие от классической математики, математическое программирование занимается математическими методами решения задач нахождения
наилучших вариантов из всех возможных.
Целевая функция – функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.
Экстремум функции – максимальное или минимальное значение функции на заданном множестве.
Нелинейное программирование– случай математического программирования, в котором целевой функцией или ограничением является нелинейная
функция.
Линейное программирование-–линейное планирование, т.е. получение
оптимального плана - решения в задачах с линейной структурой. Оптимальный план-Наилучшее распределение ресурсов в задаче математического программирования.
Задача линейного программирования – математическая дисциплина,
посвящѐнная теории и методам решения экстремальных задач на множествах мерного векторного пространства, задаваемых системами линейных уравнений
и неравенств.
10
Вопросы для изучения:
1. Общая задача линейного программирования
2. Линейное программирование в экономике
3. Геометрическая интерпретация и графическое решение ЗЛП
Общая задача линейного программирования
Общей задачей линейного программирования (ОЗЛП) называют задачу:
Максимизировать (минимизировать) функцию
n
F  cjxj
(2.1)
j 1
при
n
 a ij x j  bi (i  1, m1 ),
 j 1
n
 a ij x j  bi (i  m1  1, m2 ),
 j 1
 n
 a ij x j  bi (i  m 2  1, m)
 j 1
 x  0( j  1, n ),
1
 j
 x  произвольные( j  n  1, n),
1
 j


ограничениях:
(2.2)
где cj, aij, bi -заданные действительные числа, (2.1) - целевая функция,

(2.2) - ограничения, X  ( x1, x2 ,...,xn ) - план задачи.
Экономическая интерпретация модели ЛП состоит в следующем.
Моделируемая система характеризуется наличием нескольких видов «производственной деятельности» j ( j  1, n) , для осуществления которых требуются
имеющиеся в ограниченном количестве различные ресурсы bi , i  1, m. Расход iго ресурса на единицу продукта j-го вида производственной деятельности равен
aij. В свою очередь при таком потреблении результат j-го вида производственной деятельности для единицы соответствующего продукта (удельная стоимость или прибыль) характеризуется величиной cj.
11
Линейное программирование в экономике
1. Задача о наилучшем использовании ресурсов. Пусть некоторая произ-
водственная единица (цех, завод, фирма и т.д.), исходя из конъюнктуры рынка,
технических или технологических возможностей и имеющихся ресурсов, может
выпускать n различных видов продукции (товаров) Пj, j  1, n. Предприятие при
производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т.д.).
Математическая модель задачи имеет следующий вид:
n
Z   c j x j  max
j 1
n
a x
ij
j 1
 bi , (i  1, m),
j
(2.4)
x j  0, ( j  1, n).
2. Задача о смесях. В различных отраслях народного хозяйства возника-
ет проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего
определенными свойствами. К этой группе задач относятся задачи формировании минимальной потребительской продовольственной корзины, составлении
кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т.д. Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными
свойствами при наименьших затратах на исходные сырьевые материалы.
Математическая модель задачи имеет следующий вид:
n
Z   c j x j  min
j 1
n
a x
j 1
ij
j
 bi , (i  1, m),
x j  0, ( j  1, n).
12
(2.5)
3. Задача о раскрое материалов. Сущность задачи об оптимальном рас-
крое состоит в разработке таких технологически допустимых планов раскроя,
при которых получается необходимый комплект заготовок, а отходы ( по длине,
площади, объему, массе или стоимости) сводятся к минимуму.
Математическая модель задачи имеет следующий вид:
n
l
 c
j 1 k 1
l
x
k 1
k
j 1 k 1
x jk  min
jk
 d j , j  1, n,
jik
x jk  bi , i  1, m,
l
 a
jk
x jk  0, j  1, n; k  1, l .
Вместо критерия минимизации себестоимости в задаче может быть
взят, например, критерий минимизации отходов. В этом случае в условии
должно быть задано количество отходов, получаемых при каждом способе раскроя для единицы материала каждого вида.
Геометрическая интерпретация и графическое решение ЗЛП
Геометрическая интерпретация экономических задач дает возможность
наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно
решить графически.
Пусть дана задача:
Z=c1x1+c2x2
(2.6)
a11 x1  a12 x2  b1
a x  a x  b
 21 1 22 2
2

...........................
am1 x1  am 2 x2  bm
(2.7)
13

max
x1  0, x2  0
(2.8)
Дадим геометрическую интерпретацию элементов этой задачи.
Введем на плоскости декартову прямоугольную систему координат
x1Ox2 и сопоставим каждой паре чисел (x1,x2) точку плоскости с координатами
x1 и х2. Выясним сначала, что представляет собой множество точек, соответствующих допустимым решениям данной задачи.
Рассмотрим одно линейное неравенство a11x1  a12 x2  b1 .
Оно определяет на плоскости одну из двух полуплоскостей, на которые
прямая a11x1  a12 x2  b1 разбивает плоскость (сторона в которой располагается
полуплоскость от прямой, указывается штриховкой).
Убедиться в том, с какой стороны от прямой лежит полуплоскость,
точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости,
соответствующей данному неравенству. В противном случае неравенству соответствует другая плоскость.
Контрольные вопросы:
1. В чем особенность задачи ОЗЛП?
2. Как привести задачу ЛП к каноническому виду?
3. Может ли в области допустимых решений быть одна точка?
Тема 3. Симплекс-метод решения задач ЛП
Лекция 3
Аннотация. В данной теме раскрыто понятие симплекс-метода, рассматривается алгоритм применения симплекс-метода.
Ключевые слова. Базисное решение, симплекс-метод, симплексные
таблицы.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
14
1.
2.
М.,2008.
3.
Н.Ш. Кремер Исследование операций в экономике. 2007г.
Г.И. Просветов Математические методы и модели в экономике.
3. Вентцель Е.С. Исследование операций. М., Наука, 1980.
Глоссарий
Базисное решение – термин линейного программирования, одно из допустимых решений, находящихся в вершинах области допустимых решений,
либо (если линия уровня параллельна одному из отрезков границы области).
Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.
Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путѐм перебора вершин выпуклого многогранника в
многомерном пространстве. Метод был разработан советским математиком
Канторовичем Л. В. в 1937 году.
Симплексная таблица – основной элемент вычислительной процедуры
симплекс – метода.
Вопросы для изучения:
1. Понятие о симплекс-методе решения задач ЛП
2. Алгоритм симплекс-метода
3. Пример решения задач ЛП симплекс-методом
Понятие о симплекс-методе решения задач ЛП
Стандартная форма задачи ЛП максимизации:
(1): max z= max(c1 x1 +…+ cn xn )
(2): ai1 x1 +…+ ain xn ≤ bi , i =1, m
(3): x j ≥ 0, j =1, n
В
матричном и векторном виде эта задача может быть записана так
max z = max
CX
max z = max CX
15
AX ≤ B
X≥0
⇔
Ai X ≤ bi , i=1, m
X≥0
Каноническая форма задачи ЛП максимизации:
(1) : max z = max(c1 x1 +…+ cn xn )
(2): ai1 x1+…+ ain xn = bi , i =1, m
(3): x j ≥ 0, j =1, n
В
матричном и векторном виде эта задача может быть записана так
max z = max CX
AX= B
X≥0
max z = max CX
⇔ Ai X= bi , i=1, m
X≥0
Алгебраические основы симплекс-метода
Множество допустимых решений для канонической задачи
Рассмотрим каноническую задачу ЛП максимизации
max z = max CX
AX = B
X≥0
Множество допустимых решений задачи имеет вид
M = (X AX = B, X ≥ 0)
называется многогранным и является выпуклым и замкнутым.
Понятие решения для системы линейных уравнений (СЛУ), зависящего от множества индексов
Пусть S ⊂(1,2, , n) - множество индексов (подмножество множества номеров столбцов матрицы) и пусть дана система линейных уравнений
AX = B ⇔∑n A j x j = B
Говорят, что решение X = (x1 , , xn ) СЛУ зависит от множества индек16
сов S, если
x j = 0, j∉S .
Понятие базисного решения СЛУ.
Говорят, что решение X = (x1 , , xn ) СЛУ базисное, если оно зависит от
такого множества индексов S, что векторы {A j }j∉S - образуют столбцовый базис матрицы A.
Понятие допустимого базисного решения
Говорят, что решение X = (x1 , , xn ) СЛУ является базисным допустимым, если оно
базисное для СЛУ и X ≥ 0 , т.е. оно базисное и допустимое для задачи
ЛП в канонической форме.
Процедура симплекс-метода
Понятие базисного решения – основа симплекс-метода
Оказывается, что для нахождения оптимального решения достаточно ограничиться рассмотрением только базисных (допустимых базисных) решений в
силу справедливости следующих утверждений (теорем).
1. Если у системы линейных уравнений (СЛУ) существует решение
(СЛУ - совместна), то существует и базисное решение этой СЛУ.
2. Если задача ЛП в канонической форме имеет допустимое решение,
то она имеет и допустимое базисное решение
3. Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное решение.
В силу справедливости последнего утверждения, вычислительный алгоритм линейного программирования (симплекс-метод) основан на нахождении
именно оптимального базисного решения и оперирует только с допустимыми
базисными решениями.
Прямой симплекс-метод решения ЛП задачи (вспомогательные построения)
Рассмотрим задачу линейного программирования в канонической форме
(1) : max z = max(c1 x1 +…+ cn xn )
(2): ai1 x1 +…+ ain xn = bi , i =1, m
17
(3): x j ≥ 0, j =1, n
По этой задаче ЛП запишем систему линейных уравнений, соответствующую этой задаче:
(4) : z  c1 x1  ..  cn xn  0,
(5) : ai1 x1  ...  ain xn  bi , i  1, m
Симплексная таблица – основной элемент вычислительной процедуры
симплекс-метода.
Классификация симплексных таблиц.
Симплексная таблица называется прямо допустимой, если bi ≥ 0, i =1, m
. Прямо-допустимая С-Т соответствует допустимому базисному решению.
Симплексная таблица называется двойственно допустимой, если c j ≥ 0,
j =1, n .
Симплексная таблица называется оптимальной, если она одновременно
и прямо допустимая, и двойственно допустимая. Оптимальная С-Т соответствует оптимальному базисному решению.
Алгоритм симплекс-метода
Алгоритм прямого симплекс-метода (максимизации).
0.
Начать вычисления с прямо-допустимой симплексной табли-
цы.
Вычисления по алгоритму состоят в выполнении следующих однотипных итераций. Каждая такая итерация состоит из трех последовательно выполняемых шагов.
ИТЕРАЦИЯ
1.
Проверка оптимальности или нахождение ведущего столбца С-
Т.
Если все коэффициенты в выделенной строке при небазисных переменных неотрицательны (коэффициенты в z-уравнении), то текущее базисное ре18
шение является оптимальным.
В противном случае на следующей итерации в число базисных переменных вводим небазисную переменную xs, номер которой находится по правилу:
cs = min c j .
c j <0
Столбец под номером s называется ведущим столбцом симплексной
таблицы.
2. Проверка условия неограниченности решения задачи ЛП и нахождение ведущей строки (ведущего элемента) С-Т.
Если в ведущем столбце симплексной таблицы s нет положительных коэффициентов, то значение задачи ЛП неограниченно (нет оптимального решения)
В противном случае (в ведущем столбце имеются положительные элементы) в качестве базисной переменной, которая исключается из числа базисных, выбирается та переменная xr, для которой
bi
br
 min
.
a

0
is
a rs
a is
Строка под номером r называется ведущей строкой С-Т, а элемент ars>0
– ведущим элементом С-Т.
3. Преобразование симплексной таблицы.
Используя эквивалентные преобразования таблицы (процедуру Гаусса)
пересчитываем таблицу так, чтобы ведущий элемент новой С-Т стал равным 1,
а все остальные элементы ведущего столбца – равными 0.
Обозначим верхним индексом 1 элементы новой симплексной таблицы.
Тогда формулы пересчета коэффициентов примут вид:
19
a 1rj 
br1 
a rj
a rs
, j  1, n.
br
,
a rs
a  a ij 
1
ij
a rj
a rs
a is , i  r , j  1, n.
bi1  bi 
br
a is , i  r ,
a rs
c 1j  c j 
a rj
z1  z 0 
a rs
c s , j  1, n,
br
c.
a rs
Перейти к исследованию новой симплексной таблицы (новая итерация).
Пример расчетов по алгоритму прямого симплекс-метода.
max z  max(5 x1  3x 2 )
x1  x 2  4,
5 x1  3x 2  10,
x1  0, x 2  0.
 z  5 x1  3x 2  0,

  x1  x 2  s1  4,
5 x  2 x  s  10.
2
2
 1
20
Ответ задачи:
Пример решения задач ЛП симплекс-методом
Пример расчета экономико-математической модели
Предприятие рекламирует свою продукцию с использованием четырех
источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства
приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 усл. ед., в расчете на 1 усл. ед., затраченную на рекламу. На рекламу выделено 50 000 усл. ед.
Администрация предприятия не намерена тратить на телевидение более 40 %, а
на радио и газеты — более 50 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?
Решение.
Составим математическую модель задачи.
Цель – максимизация прибыли.
Параметрами являются все числа, приведенные в условии задачи.
Управляющие переменные:
х1 – количество средств, вложенных в рекламу на телевидение;
21
х2 – количество средств, вложенных в рекламу на радио;
х3 – количество средств, вложенных в рекламу в газетах;
х4 – количество средств, вложенных в рекламу, организованную с помощью расклейки объявлений.
Область допустимых решений имеет вид
(3.25)
Правило треугольника. Для получения элемента новой симплекстаблицы надо от элемента предыдущей симплекс-таблицы, стоящего на том же
месте, отнять следующее выражение: произведение элемента разрешающей
строки, стоящего в одном столбце с данным элементом, на элемент данной
строки, стоящий в одном столбце с разрешающим элементом, деленное на разрешающий элемент. Это выражение как бы соответствует треугольнику.
Контрольные вопросы:
1. В чем особенности симплекс метода?
2. Может ли в ограничениях присутствовать неравенства при решении задачи симплекс методом?
3. Могут ли, при решении задачи симплекс методом, присутствовать отрицательные переменные?
Тема 4. Метод искусственного базиса
Лекция 4
Аннотация. Данная тема рассматривается сущность метода искусственного базиса и его применения для решения задач ЛП.
Ключевые слова. Метод искусственного базиса, М-метод.
22
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. Н.Ш. Кремер Исследование операций в экономике. 2007г.
2. Г.И. Просветов Математические методы и модели в экономике.
М.,2008.
3. Вентцель Е.С. Исследование операций. М., Наука, 1980.
4. Е. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования
транспортного типа», Москва, 1993.
Глоссарий
Метод искусственного базиса - заключается в применении правил
симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной
ЗЛП таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М - достаточно большое положительное число.
М-метод – см. Метод искусственного базиса.
Вопросы для изучения:
1. Метод искусственного базиса
Метод искусственного базиса
Данный метод решения применяется при наличии в системе ограничений и условий-равенств, и условий-неравенств, и является модификацией табличного метода. Решение системы производится путѐм ввода искусственных
переменных Ri со знаком, зависящим от типа оптимума, т.е. для исключения из
базиса этих переменных последние вводятся в целевую функцию с большими
отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных, а в задачи минимизации - с положительными M. Та23
ким образом из исходной получается новая M-задача (поэтому метод искусственного базиса так же называют M-методом).
Исходная таблица для "Метода искусственного базиса" имеет следующий вид:
x1
x2
... xn-1
xn
b
F
-a0,1
-a0,2
... -a0,n-1
-a0,n
-b0
xn+1
a1,1
a1,2
... a1,n-1
a1,n
b1
xn+2
a2,1
a2,2
... a2,n-1
a2,n
b2
Ri
ai,1
ai,2
... ai,n-1
ai,n
bi
...
...
...
... ...
...
...
xn+m
am,1
am,2
... am,n-1
am,n
bm
M
-∑ai,1
-∑ai,2
... -∑ai,n-1
-∑ai,n
-∑bi
Элементы дополнительной строки M расчитываются как сумма соответствующих коэффициентов условий-равенств (условий в которые после приведения к каноническому виду введены переменные Ri) взятая с противоположным знаком.
Алгоритм метода искусственного базиса.
Приводим задачу ЛП к каноническому виду
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
F
x1
x2
... xn-1
xn
b
-a0,1
-a0,2
... -a0,n-1
-a0,n
-b0
24
xn+1
a1,1
a1,2
... a1,n-1
a1,n
b1
xn+2
a2,1
a2,2
... a2,n-1
a2,n
b2
Ri
ai,1
ai,2
... ai,n-1
ai,n
bi
...
...
...
... ...
...
...
xn+m
am,1
am,2
... am,n-1
am,n
bm
M
-∑ai,1
-∑ai,2
... -∑ai,n-1
-∑ai,n
-∑bi
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены),
если среди них нет отрицательных то найдено допустимое решение (решение
соответствующее одной из вершин многогранника условий) и мы переходим к
шагу 2. Если в столбце свободных членов имеются отрицательные элементы то
выбираем среди них максимальный по модулю - он задает ведущую строку k. В
этой строке так же находим максимальный по модулю отрицательный элемент
ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная,
соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекстаблицу согласно правилам.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на
оптимальность Если среди элементов симплексной таблицы, находщихся в
строках M и F(не беря в расчет элемент b0 - текущее значение целевой функции
и элемент -∑bi) нет отрицательных, то найдено оптимальное решение.
Правила преобразований симплексной таблицы
При составлении новой симплекс-таблицы в ней происходят следующие
изменения:

Вместо базисной переменной xk записываем xl; вместо небазисной
переменной xl записываем xk.
25
ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l

все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l

все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l

оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,l×ak,j/ ak,l

Контрольные вопросы:
1. В чем состоит отличие симплекс метода от метода искусственного базиса?
Тема 5. Двойственные задачи ЛП
Лекция 5
Аннотация. Данная тема посвящена двойственным задачам ЛП, раскрыты понятия двойственных оценок и рассмотрена основная теорема двойственности.
Ключевые слова. Двойственная задача, двойственные оценки, маргинальные оценки, теорема двойственности.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. Акулич И.Л. Математическое программирование в примерах и задачах. - М., 1986.
2. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по
исследованию операций. - М., 1997.
3. Бельченко В.Е., Зайцева О.Б. Методическое пособие по курсу «Исследование операций». Часть I Линейное программирование. - Армавир, 2005.
4. Бельченко В.Е., Зайцева О.Б., Ларина И.Б. Практикум по курсу
«Исследование операций». Часть II. - Армавир, 2007.
5. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. - М., 2001.
Глоссарий
Двойственная задача -
одно из фундаментальных понятий тео26
рии линейного программирования; инструмент, позволяющий установить, оптимально ли данное допустимое решение задачи ЛП, без непосредственного сравнения его со всеми остальными допустимыми решениями.
Двойственные оценки - одно из фундаментальных понятий теории линейного программирования.
Теория двойственности - представляет собой весьма важное, как с чисто теоретической, так и с практической точки зрения, направление математического программирования.
Вопросы для изучения:
1. Постановка задачи
2. Двойственные оценки
3. Основная теорема двойственности
Постановка задачи
Можно сформулировать правила получения двойственной задачи из
задачи исходной.
1. Если в исходной задаче ищется максимум целевой функции, то в
двойственной ей - минимум.
2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.
3. В исходной ЗЛП все функциональные ограничения - неравенства вида
―≤‖, а в задаче, двойственной ей, - неравенства вида ―≥‖.
4. Коэффициенты при переменных в системах ограничений взаимно
двойственных задач описываются матрицами, транспонированными относительно друг друга.
5. Число неравенств в системе ограничений одной задачи совпадает с
числом переменных в другой.
6. Условие неотрицательности переменных сохраняется в обеих задачах.
Двойственные оценки
Рассмотрим экономический смысл двойственных оценок (оценок оптимального плана) на примере экономико-математической задачи наилучшего
использования ресурсов (в частности фонда времени работы производственного оборудования), формулируемой с разными критериями оптимальности:
1. Максимум прибыли.
2. Минимум себестоимости.
27
3. Максимум выпуска продукции в заданном ассортиментном соотношении.
Основная теорема двойственности
Теорема 1. Если одна из двойственных задач имеет конечный оптимум,
то другая также имеет конечный оптимум, причем экстремальные значения
целевых функций совпадают:
(
.
2.6)
Если целевая функция одной из двойственных задач не ограничена, то
условия другой задачи противоречивы.
Теорема 2 (о дополняющей нежесткости). Для того чтобы план
и план
являлись оптимальными решениями, соответственно, задач (2.5) и (2.6) необходимо и достаточно, чтобы выполнялись следующие соотношения:
(
2.7)
Таким образом, если компонент оптимального плана больше нуля, то
при подстановке в соответствующее ограничение двойственной задачи оптимального плана это ограничение обращается в верное равенство, и наоборот.
Контрольные вопросы:
1. Определите и поясните основное неравенство теории двойственности.
2. Сформулируйте и поясните алгоритм получения двойственной задачи по исходной задаче, исходной задачи по двойственной задаче.
3. Когда основное неравенство теории двойственности превращается в
основное равенство теории двойственности?
4. Что минимизируется при решении двойственной задачи?
5. Определите убыточность и неубыточность производства продукции
с точки зрения оптимального решения пары взаимно двойственных задач?
28
Тема 6. Математическая модель транспортной задачи
Лекция 6
Аннотация. Данная тема посвящена транспортным задачам, построению экономико-математической модели транспортной задачи. Рассмотрен алгоритм решения решения ТЗ методом потенциалов.
Ключевые слова. Транспортная задача, опорный план, метод потенциалов.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. Е. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования
транспортного типа», Москва, 1993.
2. И. Л. Акулич, В. Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000.
3. www.fmi.asf.ru
Глоссарий
Транспортная задача(ТП) - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.
Метод
потенциалов
является
модификацией симплексметода решения
задачи линейного
программирования
применительно
к транспортной задаче.
Вопросы для изучения:
1. Общая постановка транспортной задачи.
2. Построение исходного опорного плана.
3. Алгоритм решения ТЗ методом потенциалов.
4. Экономические задачи, сводящиеся к транспортным
моделям.
Общая постановка транспортной задачи
29
Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого груза, потребность которых составляет соответственно b1, b2,...,bn единиц. Известна
стоимость (тариф) cij перевозки единицы груза от i-го (i=1, m) поставщика к j-му
( j  1, n) потребителю. Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится
из пунктов Ai в пункты Bj в соответствии с потребностью и общая величина
транспортных издержек будет минимальной.
Обычно исходные данные транспортной задачи представляют в виде табл. 1:
табл.1
Bj
Ai
b1
b2
...
bn
a1
c11
c12
...
c1n
a2
c21
c22
...
c2n
...
...
...
...
...
am
cm1
cm2
...
cmn
Построение исходного опорного плана
Построение опорных планов, а также их преобразование будем производить непосредственно в распределительной таблице (табл.1). Если в плане перевозок переменная xij  a  0, то это число а записываем в соответствующую
30
клетку (i, j) и считаем ее занятой или базисной, если xij = 0 то клетку (i,j) оставляем свободной.
Метод «северо-западного угла». Определение значений xij начинается с левой верхней, условно называемой северо-западной, клетки (1,1) табл.1.
Находим x11=min(a1, b1).
1) если а1<b1, то x11=a1, строка 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b1 уменьшается на а1;
2) если а1>b1, то х11=b1, столбец 1 исключается из дальнейшего рассмотрения (первый потребитель В1 будет полностью удовлетворен), а наличие груза
у первого поставщика a1 уменьшается на b1;
3) если a1=b1, то x11= a1=b1, первая строка и первый столбец исключаются из дальнейшего рассмотрения. Эта ситуация приводит к вырождению исходного решения.
.
Алгоритм решения ТЗ методом потенциалов
1. Построить опорный план по одному из правил.
2. Проверить план на невырожденность. Если полученный план вырож-
денный, формально заполняют нулями некоторые из свободных клеток так,
чтобы общее число занятых клеток было равно m+n-1. Нули надо расставлять
так, чтобы не образовался замкнутый цикл из занятых клеток.
3. Проверка плана на оптимальность.
3.1. Определение потенциалов поставщиков и потребителей. Для всех
занятых клеток рассчитываются потенциалы по формуле
ui  v j  cij (i  1, m, j  1, n)
(3.8)
где ui - потенциалы поставщиков (строк), vj - потенциалы потребителей
(столбцов).
3.2. Для всех свободных клеток рассчитываются оценки по формуле
sij  cij  (ui  v j )
(3.9)
Здесь cij - реальные тарифы, а ui  v j - косвенные тарифы.
Среди отрицательных оценок выбирается минимальная. Например, для
клеток (i, j) и (k,l) имеем оценки: sij=-2, skl=-4. В этом случае наиболее потенциальной (перспективной) является клетка (k,l). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загруз4.
31
ки данной клетки единицей груза. Так, от загрузки клетки (i,j) единицей груза
транспортные расходы уменьшаются на f i  2 денежных единиц, а от загрузки единицей груза клетки (k, l) - на f 2  4 денежных единиц. Эффективность
плана от загрузки потенциальной клетки грузом в  единиц составит f  sij
денежных единиц.
5. В вершинах цепи, чередуя проставляются знаки «+» и «-», начиная с
выбранной свободной клетки (в нее помещают знак «+»). В клетках со знаком
«-» выбирается минимальная поставка (  ) , которая перераспределяется по цепи: там, где стоит знак «+» она прибавляется, а где «-» - отнимается. В результате чего баланс цикла не нарушается. Исходная свободная клетка становится
занятой, а клетка в которой выбрана минимальная поставка – свободной.
Составляется новый план, рассчитывается значение целевой функции.
Переходим к шагу 2.
Экономические задачи, сводящиеся к транспортным
моделям
К таким задачам относятся следующие:
 оптимальное закрепление за станками операций по обработке деталей.
В них cij является таким экономическим показателем, как производительность.
Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения
cij берутся с отрицательным знаком;
 оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью c ij.
Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
 задача о сокращении производства с учетом суммарных расходов на
изготовление и транспортировку продукции;
 увеличение производительности автомобильного транспорта за счет
минимизации порожнего пробега. Уменьшение порожнего пробега сократит
количество автомобилей для перевозок, увеличив их производительность.
32
Контрольные вопросы:
1. Запишите открытую модель транспортной задачи.
2. Дайте определение цикла свободной клетки. Сколько циклов существует у одной свободной клетки?
3. Что называется оценкой свободной клетки?
4. В каком случае план можно улучшать и как это сделать?
5. Как свести открытую модель транспортной задачи к закрытой?
6. В каком случае план транспортной задачи считается вырожденным?
Как с этим бороться?
7. Как можно построить начальное опорное решение транспортной задачи?
8. Дайте экономическую интерпретацию метода потенциалов решения
транспортной задачи.
Тема 7. Целочисленное программирование
Лекция 7
Аннотация. В данной теме рассмотрены задачи целочисленного программирования. Подробно описан метод Гомори решения задач целочисленного программирования, приведены примеры решения задач целочисленного программирования
Ключевые слова. Целочисленное программирование, метод Гомори,
венгерский метод.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. Аркин П.А., Межевич К.Г Исследование операций/учебное пособие.-СПб.: СПбГТИ(ТУ),2008.-333с.
2. А.В. Кузнецов, В.П. Сакович, И.И. Холод Высшая математика. Математическое программирование/Минск «ВЫШЕЙШАЯ ШКОЛА» 1994.-288с.
3. Х. Таха. Введение в исследование операций. Т.2. - М. : Мир, 1985.
4. В.Н. Серпинский О решении уравнений в целых числах. - М.: Физматлит, 1961. - 88 с.
33
Глоссарий
Целочисленное программирование - Раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.
Метод Гомори - алгоритм, который используется для решения полностью целочисленных задач линейного программирования.
Венгерский метод - алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время.
Вопросы для изучения:
1. Целочисленное программирование. Постановка задачи
2. Графический метод решения
3. Метод Гомори (алгоритм метода). Задачи о назначениях
Целочисленное программирование. Постановка задачи
Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по произ-водству и распределению неделимой продукции (выпуск стан-ков, телевизоров, автомобилей и т. д.). В общем
виде математи-ческая модель задачи целочисленного программирования име-ет
вид
При ограничениях:
Оптимальное решение задачи, найденное симплексным ме-тодом, часто
не является целочисленным. Его можно округлить до ближайших целых чисел.
Однако такое округление может дать решение, не лучшее среди целочисленных
решений, или привести к решению, не удовлетворяющему системе ограниче-ний. Поэтому для нахождения целочисленного решения нужен особый алгоритм. Такой алгоритм предложен Гомори и состо-ит в следующем.
Определение 1. Целой частью числа Fi называют наибольшее целое
число, не превосходящее числа Fi.
Дробную часть чисел Fi и Hij обозначим {Fi} и {Hij}, она определяется
следующим образом:
Пример.
Если Fi и хотя бы одно значение Hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнитель-ное ограничение по целочисленности примет вид
34
{hi, r+l} xr+1 + {hi, r+2} xr+2 + • • • + {hi, п} xп ≥ {fi}.
Примечания. 1) Если Fi — дробное число, а все Hij — целые числа, то
задача линейного программирования не имеет целочисленного решения.
2) Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае задача является частично целочисленной.
Графический метод решения
Рассмотрим случай, когда число неизвестных равно двум. Для решения
задачи графическим методом прежде строят многоугольник решений без условия целочисленности. Условию целочисленности переменных удовлетворяют
не все координаты точек области допустимых решений, поэтому область допустимых решений ослабленной задачи (без условия целочисленности) заменяется на выпуклый многоугольник, содержащий только допустимые точки с целочисленными координатами. Чтобы найти максимум или минимум целевой
функции на выпуклой оболочке строят вектор градиент С(с1, с2). Передвигая
прямую Z =c1x1+c2x2 в направлении вектора С, в результате чего находят точку,
в которой целевая функция принимает оптимальное значение. Затем определяем координаты точки экстремума функции и вычисляем значение целевой
функции в этой точке.
Метод Гомори (алгоритм метода). Задачи о назначениях
Метод Гомори решения задач целочисленного программирования является методом отсечения.
Суть метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих
ни одного целочисленного плана. Для этого сначала решается ослабленная задача линейного программирования без учета условия целочисленности переменных.
Если полученное решение задачи линейного программирования является целочисленным, то задача целочисленного программирования также решена
и найденное решение является оптимальным и для нее. Если же в найденном
решении задачи линейного программирования одна или большее число переменных не целые, то для отыскания целочисленного решения задачи добавляются новое линейное ограничение, которое отсекает нецелочисленные решения. При продолжении решения расширенной задачи двойственным симплексным методом с учетом этого ограничения получается целочисленный план.
35
Для нахождения целочисленного решения задачи методом Гомори используется следующий алгоритм.
1. Решаем ослабленную задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он
является оптимальным и для задачи целочисленного программирования. Если
обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
2. Если в результате решения задачи линейного программирования в
полученном оптимальном плане Х  ( х1 , х2 ,..., хn ) есть нецелая базисная пе*
*
*
*
ременная х i* , то к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
Составляем неравенство Гомори хi*   aij  x j  0 и включаем его
n
3.
j 1
в систему ограничений исходной задачи.
Для этого по производящей строке симплексной таблицы выписывается
уравнение, предполагая, что первые m переменных являются базисными для
данного оптимального плана
n
n
x  xi   аij x j или xi  x   аij x j

i

i
j 1
j 1
Переносим все целые части коэффициентов в одну сторону, оставляя все
дробные в другой:
x j  [ x j ] 
 à x  õ   à x
n
n
ij
j 1 m
*
j
j
j 1 m
ij
j
õ   à x  õ 
Так как õ <1, то заменяя в правой части õ , получим строгое неравенn
*
j
j 1 m
ij
*
j
j
*
j
*
j
ство
õ   à x
n
*
j
j 1 m
ij
j
1
Так как левая часть неравенства должна принимать целые значения, то,
следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:
õ   à x
n
*
j
j 1 m
ij
j
0
36
4. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.
5. Решаем задачу, используя двойственный симплексный метод. Если
новый оптимальный план расширенной задачи будет целочисленным, то задача
решена. Если же решение нецелое, то нужно повторять алгоритм метода Гомори вплоть до получения целочисленного решения.
Контрольные вопросы:
1. Какая задача называется задачей целочисленного программирования?
2. Какие методы существуют для решения задач целочисленного программирования?
3. Как составить неравенство Гомори по строке симплексной таблицы?
4. Запишите алгоритм метода Гомори.
5. Какие решения могут быть потеряны при применении метода Гомори?
6. Сформулируйте алгоритм решения задачи целочисленного программирования
методом ветвей.
Тема 8. Элементы теории нелинейного динамического программирования
Лекция 8
Аннотация. В данной теме освещено понятие динамического программирования. Рассмотрена задача нелинейного программирования Приведен алгоритм метода динамического программирования.
Ключевые слова. Целочисленное программирование, динамическое
программирование.
Методические рекомендации по изучению темы. Тема содержит лекционную часть, где в разделе «Лекция» имеются общие представления по теме.
Далее необходимо ответить на вопросы, предлагающиеся после лекции. После
прохождения предыдущего этапа необходимо решить практические задания.
Источники информации:
1. http://knigi-uchebniki.com/mikroekonomika_702/2ainamicheskie-igryisovershennoy.html
2. Астафьева Л.К. Математические методы в экономике. 2007г.
3. Г.И. Просветов Математические методы и модели в экономике.
М.,2008.
37
Глоссарий
Целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно
накладывается ограничение целочисленности.
Динамическое программирование (ДП) - метод решения задач путем
составления последовательности из подзадач таким образом, что: первый элемент последовательности (возможно несколько элементов) имеет тривиальное
решение; последний элемент этой последовательности - это исходная задача;
каждая задача этой последовательности может быть решена с использованием
решения подзадач с меньшими номерами
Вопросы для изучения:
1. Задачи нелинейного программирования
2. Динамическое программирование
Задачи нелинейного программирования
Задача нелинейного программирования это задача на условный минимум с ограничениями типа неравенств. Пусть на
f1(x),
f2(x),
определены функции f(x),
...
fm(x). Обозначим D = {x:
, fi(x) 0, i=1,..,m, xj 0, j=1,..,n}={x:
, F(x)
0, x 0}, где F(x) = (f1(x), ..., fm(x)). Множество D называется допустимой областью. Задача минимизации функции f на множестве D называется задачей нелинейного программирования. Таким образом, решением задачи нелинейного
программирования
являются
вектор
и
число f* такие,
что
.
Определение 1. Точка
нимума
функции f на
называется точкой условного (глобального) мимножестве D,
если
.
Определение 2. Точка
называется точкой локального условного минимума функции f на множестве D, если существует число
, такое, что неравенство
выполняется для таких
38
, что
.
Метод динамического программирования
Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный
к так называемым «многошаговым» (или «многоэтапным») операциям.
Представим себе некоторую операцию О, распадающуюся на ряд последовательных «шагов» или «этапов»,— например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой
самолетов нескольких полос противовоздушной обороны; или же последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции
(подобно вышеприведенным) расчленяются на шаги естественно; в некоторых
членение приходится вводить искусственно — скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает
какоето время t.
Итак, рассмотрим операцию Ò, состоящую из т шагов (этапов). Пусть
эффективность операции характеризуется какимто показателем W, который мы
для краткости будем в этой главе называть «выигрышем». Предположим, что
выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:
где wi — выигрыш на iм шаге.
Если W обладает таким свойством, то его называют «аддитивным критерием».
Операция Ò, о которой идет речь , представляет собой управляемый
процесс, т. е. мы можем выбирать какието параметры, влияющие на его ход и
исход, причем на каждом шаге выбирается какоето решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть
это решение «шаговым управлением». Совокупность всех шаговых управлений
представляет собой управление операцией в целом. Обозначим его буквой х, а
шаговые управления — буквами х1, x2, ..., хт:
Рассмотрим несколько примеров многошаговых операций и для каждого
из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности) W.
1. Планируется деятельность группы промышленных предприятий II1,
П2, ..., Пk на период т хозяйственных лет mлетку). В начале периода на развитие группы выделены какието средства М, которые должны быть както распре39
делены между предприятиями. В процессе работы предприятия вложенные в
него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит
доход, зависящий от того , сколько средств в него вложено. В начале каждого
хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы, суммарный доход за т
лет был максимальным?
2. Космическая ракета состоит из т ступеней, а процесс ее вывода на
орбиту — из т этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какойто
общий вес:
где Gi — вес iй ступени.
3. Владелец автомашины эксплуатирует ее в тече ние т лет. В начале
каждого года он может принять одно из трех решений:
1) продать машину и заменить ее новой;
2) ремонтировать ее и продолжать эксплуатацию;
3) продолжать эксплуатацию без ремонта.
Шаговое управление — выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное
значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т.
е. как чередовать управления 1, 2,3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?
4. Прокладывается участок железнодорожного пути между пунктами А и
В (рис. 12.1). Местность пересеченная, включает лесистые зоны, холмы, болота,
реку, через которую надо строить мост. Требуется так провести дорогу из А в В,
чтобы суммарные затраты на сооружение участка были минимальны.
Примеры решения задач динамического программирования
1. Прокладка наивыгоднейшего пути между двумя пунктами.
Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и
намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий
40
два пункта А и В, из которых второй лежит к северовостоку от первого.
Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север ;
любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки
которой параллельны одной из координатных осей (рис. 13.1). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой
путь из А в В, при котором суммарные затраты минимальны.
Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно !); либо разделить процесс перехода из А в В на отдельные шаги (один шаг — один отрезок)
и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным «слепым» перебором.
Продемонстрируем, как это делается , на конкретном примере. Разделим
расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном — на 5 частей (в принципе дробление может быть сколь угодно мелким).
Тогда любой путь из А в В состоит из т = 7 + 5 = 12 отрезков, направленных на
восток или на север (рис. 13.2). Проставим на каждом из отрезков число, выражающее (в каких то условных единицах) стоимость прокладки пути по этому
отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел,
стоящих на отрезках, минимальна.
41
Будем рассматривать сооружаемый путь как управляемую систему S,
перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами : восточной (х) и северной (у), обе — целочисленные (0 ≤ х ≤ ≤ 7, 0 ≤ y ≤ 5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 13.2) мы должны найти условное оптимальное
управление: идти нам из этой точки на север (управление «с») или на восток
(управление «в »). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна . Эту стоимость
мы попрежнему будем называть «условным оптимальным выигрышем» (хотя в
данном случае это не «выигрыш», а «проигрыш») для данного состояния системы S перед началом очередного шага.
Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12го шага. Рассмотрим отдельно правый верхний угол нашей
прямоугольной сетки (рис. 13.3). Где мы можем находиться после 11го шага?
Только там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из
точек В1 или В2. Если мы находимся в точке В\, у нас нет выбора (управление
вынужденное ): надо идти на восток, и это обойдется нам в 10 единиц. Запишем
это число 10 в кружке у точки В\, а оптимальное управление покажем короткой
стрелкой, исходящей из В1 и направленной на восток. Для точки B2 управление
тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке
у точки В2. Таким образом, условная оптимизация последнего шага сделана, и
условный оптимальный выигрыш для каждой из точек В1, В2 найден и записан
в соответствующем кружке.
Теперь давайте оптимизировать предпоследний (11й) шаг. После пред42
предпоследнего (10го) шага мы могли оказаться в одной из точек С1, С2, С3
(рис. 13.4). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти
на восток ; обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс
10, записанных в кружке при Bi). Число 21 записываем в кружке при точке С1.
Для точки С2 управление уже не вынужденное: мы можем идти как на восток,
так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В2
до конца — еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10,
всего 23 единицы. Значит, условное оптимальное управление в точке С2 — идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2). Для
точки С3 управление снова вынужденное («с»), обойдется это до конца в 22
единицы (ставим стрелку на север, число 22 записываем в кружке при С3).
Аналогично, «пятясь» от предпоследнего шага назад, найдем для каждой
точки с целочисленными координатами условное оптимальное управление («с»
или «в»), которое обозначим стрелкой, и условный оптимальный выигрыш
(расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним — уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 13.5.
Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем , куда идти (стрелка) и во что нам
обойдется путь до конца (число в кружке ).. В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В: W* = 118.
Теперь остается построить безусловное оптимальное управление — тра43
екторию, ведущую из А и В самым дешевым способом. Для этого нужно только
«слушаться стрелок», т. е. прочитать, что они предписывают делать на каждом
шаге. Такая оптимальная траектория отмечена на рис. 13.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:
т. е. первые четыре шага мы должны делать на север, следующие два —
на восток, затем опять один на север и остальные пять — на восток. Задача решена.
Заметим, что в ходе условной оптимизации мы можем столкнуться со
случаем, когда оба управления для какойто точки на плоскости являются оптимальными, т. е. приводят к одинаковому расходу средств от этой точки до конца, Например, в точке с координатами (5; 1) оба управления « с» и «в» являются
оптимальными и дают расход до конца равным 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали «с»; с тем же успехом мы могли бы
выбрать «в»). Такие случаи неоднозначного выбора оптимального управления
постоянно встречаются в динамическом программировании; в дальнейшем мы
специально отмечать их не будем, а попросту выберем произвольно любой из
равноценных вариантов. От этого произвола, разумеется, может зависеть оптимальное управление всем процессом, но не оптимальный выигрыш . Вообще, в
задачах динамического программирования (как и в задачах линейного) решение
далеко не всегда единственное.
А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого
шага) направление (если таких два, выбираем любое). Таким способом мы получим управление x=(c,c,b,b,b,b,c,b,b,b,c,c)
Подсчитаем расходы для этой траектории . Они будут равны W = 10 +12
+ 8+ 10 + 11 + 13+ 15 + 8 + + 10 + 9 + 8+14= 128, что безусловно больше, чем
W* = 118. В данном случае разница не очень велика, но
в
других она может быть существенной.
В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, по, разумеется, усложняет и удлиняет расчеты.
Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике: например, при выборе наискорейшего пути между двумя
точками или наиболее экономного (в смысле расхода горючего) набора скоро44
сти и высоты летательным аппаратом.
Сделаем одно попутное замечание. Внимательный читатель, вероятно,
заметил, что в нашей задаче точки А и В (начало и конец) в принципе ничем
друг от друга не отличаются: можно было бы строить условные оптимальные
управления не с конца к началу, а с начала к концу, а безусловные — в обратном направлении. Действительно, это так: в любой задаче динамического программирования «начало» и «конец» можно поменять местами. Это совершенно
равносильно описанной ранее методике в расчетном отношении, но несколько
менее удобно при словесном объяснении идеи метода: легче аргументировать,
ссылаясь на «уже сложившиеся» условия к началу данного шага, чем на те, которые еще «предстоят» после этого шага. По существу же оба подхода совершенно равносильны.
Контрольные вопросы:
1.
2.
3.
Чем завершается этап условной оптимизации?
Чем завершается этап безусловной оптимизации?
Определи алгоритм решения задачи динамического программиро-
вания?
4. Почему метод динамического программирования широко используется при решении экономических оптимизационных задач?
45
Информационные источники
Основная литература:
1. Н.Ш. Кремер Исследование операций в экономике. 2007г.
2. Исследование операций в экономике. Под редакцией проф. Н.Ш. Кремера. М., «Банки и биржи», ЮНИТИ, 1997.
3. Хэмди А. Таха. Введение в исследование операций. Издательский дом
«Вильямс»,М., С-П, Киев, 2001.
4. Вентцель Е.С. Исследование операций. М., Наука, 1980.
5. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. - М., 2001.
6.
http://knigi-uchebniki.com/mikroekonomika_702/2ainamicheskie-igryisovershennoy.html
7. Астафьева Л.К. Математические методы в экономике. 2007г.
8. Г.И. Просветов Математические методы и модели в экономике.
М.,2008.
Дополнительная литература:
1.
П.Н. Коробов. Математическое программирование и моделирова-
ние экономических процессов. – М.: ДНК, 2006. – 376 с.
2.
Камилл Ахметов. Практика управления проектами. – М.: Русская
Редакция, 2004. – 272 с.
3.
В.А. Охорзин. Оптимизация экономических систем. Примеры и ал-
горитмы в среде Mathcad. – М.: Финансы и статистика, 2005. – 144 с.
4.
Г.В. Шадрина. Управленческий анализ. – М.: Альфа-Пресс, 2008. –
5.
В.В. Покровский. Математические методы в бизнесе и менеджмен-
320 с.
те. – М.: Бином. Лаборатория знаний, 2008. – 112 с.
6.
А.Р. Урубков, И.В. Федотов. Методы и модели оптимизации управ-
ленческих решений. – М.: Дело АНХ, 2011. – 240 с.
7.
Акулич И.Л. Математическое программирование в примерах и за-
дачах. - М., 1986.
46
8.
Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по
исследованию операций. - М., 1997.
9.
Бельченко В.Е., Зайцева О.Б. Методическое пособие по курсу
«Исследование операций». Часть I Линейное программирование. - Армавир,
2005.
10.
Бельченко В.Е., Зайцева О.Б., Ларина И.Б. Практикум по курсу
«Исследование операций». Часть II. - Армавир, 2007.
11.
Аркин П.А., Межевич К.Г Исследование операций/учебное посо-
бие.-СПб.: СПбГТИ(ТУ),2008.-333с.
12.
Х. Таха. Введение в исследование операций. Т.2. - М. : Мир, 1985.
Информационные ресурсы:
1. Балдин, К. В. Математические методы и модели в экономике [Электронный ресурс] : учебник / К. В. Бал дин, В. Н. Башлыков, А. В. Рукосуев; под общ.
ред. К. В. Балдина. - М.: ФЛИНТА : НОУ ВПО «МПСИ», 2012. - 328 с. - ISBN
978-5-9765-0313-7 (ФЛИНТА), ISBN 978-5-9770-0647-7 (НОУ ВПО «МПСИ»).
2. Экономико-математические методы в примерах и задачах: Учеб. пос. /
А.Н.Гармаш, И.В.Орлова, Н.В.Концевая и др.; Под ред. А.Н.Гармаша - М.: Вуз.
уч.: НИЦ ИНФРА-М, 2014 - 416с.: 60x90 1/16 + ( Доп. мат. znanium.com).(п)
ISBN 978-5-9558-0322-7, 700 экз.
3. Машунин, Ю. К. Теория управления. Математический аппарат управления в экономике [Электронный ресурс] : учеб. пособие / Ю. К. Машунин. - М.:
Логос, 2013. - 448 с. - (Новая университетская библиотека). - ISBN 978-5-98704736-1.
4. Грызина Н.Ю., Мастяева И.Н., Семенихина О.Н. МАТЕМАТИЧЕСКИЕ
МЕТОДЫ
ИССЛЕДОВАНИЯ
ОПЕРАЦИЙ
В ЭКОНОМИКЕ:
Учебно-
методический комплекс. – М.: Изд. центр ЕАОИ, 2009. – 196 c. ISBN 978-5-37400071-9
47
Список сокращений
ИО – исследование операций.
ЛП – линейное программирование.
ЗЛП – задача линейного программирования.
БП – базисное решение.
ТП – транспортная задача.
ДП – динамическое программирование.
48
Глоссарий
Базисное решение – термин линейного программирования, одно из допустимых решений, находящихся в вершинах области допустимых решений,
либо (если линия уровня параллельна одному из отрезков границы области).
Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.
Венгерский метод - алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время.
Двойственная задача - одно из фундаментальных понятий теории линейного программирования; инструмент, позволяющий установить, оптимально ли данное допустимое решение задачи ЛП, без непосредственного сравнения его со всеми остальными допустимыми решениями.
Двойственные оценки - одно из фундаментальных понятий теории линейного программирования.
Динамическое программирование (ДП) - метод решения задач путем
составления последовательности из подзадач таким образом, что: первый элемент последовательности (возможно несколько элементов) имеет тривиальное
решение; последний элемент этой последовательности - это исходная задача;
каждая задача этой последовательности может быть решена с использованием
решения подзадач с меньшими номерами
Задача линейного программирования – математическая дисциплина,
посвящѐнная теории и методам решения экстремальных задач на множествах мерного векторного пространства, задаваемых системами линейных уравнений
и неравенств.
Имитационное моделирование – экспериментирование с моделью реальной системы, в частности, вычислительный эксперимент, проводимый с помощью математической модели путем изменения различных исходных предпосылок.
Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.
Линейное программирование-–линейное планирование, т.е. получение
оптимального плана - решения в задачах с линейной структурой.
Математическая модель представляет собой систему математических
и логических соотношений, описывающих структуру и функции реальной системы.
Математическое программирование – это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограни49
чениями. В отличие от классической математики, математическое программирование занимается математическими методами решения задач нахождения
наилучших вариантов из всех возможных.
Метод искусственного базиса - заключается в применении правил
симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной
ЗЛП таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае ее максимизации слагаемое, представляющее собой произведение числа (-М) на сумму искусственных переменных, где М - достаточно большое положительное число.
М-метод – см. Метод искусственного базиса.
Метод Гомори - алгоритм, который используется для решения полностью целочисленных задач линейного программирования.
Метод
потенциалов
является
модификацией симплексметода решения
задачи линейного
программирования
применительно
к транспортной задаче.
Модель – система, способная замещать оригинал так, что ее изучение
дает новую информацию об оригинале.
Моделирование – это процесс построения и исследования модели, способной заменить реальную систему и дать о ней новую информацию.
Нелинейное программирование– случай математического программирования, в котором целевой функцией или ограничением является нелинейная
функция.
Описательные модели экономических систем представляют собой
формализованную с помощью математического аппарата экономическую задачу и используются для более глубокого изучения состояния системы и взаимосвязи ее элементов.
Оптимизационные модели отражают в математической форме смысл
экономической задачи. Отличительной особенностью этих моделей является
наличие условия нахождения оптимального решения (критерия оптимальности), которое записывается в виде функционала.
Оптимальный план- наилучшее распределение ресурсов в задаче математического программирования.
Символическая модель описывает структуру и функции оригинала с
помощью символов и соотношений между ними, выражающих определенные
зависимости, присущие оригиналу.
50
Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путѐм перебора вершин выпуклого многогранника в
многомерном пространстве. Метод был разработан советским математиком
Канторовичем Л. В. в 1937 году.
Симплексная таблица – основной элемент вычислительной процедуры
симплекс – метода.
Теория двойственности - представляет собой весьма важное, как с чисто теоретической, так и с практической точки зрения, направление математического программирования.
Транспортная задача (ТП) - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.
Целевая функция – функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.
Эвристика (в переводе с греческого - нахожу, придумываю, открываю) это совокупность неформальных методов решения задач (эвристических методов), основанных на прошлом опыте, интуиции решающего. Эвристические методы в общем случае не гарантируют получение наилучшего решения, поскольку они опираются не на доказательства, а на так называемые правдоподобные рассуждения.
Экстремум функции – максимальное или минимальное значение функции на заданном множестве.
Целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно
накладывается ограничение целочисленности.
51
Вопросы к экзамену
1.
Предмет и цели исследования операций. Общие понятия
2.
Общая характеристика и последовательность решения задач в ис-
следованиях операций. Основные отличия метода исследования операций
3.
Основные задачи, решаемые методом исследования операций.
Классификация задач.
4.
Методы отыскания оптимальных решений в задачах исследования
операций. Классификация методов.
5.
Экономико-математическое моделирование в теории исследования
операций.
6.
Постановка и модель задачи определения оптимального ассорти-
мента продукции.
7.
Постановка и модель задачи определения оптимального рациона
питания (на примере).
8.
Постановка и модель задачи определения оптимального использо-
вания мощностей оборудования.
9.
Понятие задачи линейного программирования. Примеры.
10.
Приведение задачи линейного программирования к канонической
форме. Примеры.
11.
Графическое решение задачи линейного программирования.
12.
Симплекс-метод. Геометрическая интерпретация симплексного
метода.
13.
Взаимно двойственные задачи линейного программирования и их
свойства.
14.
Экономическая интерпретация задачи, двойственной задаче об ис-
пользовании ресурсов
15.
Теоремы двойственности
16.
Целочисленные задачи линейного программирования. Методы ре-
шения. Задача коммивояжера.
52
17.
Постановка и экономико-математическая модель транспортной за-
18.
Экономические задачи, сводящиеся к транспортным.
19.
Методы составления первоначальных опорных планов в транспорт-
дачи.
ной задаче. Пример
20.
Системы управления запасами. Общие понятия. Модель оптималь-
ного размера заказа.
21.
Назначение и области применения сетевого планирования и управ-
ления (СПУ). Сетевая модель и ее основные элементы. Порядок и правила построения сетевых графиков. Понятие о критическом пути.
22.
Линейная диаграмма проекта. Временные параметры сетевых гра-
фиков.
53
1/--страниц
Пожаловаться на содержимое документа