М-задача линейного программирования

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

По дисциплине

«Высшая математика (математическое программирование)»

Для студентов заочной формы обучения

Гродно 2009

Содержание

Требования по оформлению контрольной работы.. 3

ТЕМА 1. Симплекс метод. Двойственность. 4

М-задача линейного программирования. 4

Вопросы для самопроверки по теме 1. 5

ТЕМА 2. Транспортная задача. 8

Вопросы для самопроверки по теме 2. 10

ТЕМА 3. Метод динамического программирования. 11

Вопросы для самопроверки по теме 3. 13

ТЕМА 4. Решение задач линейного программирования графическим способом. Задачи целочисленного линейного программирования. 14

Вопросы для самопроверки по теме 4. 18

Рекомендуемая литература. 19

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

по курсу «Высшая математика. Математическое программирование»

Для студентов заочной формы обучения

специальностей «Экономика и управление на предприятии», «Финансы и кредит», «Бухгалтерский учет»

1) Работа оформляется в ученической тетради рукописным образом.

2) Работа должна иметь титульный лист (см.Приложение 1), на котором указаны

a. Фамилия и инициалы студента

b. Название факультета, курса, группы

c. Номер зачетной книжки,

d. номер варианта (совпадает с номером фамилии в списке группы в журнале)

e. форма для выставления преподавателем отметки о выполнении:

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

4) Оформленные решенные задачи следует располагать в порядке возрастания номеров задач. Каждая новая задача должна начинаться с новой страницы.

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

6) Рисунки должны быть выполнены с использованием чертежных инструментов и в достаточно крупном масштабе.

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

8) В конце каждого задания следует записать слово «ответ» и выписать полностью ответ и необходимые к нему комментарии.

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

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

Работы, выполненные без соблюдения указанных правил, не зачитываются и возвращаются студенту для переработки

ТЕМА 1. Симплекс метод. Двойственность.

М-задача линейного программирования

Задача линейного программирования имеет вид:

Значения параметров с_j, b_i, a_ij, i= , j= ; задачи заданы в таблице

Требуется:

1) Записать модель задачи линейного программирования с численными значениями параметров

2) решить построенную задачу линейного программирования;

3) записать математическую модель двойственной задачи

4) используя решение прямой задачи найти с помощью условий дополняющей нежесткости решение двойственной задачи.

Вопросы для самопроверки по теме 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. как от ЗЛП на минимум перейти к ЗЛП на максимум?

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. Сформулируйте в экономических терминах задачу об оптимальном использовании сырья.

61. Запишите общий вид модели задачи об оптимальном использовании сырья, двойственной к производственной задаче.

62. Какое экономическое содержание имеют переменные задачи об оптимальном использовании сырья?

63. Какое экономическое содержание имеет целевая функция задачи об оптимальном использовании сырья?

64. Какое экономическое содержание имеют ограничения в задаче об оптимальном использовании сырья?

65. Что является решением задачи об оптимальном использовании сырья?

66. Опишите правила построения двойственной задачи для ЗЛП на максимум.

67. Как связаны значения целевых функций на произвольны планах прямой и двойственной ЗЛП?

68. Что можно сказать о решении двойственной ЗЛП, если целевая функция прямой ЗЛП неограниченно возрастает на множестве планов?

69. Что можно сказать о решении двойственной ЗЛП, если множество планов прямой ЗЛП пусто?

70. Что можно сказать о решении двойственной ЗЛП, если прямая ЗЛП имеет решение?

71. Как связаны значения прямой и двойственной целевой функции на оптимальных планах соответствующих задач?

72. Как по решению прямой задачи построить решение двойственной задачи?

73. Сформулируйте и поясните условия дополнительной нежесткости.

74. Как по решению прямой ЗЛП в симметричной форме табличным симплекс-методом можно найти решение двойственной ЗЛП?

М-задача