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

Содержание

Введение

1. Описание отрасли………………………………………………………….3
2. Задача оптимального распределения ресурсов………………………….5
3. Транспортная задача………………………………………………….…..21
4. Задача теории игр…………………………………………………………24
5. Обоснование распределения финансовых ресурсов между  проектами (динамическое программирование).....……………………………..…...29

Заключение…………………………..……………………………………..……33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

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

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

Основные задачи:

- научиться строить экономико-математические  модели;

- освоить симплекс-метод табличного  решения задачи линейного программирования;

- освоить двойственный симплекс-метод  решения задачи линейного программирования;

- освоить метод потенциалов  решения транспортной задачи;

- освоить методику решения антагонистических  игр;

- освоить методику  решения задачи динамического  программирования.

 

 

 

 

 

 

 

 

 

 

 

 

Описание отрасли.

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

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

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

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

На основании данной тематики:

(ресурс 1) – шелк;

(ресурс 2) – хлопок;

(ресурс 3) – лен.

 

(изделие 1) – одеяло;

(изделие 2) – халат;

(изделие 3) – полотенце.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Построение экономико-математической модели задачи распределения ресурсов

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

Представим исходные данные варианта 7 в виде таблицы 1.

Таблица 1 - Исходные данные

Норма затрат Ресурсы		Виды изделий			Запас ресурсов	Скрытые цены ресурсов
						yi	yi*
		3	1	2	30
		2	3	4	20
		1	2	6	52
Цена единицы изделия		4	6	8	fmax(х)	gmin(у)
План выпуска	xj
	xj*

 

 

Введем переменные: х₁ – объем производства продукции первого вида; х₂ – объем производства продукции второго вида; х₃ – объем производства продукции третьего вида.

Целевая функция, отражающая доход от реализации произведенной  продукции, представляет собой сумму  произведений объема производства каждого  вида продукции на значение ее цены:

,

где n – количество видов продукции.

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

,

где m – количество ресурсов.

Также должно выполняться  условие не отрицательности переменных:

.

Таким образом, экономико-математическая модель прямой задачи линейного программирования (ПЗЛП) варианта 0 имеет вид:

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

Данная ПЗЛП имеет стандартную форму записи, поскольку в задаче на максимум все функциональные (ресурсные) ограничения имеют знаки «меньше или равно».

 

2. Построение двойственной задачи к задаче распределения ресурсов

Для построения двойственной задачи линейного программирования (ДЗЛП) следует ввести двойственные переменные: у₁ – скрытая цена первого ресурса; у₂ – скрытая цена второго ресурса; у₃ – скрытая цена третьего ресурса.

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

.

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

.

Должно выполняться  условие неотрицательности переменных:

.

Также для построения ДЗЛП можно руководствоваться следующими правилами.

1. В первой задаче  определяется максимум линейной  целевой функции, во второй  – минимум.

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

3. Каждая из задач  задана в стандартной форме,  при этом в задаче максимизации  все неравенства вида «меньше  или равно», а в задаче минимизации  все неравенства вида «больше или равно».

4. Матрицы коэффициентов  при переменных в системах  ограничений обеих задач являются  транспонированными друг к другу.  Для варианта 0 матрица коэффициентов  при переменных в системе ограничений  ПЗЛП имеет вид:

.

Тогда транспонированная матрица, отражающая коэффициенты при переменных в системе ограничений ДЗЛП, имеет  вид:

.

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

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

Таким образом, экономико-математическая модель ДЗЛП варианта 0 имеет вид:

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

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

3. Решение прямой и двойственной задач линейного программирования

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

Для ПЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме  записи ПЗЛП варианта 44 следует добавить дополнительные переменные х₄, х₅, х₆, в соответствующие неравенства со знаком «+», поскольку они отражают возможный остаток неиспользованных ресурсов:

Для ДЗЛП каноническая форма  записи имеет вид:

Для перехода к канонической форме записи ДЗЛП варианта 0 следует  добавить дополнительные переменные y₄, y₅, y₆, в соответствующие неравенства со знаком «-», поскольку они отражают возможное превышение затрат на приобретение ресурсов над ценой реализации продукции (возможный убыток от производства продукции):

 

Соответствие переменных прямой и двойственной задачи

Во взаимодвойственных задачах  линейного программирования первоначальным переменным ПЗЛП соответствуют дополнительные переменные ДЗЛП и аналогично первоначальным переменным ДЗЛП соответствуют дополнительные переменные ПЗЛП.

Установим соответствие переменных прямой и двойственной задачи для варианта 0:

х1 y4

х2 y5

х3 y6

х4 y1

х5 y2

х6 у3

 

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

А. Одновременное решение ПЗЛП и ДЗЛП с помощью симплекс-таблиц.

Б. Двойственный симплекс-метод.

Рассмотрим оба метода.

 

А. Одновременное решение ПЗЛП и ДЗЛП с помощью симплекс-таблиц

Решаем ПЗЛП.

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

В рассматриваемом варианте в первую строку с_j вносим значения коэффициентов при переменных из целевой функции 3, 10 и 4, остальные значения равны нулю. В столбец базисных переменных вносим дополнительные переменные х₄, х₅, х₆. В рассматриваемом случае базисные переменные не входят в целевую функцию, поэтому им соответствуют нулевые значения в столбце с_i.

