Методы оптимальных решений (стр. 1 )

Кузнецкий институт информационных и управленческих технологий (филиал)

ФГБОУ ВПО «Пензенский государственный университет»

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

Методические указания по выполнению контрольной работы

2013

Общая характеристика работы

Контрольная работа рассчитана для студентов заочной формы обучения по направлению подготовки 080100.62 «Экономика».

Контрольная работа включает 25 вариантов, в каждом из которых теоретический вопрос и два практических задания. Вариант работы студента соответствует номеру в журнале преподавателя (вариант см. в приложении А).

В процессе выполнения работы студент:

· углубляет теоретические и практические знания по методам нахождения оптимальных решений линейных и нелинейных задач математического программирования;

· развивает логическое и алгоритмическое мышление;

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

· приобретает умение применять различные методы теории оптимизации для решения различных экономических задач;

· составляет математические модели экономических задач и находит оптимальное решение различными методами.

Требования к оформлению курсовой работы

1. Работа начинается с титульного листа (см. сайт КИИУТ)

2. Вариант работы соответствует порядковому номеру студента.

3. Контрольная работа должна содержать следующие структурные разделы: задание (с указанием номера варианта), содержание, введение, основная часть, список литературы.

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

•Введение – во введении указываются цели работы и используемые информационные технологии

• Содержание - подробное содержание работы с указанием номеров страниц. Для теоретического вопроса оно должно быть особенно детальным (с разделами и подразделами), чтобы облегчить поиск материала.

• Основная часть состоит из следующих разделов:

Ø 1 - раскрывается тема, даются теоретические основы выполняемого задания;

Ø 2 – практическое задание - составление математической модели и решение задачи линейного программирования геометрически

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

Ø 4 - практическое задание - составление математической модели и решение транспортной задачи.

• Список литературы, которая была использована при выполнении контрольной работы.

4. Общий объем контрольной работы должен составлять 25-35 листов формата А4 (210x297 мм).

5. Контрольную работу набирают на компьютере в текстовом редакторе. Решение для практических заданий допустимо писать от руки (на листах формата А4)

6. Параметры печатной страницы: отступы - 2см (верхнее и нижнее поля), 3 см — левое, 1.5 см — правое поля.

7. Шрифт: Times New Roman, размер - 14 пт, междустрочный интервал - полуторный.

Пример содержания

Введение 3

1. Теоретический вопрос. Тема по варианту. 4

1.1 Подпункт согласно теме 4

1.2 Подпункт согласно теме 10

2. Симплекс-метод решения задачи линейного программирования. 12

2.1 Постановка задачи 12

2.2 Математическая модель задачи. 14

2.3 Геометрическое решение задачи 15

2.4 Решение задачи симплекс-методом. 19

3. Транспортная задача 21

3.1 Постановка задачи. 21

3.2 Математическая модель задачи. 23

3.3 Решение транспортной задачи. 26

Литература 29

Задание 1. Теоретический вопрос.

1. Экстремумы и их классификация.

2. Формализация проблем управления в экономике.

3. Схемы принятия управленческих решений

4. Математические модели операций.

5. Математическое программирование.

6. Виды задач линейного программирования.

7. Геометрическая интерпретация задачи линейного программирования.

8. Экономическая и геометрическая интерпретации задачи нелинейного программирования.

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

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

11. Общая задача целочисленного программирования

12. Метод Гомори решения задачи целочисленного программирования.

13. Общая постановка задачи динамического программирования.

14. Выпуклые множества и выпуклые функции.

15. Задачи выпуклого программирования.

16. Задачи квадратичного программирования.

17. Метод множителей Лагранжа.

18. Принцип оптимальности и уравнения Беллмана.

19. Функции полезности, спроса, кривые безразличия.

20. Многокритериальные задачи оптимизации.

21. Оптимальность по Парето или Слейтеру.

22. Принятие решений при наличии возмущений.

23. Игровой подход к управлению.

24. Вероятностный подход к управлению.

25. Игровые принципы равновесных решений.

Задание 2. Симплекс-метод решения задачи линейного программирования

Методические указания

Рассмотрим пример.

2.1 Постановка задачи

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

Вид сырья	Нормы расхода сырья (кг) на одно изделие	Общее количество сырья (кг)
А	В
I	12	4	300
II	4	4	120
III	3	12	252
Прибыль от реализации одного изделия (руб.)	30	40

Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной. Составить математическую модель задачи, решить задачу геометрически и симплекс-методом.

2.2. Математическая модель задачи

Искомый выпуск изделий А обозначим через х1 изделий В - через х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные х1, х2 должны удовлетворять следующей системе неравенств:

12х1 + 4х2 ≤ 300,

4х1 + 4х2 ≤ 120, (1)

3х1 + 12х2 ≤ 252.

Общая прибыль произведенной предприятием продукции составляет

F = 30х1 + 40х2. (2)

По своему экономическому содержанию переменные х1 и х2 могут принимать только лишь неотрицательные значения:

х1, х2 > 0. (3)

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

2.3 Геометрическое решение задачи

Сначала определим многоугольник решений

1) 12х1 + 4х2 = 300

х2 =х1

2) 4х1 + 4х2 = 120

х2 = 30 - х1

3) 3х1 + 12х2 = 252

4)

5)

Многоугольник решений – OABCD

Построим линию уровня

x1	0	20
x2	12	-3

Построим вектор .

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

Эта точка – В. Точка пересечения второй и третьей линии:

В(12; 18)

Найдем значение целевой функции в этой точке:

F(12; 18) = 30×12 + 40×18 = 1080

Ответ: план выпуска: Х = (12; 18), F(Х) = 1080.

2.4 Решение задачи симплекс-методом

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

12х1 + 4х2 + х3 = 300,

4х1 + 4х2 + х4 = 120,

3х1 + 12х2 + х5 = 252.

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, х3 - это неиспользуемое количество сырья I вида.

Преобразованную систему уравнений запишем в векторной форме:

x1P1 + x2P2 + x3P3 + x4P4 + x5P5 =P0,

где

; ; ; ; ; .

Поскольку среди векторов P1, P2, P3, P4, P5 имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план X = (0, 0, 300, 120, 252), определяемый системой трехмерных единичных векторов P3 , P4 , P5, которые образуют базис трехмерного векторного пространства.

Составляем симплексную таблицу I итерации (табл. 1):

Вычисления в 4-ой (m+1)-й строке:

;

;

;

;

;

;

;

;

;

Таблица 1.

i	Базис	Сб	Р0	30	40	0	0	0
P1	P2	P3	P4	P5
1	P3	0	300	12	4	1	0	0
2	P4	0	120	4	4	0	1	0
3	P5	0	252	3	12	0	0	1
4			0	-30	-40	0	0	0

Целевая функция равна нулю (ничего не производится, сырье не тратиться – план не оптимальный).