Размещено на http://www.allbest.ru/

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

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

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

«ИЖЕВСКАЯ ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ»

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

КОНТРОЛЬНАЯ РАБОТА

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

Ижевск, 2007

Содержание

1. Классификация переменных и ограничений по их роли в моделируемом процессе

2. Двойственные задачи линейного программирования

2.1 Понятие двойственной задачи ЛП

2.2 Общая схема построения двойственной задачи

2.3 Пример построения двойственной задачи

3. Решение задач

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

1. Классификация переменных и ограничений по их роли в моделируемом процессе

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

По соотношению экзогенных и эндогенных переменных, включаемых в модель, они могут разделяться на открытые и закрытые. Полностью открытых моделей не существует; модель должна содержать хотя бы одну эндогенную переменную. Полностью закрытые экономико-математические модели, т.е. не включающие экзогенных переменных, исключительно редки; их построение требует полного абстрагирования от “среды”, т.е. серьёзного упрощения реальных экономических систем, всегда имеющих внешние связи. Подавляющее большинство экономико-математических моделей занимает промежуточное положение, и различаются по степени открытости (закрытости).

	Типы ограничений
	1.	Задания по объему производства
	2.	Ограничения на объем используемых ресурсов
	3.	Балансовые соотношения между переменными
	4.	Специальные условия для защиты интересов отдельных предприятий
	5	Требование типизации и стандартизации технического оснащения технических процессов (условия связности)

Рисунок 1. Типы ограничений

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

2. Двойственные задачи линейного программирования

2.1 Понятие двойственной задачи ЛП

Пусть задана каноническая задача ЛП

(2.1)

Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то

cx = cx+u(-Ax+b) = (c-uA)x+bu

Предположим, что и можно выбрать таким образом, чтобы иА ? с. Тогда при любых х?0 справедливо неравенство

сх?bи (2.2)

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

Если задана каноническая задача ЛП

(2.3)

то задача ЛП

(2.4)

называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к (D*, f*) называется прямой (или исходной).

2.2 Общая схема построения двойственной задачи

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

Если задана общая задача ЛП

(2.5)

где D определяется системой уравнений и неравенств

то двойственной по отношению к ней называется общая задача ЛП

(2.6)

где D* определяется системой уравнений и неравенств

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х_j?0 или u_i?0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (а^jи?с_j или a_ix?b_i).

5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, a_ix?b_i или а^jи?с_j), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (u_i?0 или х_j?0).

Из приведенного определения вытекает важное свойство -- симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей:

((D*)*, (f*)*)?(D, f),

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

В матричной форме пара двойственных общих задач линейного программирования может быть кратко записана как:

(2.3)

и

(2.7)

2.3 Пример построения двойственной задачи

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП

f_max(x)= 5x₁ -2x₂ +7x₃ +4x₄ -3x₅

D={xcR⁵ |

4x₁ +x₂ -x₃ +x₄ ?2,

5x₂ +x₃ -6x₄ +2x₅ =4,

2x₁ +3x₂ +6x₃ +x₄ -3x₅?5,

x_2, x₅?0 }

тогда двойственной к ней будет задача

f*_min(u)= 2u₁ +4u₂ +5u₃

D={ucR³ |

4u₁ +2u₃=5,

u₁ +5u₂ +3u₃? -2,

-u₁ + u₂ +6u₃=7,

u₁ -6u₂ + u₃=4,

2u₂ -3u₃? -3,

u_1, u₃?0 }

3. Решение задач

1. Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль при реализации детали А - 10 руб, детали В - 16 руб. Определить производственную программу, максимизирующую прибыль при условии: деталей А произвести не менее 300 ед., а деталей В не более 200 ед.

Станки	А	В	Время работы станка, ч
1	0,2	0,1	100
2	0,2	0,5	180
3	0,1	0,2	100

Решение:

Переменные решения:

x_{1 -} количество деталей А

x_{2 -} количество деталей В

Функция цели:

f(x)= 10x₁+16x₂ max

Ограничения:

0,2x₁+0,1x₂ ? 100

0,2x₁+0,5x₂ ? 180

0,1x₁+0,2x₂ ? 100

x₁ ? 300

x₂ ? 200

x_1, x₂ ? 0



Оптимальный план выпуска продукции
Станки	Время работы станка, ч	Детали
		А	В
1	100	0,2	0,1
2	180	0,2	0,5
3	100	0,1	0,2
Прибыль	10	16
	Х1	Х2		Ограничения
Переменные	400	200	1	100
			2	180
			3	80
	Целевая функция
Р	7200

Вывод: При производстве деталей А не менее 300 ед., а В - не более 200 ед. прибыль будет равна 7200 руб.

2. Площадь пашни в сельскохозяйственной организации составляет 3000 га, сенокосов - 1000 га, пастбищ -700 га. В хозяйстве возделываются пшеница, озимая рожь, овес, турнепс и картофель, животноводческий подкомплекс включает коров, молодняк КРС и овец. Для содержания одной коровы требуется 1,9 га пашни, 0,5 га сенокосов и 0,1 га пастбищ, молодняка КРС - 1 га пашни, 0,5 га сенокосов, 0,1 га пастбищ, овец - 0,3 га пашни, 0,09 га сенокосов, 0,05 га пастбищ. При необходимости не более 700 га пастбищ может быть трансформировано в пашню. Площадь зерновых должна быть не менее, чем в 7 раз больше площади пропашных. Хозяйство располагает трудовыми ресурсами в размере 200 тыс. чел.-ч. Затраты труда составляют на 1 га посевов пшеницы - 3 чел.-ч., озимой ржи - 2, овса - 2,1, турнепса - 65, картофеля - 65 чел.-ч., а на одну голову молодняка КРС - 95, корову - 205, голову овец - 8 чел.-ч. Объем производства молока в хозяйстве должен быть не менее 5000 ц, мяса - не менее 500 ц, шерсти -5 ц. Продуктивность животных на одну голову: овцы - 0,3 ц мяса, 0,035 ц шерсти, коров - 23 ц молока, молодняка КРС - 1,5 ц мяса. Поголовье молодняка КРС в структуре стада КРС должно быть не менее 50%. Прибыль от реализации продукции составляет с 1 га пшеницы -- 3, озимой ржи -- 2,6, овса -- 2,6, турнепса -- 4,5, картофеля - 6 тыс. руб., с одной головы овец - 0,9, коров - 3, молодняка КРС - 2,5 тыс. руб. Требуется разработать экономико-математическую модель производственно-отраслевой структуры организации, математическую запись модели привести к табличному виду, решить модель в ЭТ Excel. Критерий оптимальности - максимум прибыли.