Рабочее поле таблицы (столбцы под  переменными х₁, х₂, х₃, х₄, х₅, х₆) заполняем коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП.

Поскольку, в первом равенстве отсутствуют  переменные х₅ и х₆, поэтому в первой рабочей строке симплекс-таблицы этим переменным соответствует коэффициент «0».

 

сi	сj	4	6	8	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	3	1	2	1	0	0	30
0	x5	2	3	4	0	1	0	20
0	х6	1	2	6	0	0	1	52
Dj

 

Заполняем индексную  строку:

D₁ = 0×3 + 0×1 + 0×2 – 4 = -4;

D₂ = 0×1 + 0×3 + 0×2 – 6 = -6;

D₃ = 0×1 + 0×2 + 0×6 – 8 = -8;

D₄ = 0; D₅ = 0; D₆ = 0;

D₇= 0×30 + 0×20 + 0×52 = 0.

 

сi	сj	4	6	8	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	3	1	2	1	0	0	30
0	x5	2	3	4	0	1	0	20
0	х6	1	2	6	0	0	1	52
Dj		-4	-6	-8	0	0	0	0

 

Первое опорное решение имеет вид: = (0, 0, 0, 30, 20, 52), = 0. (компоненты опорного решения выписывают для базисных переменных из столбца свободных членов b_i; переменные, не входящие в базис, имеют значение 0). В рассматриваемом случае переменные х₁, х₂, х₃. не входят в базис, поэтому их компоненты в опорном решении равны нулю, базисные переменные имеют значения х₄ = 30, х₅ = 20, х₆ = 52. Значение целевой функции берут из последней строки столбца . На данном шаге симплекс-метода = 0.

Следует проверить первое опорное решение на оптимальность.

В рассматриваемом случае первое опорное решение не оптимальное, поскольку имеются три отрицательные  оценки D₁ = - 4, D₂ = - 6,

D₃ = - 8.

Следовательно, нужно сделать следующий шаг симплекс-метода: ввести в базис переменную, которую нужно улучшить.

Такой переменной является переменная из столбца с наибольшей по абсолютной величине оценкой |D₃| = 8, т.е. переменная х₃.

 

сi	сj	4	6	8	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x4	3	1	2	1	0	0	30	30/2
0	x5	2	3	“4”	0	1	0	20	20/4
0	х6	1	2	6	0	0	1	52	52/6
Dj		-4	-6	-8	0	0	0	0	-

 

Теперь следует определить, какую переменную нужно вывести  из базиса.

В столбце оценочных отношений min{b_i/ h_ij} отражены отношения свободных членов к элементам из разрешающего столбца, минимальным является отношение 20/4, соответствующее строке переменной х₅, следовательно, эта строка – разрешающая, а переменная х₆ выводится из базисных переменных. На пересечении ключевой строки и ключевого столбца находится ключевой элемент «4».

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

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

В строке, соответствующей  переменной х₃ переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «4»:

 

сi	сj	4	6	8	0	0	0		min
	Базисные переменные (БП)	х1	x2	х3	х4	х5	х6	bi	bi/ hij
0	x4			0	1		0
8	x3	1/2	3/4	1	0	1/4	0	5
0	x6			0	0		1
Dj				0	0		0

 

Заполняем столбцы для базисных переменных х₄, х₃, х₆:

сi	сj	4	6	8	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x4
8	x3
0	x6
Dj

Остальные клетки заполняем  по правилу прямоугольника, отмечая, что ключевой элемент «4» находится в первой строке и втором столбце предыдущей таблицы:

;

;

;

;

;

;

;

сi	сj	4	6	8	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x4	2	-1/2	0	1	-2	0	20
8	x3	1/2	3/4	1	0	1/4	0	5
0	x6	-2	-5/2	0	0	-6	1	22
Dj				0	0		0

.

Находим оценки переменных:

D₁ =0.2 + 8×1/2 + 0×(-2)– 4 = 0;

D₂ = 0.(-1/2) + 8×3/4 + 0×(-5/2) – 6 = 0 ;

D₅ = 0.(-2) + 8.1/4 + 0×1 – 0 = 2 ;

D₇ = 0.(20) + 8×5 + 0×(22) = 40.

 

сi	сj	3	4	1	0	0	0		min
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi	bi/ hij
0	x4	2	-1/2	0	1	-2	0	20
8	x3	1/2	3/4	1	0	1/4	0	5
0	x6	-2	-5/2	0	0	-6	1	22
Dj		0	0	0	0	2	0	40

 

Поскольку все оценки положительные D_j, то полученное опорное решение является оптимальным: = (0, 0, 5, 20, 0, 22), а максимальное значение целевой функции равно = 40.

 

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

 

сi	сj	4	6	8	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	2	-1/2	0	1	-2	0	20
8	x3	1/2	3/4	1	0	1/4	0	5
0	x6	-2	-5/2	0	0	-6	1	22
Dj		0	0	0	0	2	0	40
yi		y4	y5	y6	y1	y2	y3

 

Таким образом, = (0,2,0,0,0,0), поскольку y₁ « x₄, y₂ « x₅, y₃ « x₆, y₄ « x₁, y₅ « x₂, y₆ « x₃. Значение целевой функции = 40.

Экономический смысл всех переменных, участвующих  в решении

Экономический смысл  переменных, участвующих в решении  отражен в таблице