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

Содержание

 

1 Условные обозначения, применяемые  при моделировании 3

2 Задача № 1  9

3 Задача № 2 12

4 Задача № 3 17

Список используемой литературы  28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Условные обозначения, применяемые при моделировании

 

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

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

К задачам динамического программирования относятся:

1. Распределение ресурсов(финансовых, материальных, топливно-энергетических и др.) между несколькими предприятиями с целью получения максимальной прибыли за определённый период времени.
2. Составление календарных планов ремонта и обновления технологического оборудования на предприятии.
3. Управление запасами сырья и готовой продукции на предприятии для обеспечения его бесперебойной работы.
4. Проектирование дороги минимальной стоимости в условиях сложного рельефа местности.
5. Загрузка транспортного средства предметами различных типоразмеров с целью перевозки грузов максимальной стоимости.
6. Определение наиболее экономичного режима полёта летательного аппарата.

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

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

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

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

,

где - некоторая функция, выражающая закон изменения состояния системы S, определяемая внутренними свойствами системы и внешними условиями её существования и называемая функцией процесса.

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

.

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

Многошаговые процессы включают в общем случае некоторое число N шагов. Через обозначают номер шага, который может принимать значения от 1 до N включительно; это обстоятельство записывается так: На каждом шаге процесса управления u может принимать различные значения .

Таким образом, обозначим через состояние системы после шага с номером ; при этом через естественно обозначить начальное состояние системы перед первым шагом процесса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Задача № 1

 

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решить задачу на максимум, и почему?

Условие задачи:

Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.

 

Питательное вещество (витамин)	Необходимый минимум питательных веществ	Число единиц питательных Веществ в 1 кг корма
		I	II
	9	3	1
	8	1	2
	12	1	6

 

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ед.

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

Решение:

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

Ограничения задачи будут выглядеть следующим образом:

,

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

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

Аналогичный образом построим области решения двух других неравенств. Решениям второго уравнения служат точки прямой , (0;4) и (8;0); третьего уравнения - точки (0;2) и (12;0).

Заштрихуем общую область для всех неравенств.

 

 

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

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

,                

;         

 

,

(ден. ед.)

Т.о. оптимальное решение найдено. Минимум расходов 26 ден. ед. достигается при использовании 2 единиц I вида корма и 3 единиц II вида питательных веществ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Задача № 2

 

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

 

Таблица 24 – Исходные данные к задаче

Тип сырья	Нормы расхода сырья на одно изделие, ед.		Запасы сырья, ед.
	А	Б
I	1	2	11
II	2	1	5
III	1	3	14
Прибыль изделия, ден. ед.	4	2	Х

 

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

Определим максимальное значение целевой функции F(X) = 4x1 + 2x2 при следующих условиях-ограничений.

x1 + 2x2≤11

2x1 + x2≤5

x1 + 3x2≤14

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 

1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 11

2x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5

1x1 + 3x2 + 0x3 + 0x4 + 1x5 = 14

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 

 

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

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

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

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,11,5,14)

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

 

Базис	B	x1	x2	x3	x4	x5
x3	11	1	2	1	0	0
x4	5	2	1	0	1	0
x5	14	1	3	0	0	1
F(X0)	0	-4	-2	0	0	0

 

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной  переменной.

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

3. Определение новой свободной  переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (11 : 1 , 5 : 2 , 14 : 1 ) = 21/2

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

 

Базис	B	x1	x2	x3	x4	x5	min
x3	11	1	2	1	0	0	11
x4	5	2	1	0	1	0	21/2
x5	14	1	3	0	0	1	14
F(X1)	0	-4	-2	0	0	0	0

 

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=2

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

 

B	x 1	x 2	x 3	x 4	x 5
11-(5 • 1):2	1-(2 • 1):2	2-(1 • 1):2	1-(0 • 1):2	0-(1 • 1):2	0-(0 • 1):2
5 : 2	2 : 2	1 : 2	0 : 2	1 : 2	0 : 2
14-(5 • 1):2	1-(2 • 1):2	3-(1 • 1):2	0-(0 • 1):2	0-(1 • 1):2	1-(0 • 1):2
0-(5 • -4):2	-4-(2 • -4):2	-2-(1 • -4):2	0-(0 • -4):2	0-(1 • -4):2	0-(0 • -4):2

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4	x5
x3	81/2	0	11/2	1	-1/2	0
x1	21/2	1	1/2	0	1/2	0
x5	111/2	0	21/2	0	-1/2	1
F(X1)	10	0	0	0	2	0

 

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

 

Базис	B	x1	x2	x3	x4	x5
x3	81/2	0	11/2	1	-1/2	0
x1	21/2	1	1/2	0	1/2	0
x5	111/2	0	21/2	0	-1/2	1
F(X2)	10	0	0	0	2	0

 

Оптимальный план можно записать так:

x1 = 21/2

F(X) = 4•21/2 = 10

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 81/2

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 111/2

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

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

Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x3), выполнив соответствующие этапы алгоритма.

После преобразований получаем новую таблицу:

 

Базис	B	x1	x2	x3	x4	x5
x2	52/3	0	1	2/3	-1/3	0
x1	-1/3	1	0	-1/3	2/3	0
x5	-22/3	0	0	-12/3	1/3	1
F(X )	10	0	0	0	2	0

 

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

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