Решение:

Системы переменных и ограничений:

I. Основные ограничения по использованию ресурсов организации:

1. по использованию пашней, га:

x₁ + x₂ + x₃ + x₄ + x₅ +1,9x₆ + x₇ +0,3x₈ ? 3000 + x₉

2. по использованию сенокосов, га:

0,5x₆ + 0,5x₇ +0,09x₈ ? 1000

3. по использованию пастбищ, га:

0,1x₆ + 0,1x₇ +0,05x₈+ x₉ ? 700

4. по использованию трудовых ресурсов, ч-часы:

3x₁ +2 x₂ + 2,1x₃ +65 x₄ + 65x₅ +205x₆ + 95x₇ +8x₈ ? 200000

II. Дополнительные ограничения:

5. по объему трансформации пастбищ в пашню:

x₉ ? 700

III. Основные ограничения по предельным размерам в структуре и соотношению посевных площадей с/х культур:

6. по соотношению площади под пропашными культурами:

x₁ + x₂ + x₃ ? 7( x₄ + x₅ )

IV. Основные ограничения по численности поголовья животных, их структура и соотношение:

7. по структуре стада КРС, гол.:

x₇ ? 0,5( x₆ + x₇ )

x₇ ? 0,5x₆ +0,5x₇

-0,5x₇ + x₇ - 0,5x₆ ? 0

0,5х₇ - 0,5х₆ ? 0

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

8. по минимальному объему производства молока, ц.:

23х₆ ? 5000

9. по минимальному объему производства мяса:

0,3x₈ +1,5x₇ ? 500

10. по минимальному объему производства шерсти:

0,035х₈ ? 5

двойственный линейное программирование

VI. Условие неотрицательности:

х₁ ч х₉ ? 0

Матем. запись функции цели:

F(х) = 3x₁ + 2,6x₂ + 2,6x₃ + 4,5x₄ + 6x₅ +3x₆ + 2,5x₇ +0,9x₈ > max

Матрицу ЭММ смотри в приложении 1.

Анализ результатов прямого и двойственного решения

Анализ прямого решения

Значения ограничений по решению (потребности, возможности)

Вид ресурсов (продуктов)	Тип ограничения	Размер ограничения	Потребности (возможности)	Отклонение
По пашне, га	<=	3000	3000	0
По сенокосам, га	<=	1000	274	726
По исп-ю пастбищ, га	<=	700	700	0
Труд.рес-сы, чел-часы	<=	200000	105620	94380
По объему трансф-и	<=	700	641	59
По соотн-ю площадей	>=	0	0	0
По числ-ти поголовья	>=	0	44	44
По мин об-му пр-ва молока	>=	5000	5000	0
По об-му пр-ва мяса	>=	500	500	0
По об-му пр-ва шерсти	>=	5	5	0

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

Анализ двойственного решения задачи

Анализ двойственных оценок переменных

Наименование переменной	Нормированная стоимость (градиент)	Допустимое увеличение	Допустимое уменьшение
знач перем х1	0	3	0,340659341
знач перем х2	0	0,40000009	1000000000000000000000000000000,0
знач перем х3	0	0,40000009	1000000000000000000000000000000,0
знач перем х4	-2	1,500000002	1000000000000000000000000000000,0
знач перем х5	0	1000000000000000000000000000000,0	1,499999997
знач перем х6	0	3,75	1000000000000000000000000000000,0
знач перем х7	0	1,2125	0,19375
знач перем х8	0	0,03875	1000000000000000000000000000000,0
знач перем х9	0	1000000000000000000000000000000,0	1,29166667

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

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

Анализ двойственных оценок ограничений

Наименование ограничения	Теневая цена (коэффициент Лангранжа)	Допустимое увеличение	Допустимое уменьшение
1. по пашне, га потребн	3	8779,513217	2879,979296
2.по сенокосам, га потребн	0	1000000000000000000000000000000,0	726,0662526
3. по исп-ю пастбищ, га потребн	3	59,35817805	640,6418219
4. трудовые ресурсы, чел.-час потребн	0	1000000000000000000000000000000,0	94379,76708
5. По объему трансформации потребн	0	1000000000000000000000000000000,0	59,35817805
6. по соотношению площадей потребн	0	2879,979296	12178,03446
7. по численности поголовья потребн	0	43,68530021	1000000000000000000000000000000,00
8. по мин объему произ-ва молока потребн	0	2009,52381	5000
9. по объему пр-ва мяса потребн	-1	1702,06974	131,0559006
10. по объему пр-ва шерсти потребн	-1	15,28985507	5

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

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

Вывод: оптимальный план производства в сельскохозяйственной организации: 2520 га пшеницы, 360 га картофеля, 217 коров, 305 молодняка, 143 овцы, 641 трансформации. При этом достигается максимальная прибыль в 11236 единиц.

Размещено на Allbest.ru