Контрольная работа по дисциплине «Экономико-математическое моделирование»

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

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования

«Алтайский государственный  аграрный университет»

Кафедра «Геодезии и картографии»

 

 

 

 

Контрольная работа по дисциплине

«Экономико-математическое моделирование»

 

 

Выполнил: студент 5 курса

Факультет: Природообустройство

Специальность: Землеустройство

Шифр:         

Проверил:                      

Барнаул 2013г.

 

 

Содержание:

20. Как осуществляется  проверка плана на оптимальность  при решении задач распределительным  методом?

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

40. Элементы и принципы  построения сетевых графиков. Их  назначение.

50. Балансовые модели в  землеустройстве и кадастре.

Задачи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20. Как  осуществляется проверка плана  на оптимальность при решении  задач распределительным методом?

Проверка плана  транспортной задачи в описываемом  методе на оптимальность осуществляется с помощью потенциалов. Потенциалы – это такие числа, которые  по определенным правилам назначаются  каждой строке и каждому столбцу. Потенциалы строк обозначим u_i, потенциалы столбцов – v_j. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А₂В₃. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u₃ = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле 

 

.       

2) Решим задачу с искусственным  базисом (хотя бы один знак  неравенств-ограничений " ≥ " или " = ").

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для  этого введем две переменные х₃ ≥ 0 и х₄ ≥ 0 получим:

Система ограничений предлагает только одну допустимую базисную переменную x₄, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R₁ ≥ 0 и R₂ ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R₁, R₂ и x₄. Получили, так называемую, М-задачу:

Данная система является системой с базисом, в которой R₁, R₂ и x₄ базисные переменные, а x₁, x₂ и x₃ свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

 

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	-4	-16	0	0	0	0	0	-
R1	3	4	-1	1	0	0	6	6/4=3/2
R2	1	3	0	0	1	0	3	3/3=1
x4	2	1	0	0	0	1	4	4/1=4
Оценка	-4	-7	1	-1	-1	0	-	-

В таблицу для задач  с искусственным базисом добавлена  строка «Оценка». Она получается суммированием  соответствующих коэффициентов  строк с искусственными переменными (R) с обратным знаком. Она будет  присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х₂, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R₂ выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х₂ из свободной перейдет в базисную, а переменная R₂ из базисной – в свободную. Запишем следующую симплекс-таблицу:

итерация 1

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	4/3	0	0	0	16/30	0	16	-
R1	5/3	0	-1	1	-4/3	0	2	6/5
x2	1/3	1	0	0	1/3	0	1	3
x4	5/3	0	0	0	-1/3	1	3	9/5
Оценка	-5/3	0	1	-1	4/3	0	-	-

Разрешающий столбец х₁, разрешающая строка R₁, R₁ выходит из базиса, x₁ входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

БП	x1	x2	x3	R1	R2	x4	Решение	Отношение
z	0	0	4/5	-4/5	32/5	0	72/5	-
x1	1	0	-3/5	3/5	-4/5	0	6/5	-
x2	0	1	1/5	-1/5	3/5	0	3/5	-
x4	0	0	1	-1	1	1	1	-

Далее разрешающий столбец  выбирается по z-строке. В z-строке все  коэффициенты неотрицательны кроме  коэффициента при искусственной  переменной R₁, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x₁ = 6/5; x₂ = 3/5; z_max = 72/5.

 

 

 

 

 

 

 

 

 

 

 

 

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

Особые случаи применения симплекс-метода

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

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

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

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

Алгоритм симплекс-метода включает следующие этапы:

1. Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
2. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

40. Элементы  и принципы построения сетевых  графиков. Их назначение.

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

Главными элементами сетевой  модели являются работы и события.

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

 

•     — событие,

 

    — работа (процесс),

 

    — фиктивная работа  — применяется для упрощения  сетевых графиков (продолжительность  всегда равна 0).

 

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

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

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

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

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