Бузулукский гуманитарно-технологический институт (филиал)

Бузулукский гуманитарно-технологический институт (филиал)

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

Высшего профессионального образования

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

Кафедра физики, информатики, математики

Рассмотрено

на заседании кафедры

«__» ____________ 2012 г.

Зав. кафедрой_____________

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

Составитель: Ахматова Д.Н.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНЫХ РАБОТ

Бузулук 2012 г

.

Рецензент

Кандидат физико-математических наук, доцент Трофимова Е.Б.

Ахматова Д.Н.

Методы оптимальных решений: методические указания по выполнению контрольных работ.- Бузулук: БГТИ (филиал) ГОУ ОГУ, 2012.- 17с.

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

Работа предназначена в помощь студентам заочной формы обучения.

© Ахматова Д.Н.,2012

© БГТИ (филиал) ГОУ ОГУ, 2012

Пояснительная записка

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

Работа должна быть оформлена на листах формата А4. Рекомендуется, при выполнении работы, оставлять поля 3-4 см и в конце работы несколько чистых страниц для замечаний рецензента.

Контрольная работа состоит из 6 заданий по 10 вариантов в каждом. Номер варианта определяется по первой букве фамилии студента в соответствии с таблицей 1. Задания варианта выполняются последовательно в установленном порядке. Перед решением задачи необходимо указать ее номер и записать полностью ее условие. Решение задачи следует выполнять строго по отдельным пунктам, каждый из них сопровождая пояснениями; записывать формулу в общем виде, а затем подставлять конкретные значения; записывать полученный ответ.

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

Работы, выполненные без соблюдения этих правил, на рецензию не принимаются и возвращаются для переработки.

Таблица 1

Номера заданий каждого варианта определяются по таблице 2.

Таблица 2.

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

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

Тема. Метод Гомори

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

Дополнительное ограничение отсекает часть области, содержащую нецелочисленное оптимальное решение.

Вновь полученную задачу решают методом линейного программирования. Процесс построения сечений и решения задачи повторяется до получения целочисленного оптимального решения.

Алгоритм метода Гомори

Пусть дана полностью ЦЗЛП

(*)

1) Отбросив условие целочисленности, решим исходную задачу симплексным методом.

Пусть на последнем шаге симплексного метода получили таблицу:

i	БП	C б	b i		…		…			…
			…			…
… i … m	… …	… …	… …	… …		… …	…	… …	… …	…	… …
m+1							…			…

Этой таблице соответствует система ограничений

Оптимальное решение имеет вид (). Если получится целочисленное оптимальное решение, то задача решена. Если в оптимальном решении не все переменные целочисленные, то строим сечение.

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

.

Для этого уравнения строим неравенство , где - дробные части чисел.

3) Присоединяя неравенство к ранее решенной задачи, получим новую задачу линейного программирования, которую решаем двойственным симплексным методом; если ее оптимальное решение окажется целочисленным, то оно и будет оптимальным решением исходной задачи. Если снова получится нецелочисленное решение, то строим новое сечение и т.д.

Задание № 1

1-10. В пунктах А₁, А₂, А₃ производится однородная продукция в количествах а₁, а₂, а₃ единиц. Готовая продукция поставляется в пункты В₁, В₂, В₃, В₄, потребности которых составляют b₁, b₂, b₃, b₄ единиц. Стоимости с_ij перевозок единицы продукции из пункта А_i в пункт В_j заданы матрицей . Требуется найти оптимальный план методом дифференциальных рент.

1. а₁= 500 а₂= 200 а₃= 600 b₁= 250 b₂= 150 b₃= 350 b₄= 250

2. а₁= 500 а₂= 900 а₃= 100 b₁= 200 b₂= 650 b₃= 150 b₄= 300

3. а₁= 200 а₂= 500 а₃= 300 b₁= 150 b₂= 450 b₃= 50 b₄= 50

4. а₁= 250 а₂= 650 а₃= 300 b₁= 350 b₂= 50 b₃= 150 b₄= 450

5. а₁= 350 а₂= 750 а₃= 300 b₁= 200 b₂= 50 b₃= 600 b₄= 400

6. а₁= 450 а₂= 200 а₃= 350 b₁= 150 b₂= 300 b₃= 50 b₄= 400

7. а₁= 300 а₂= 700 а₃= 400 b₁= 250 b₂= 450 b₃= 150 b₄= 350

8. а₁= 250 а₂= 550 а₃= 350 b₁= 300 b₂= 150 b₃= 400 b₄= 150

9. а₁= 750 а₂= 200 а₃= 550 b₁= 450 b₂= 300 b₃= 350 b₄= 250

10. а₁= 400 а₂= 300 а₃= 500 b₁= 350 b₂= 250 b₃= 150 b₄= 250

Задание № 2

11-20. Решить методом Гомори.

11.	12.	13.	14.	15.
16.	17.	18.	19.	20.

Задание № 3

2 1-30. Найти необходимый размер компенсации для задачи

U (x₁; x₂)

,

если произошло изменение цены на один из товаров.

Все необходимые числовые данные приведены в таблице 3.

Таблица 3.

Номер задачи	U (x1; x2)	=(Р1; Р2)	I	Изменение цены
		(4; 5)		цена на первый товар увеличиться до 8 денежных единиц
	3x13 · x22	(3; 10)		цена на второй товар увеличиться до 20 денежных единиц
		(3; 6)		цена на первый товар увеличиться до 7 денежных единиц
		(10; 5)		цена на второй товар увеличиться до 7 денежных единиц
		(2; 5)		цена на первый товар увеличиться до 5 денежных единиц
	4x12 · x23	(1; 2)		цена на второй товар увеличиться до 4 денежных единиц
		(5; 2)		цена на первый товар увеличиться до 7 денежных единиц
		(1; 4)		цена на второй товар увеличиться до 7 денежных единиц
		(5; 5)		цена на первый товар увеличиться до 9 денежных единиц
	3x1 · x23	(5; 1)		цена на второй товар увеличиться до 3 денежных единиц

Задание № 4

31-40. Решить игру сведением к задаче линейного программирования. Платежные матрицы имеют вид:

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

31.	32.	33.	34.	35.
36.	37.	38.	39.	40.

Задание № 5

41-50. Найти наибольшее и наименьше значения функции при заданных ограничениях.

41.	42.
43.	44.
45.	46.
47.	48.
49.	50.

Задание № 6

51-60. Для реконструкции и модернизации производства на n предприятиях выделены денежные средства с. По каждому из n предприятий известен возможный прирост () выпуска продукции в зависимости от выделенной ему суммы x (). Требуется с помощью метода динамического программирования распределить средства с между предприятиями так, чтобы суммарный прирост выпуска продукции на всех n предприятиях достиг максимальной величины (этот основной результат задачи получить для с =100 млн ден. ед. и n =4).

Все необходимые числовые данные приведены в таблице 4.

Таблица 4.

Номер задачи	Предприятие	Прирост выпуска продукции на i -м предприятии млн ден.ед.	Часть средств, выделяемых предприятием, млн ден.ед
	№1
	№2
	№3
	№4

Контрольные вопросы:

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. Определение опорного плана транспортной задачи методом «северо-западного угла»

26. Закрытая модель транспортной задачи

27. Открытая модель транспортной задачи

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

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

30. Общая постановка задачи нелинейного программирования. Теорема Куна-Таккера

31. Основные понятия теории игр.

32. Классификация игр

33. Решение матричных игр в чистых стратегиях

34. Решение матричных игр в смешанных стратегиях

35. Основные понятия теории игр. Доминирование стратегий

36. Методы решения матричных игр без седловой точки

37. Принцип оптимальности. Уравнение Беллмана

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

39. Определение функции полезности.

40. Свойства функции полезности

41. Кривые безразличия.

42. Свойства кривых безразличия

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

44. Решение задачи потребительского выбора методом множителей Лагранжа

45. Функции спроса. Свойства функции спроса

46. Геометрическое представление изменения спроса при изменении цен и дохода: кривые «доход-потребление», кривые «цена-потребление»

47. Коэффициенты эластичности спроса по ценам и доходу.

48. Свойства коэффициентов эластичности

49. Факторы, определяющие эластичность спроса

50. Коэффициенты эластичности. Эластичность спроса по цене (прямая).

51. Эластичность спроса по доходу.

52. Коэффициенты эластичности. Перекрестная эластичность спроса по цене

53. Общие свойства производственных функций

54. Доминирование и оптимальность по Парето

55. Эффективные решения и паретова граница

56. Основные методы решения многокритериальных задач

57. Метод обобщенного критерия

58. Методы параметрического программирования

59. Теорема Неймана

60. Матричная игра как задача линейного программирования

7 Учебно-методическое обеспечение дисциплины

7.1 Основная литература

1. Экономико-математическое моделирование: учебник/ Под ред.И.Н. Дрогобыцкого. - М.: ЭКЗАМЕН, 2006. - 798 с - ISBN 5-472-01573-1.

2. Экономико-математические методы и прикладные модели: учеб.пособие для вузов/ под ред.В.В. Федосеева. - М.: ЮНИТИ, 2002. - 391 с - ISBN 5-238-00068-5.

3. Красс, М.С. Математика для экономического бакалавриата: Учебник/ М.С. Красс, Б.П. Чупрынов. - М.: Дело, 2005. - 576 с - ISBN 5-7749-0404-0.

4. Красс, М. С. Математика для экономистов: учеб.пособие для вузов/ М. С. Красс, Б.П. Чупрынов. - CПб.: Питер, 2005. - 464 с. - (Учебное пособие). - Библиогр.: с. 461. - Предм.указ.: с. 462-464. - ISBN 5-94723-672-9.

5. Лабскер, Л. Г. Игровые методы в управлении экономикой и бизнесом: учеб. пособие для вузов / Л. Г. Лабскер, Л. О. Бабешко; Акад. нар. хоз-ва при Правительстве РФ. - М.: Дело, 2001. - 464 с - ISBN 5-7749-0233-1.

7.2 Дополнительная литература

1. Красс, М. С. Математика для экономических специальностей: учеб. для вузов/ М. С. Красс. - М.: Дело, 2003. - 704 с - ISBN 5-7749-0264-1.

2. Исследование операций в экономике: учеб. пособие для вузов/ под ред. Н.Ш. Кремера. - М.: ЮНИТИ, 2004. - 407 с. - Библиогр.: с. 393-402. - ISBN 5-238-00636-5

3. Шелобаев, С. И. Математические методы и модели в экономике, финансах, бизнесе: учеб. пособие для вузов/ С.И. Шелобаев. - М.: ЮНИТИ-ДАНА, 2001. - 367 с.

4. Бережная, Е. В. Математические методы моделирования экономических систем: учеб.пособие для вузов/ Е. В. Бережная, В. И. Бережной. - М.: Финансы и статистика, 2002. - 368 с.: ил. - ISBN 5-279-02291-8.

5. Коршунова Н.И., Плясунов В.С. Математика в экономике: - М.: Издательство «Вита - Пресс», 2001.- 368с.

6. Замков, О. О. Математические методы в экономике: учебник / О. О. Замков, А. В. Толстопятенко, Ю. Н. Черемных; общ. ред. А. В. Сидорович.- 4-е изд. стер. - М.: Дело и Сервис, 2004. - 368 с. - (Учебники МГУ им. М. В. Ломоносова) - ISBN 5-86509-054-2.

7. Акулич, И.Л. Математическое программирование в примерах и задачах: учеб.пособие/ И.Л. Акулич.- 2- е изд., испр. - CПб.: Лань, 2009. - 348 с.: ил... - Библиогр.: с. 346-347 - ISBN 978-5-8114-0916-7.

8. Вентцель, Е. С. Исследование операций: задачи, принципы, методология: учеб.пособие для вузов/ Е. С. Вентцель.- 3-е изд., стер. - М.: Дрофа, 2004. - 208 с.: ил. - (Высшее образование). - Библиогр.: с. 206. - ISBN 5-7107-7770-6.

Бузулукский гуманитарно-технологический институт (филиал)

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: