Перечень практических заданий

Пункты отправления

Пункты назначения

Потребности

1. Составить экономико-математическую модель задачи.

2. Решить задачу линейного программирования графическим методом.

3. Решить задачу симплекс-методом.

4. Для приведенной задачи записать двойственную.

5. Построить симплексную таблицу и определить начальный опорный план для M-задачи.

6. Построить исходный опорный план транспортной задачи 2-мя способами. Вычислить значение функции. Сравнить полученные результаты.

7. Решить транспортную задачу.

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

9. Построить остовое дерево графа (алгоритм Прима, алгоритм Крускала).

10. Для заданного графа применить алгоритм Дейкстры.

11. Дана сеть из n вершин. На сети указаны пропускные способности ребер(в обоих направлениях одинаковые). Построить максимальный поток из I в S.

12. Построить линейный график комплекса работ и определить критический срок и сроки начала и окончания работ без учета ограничения на количество рабочих.

13. Найти решение задачи целочисленного линейного программирования методом Гомори (методом отсечений).

Задания для домашних контрольных работ и методические рекомендации по их выполнению

1. Выбор варианта задания для выполнения ДКР осуществляется по последней цифре индивидуального шифра учащегося.

2. Для допуска к экзамену необходимо получить зачет по выполнению ДКР.

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

4. В работу должны быть включены все 3 задания, соответствующие варианту. Два теоретических вопроса и одно практическое задание. Контрольные работы, содержащие не все задания, а также содержащие задачи не своего варианта, не засчитываются.

5. Решения задачи следует излагать подробно и аккуратно, объясняя и мотивируя все действия по ходу решения и делая необходимые чертежи.

6. В случае получения проверенной работы, как не зачтённой, учащийся должен исправить все отмеченные преподавателем ошибки и недочеты и прислать ДКР для повторной проверки, в короткий срок.

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

Две последние цифры номера зачетной книжки студента	Номер темы контрольной работы для 1-го и 2-го теоретических заданий	Номер практического задания
	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

ПЕРЕЧЕНЬ ТЕОРЕТИЧЕСКИХ ВОПРОСОВ контрольной работы:

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. Задача линейного программирования с n- переменными, способы решения.

30. Основные этапы симплекс-метода, характеристика каждого этапа.

31. Сравнительная характеристика основных методов решения задач линейного программирования.

32. Задачи линейного программирования. Постановка, математическая модель. Способы решения.

33. Нахождение кратчайших путей в графе (алгоритм Флойда).

34. Транспортная задача. Построение исходного опорного плана методом минимального элемента.

35. Графический метод решения ЗЛП.

36. Симплексный метод. Построение начального опорного плана. Базисные переменные, их характеристика

37. Построение минимального остовного дерева графа (алгоритм Крускала).

38. Транспортная задача в сетевой постановке.

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

40. Графическая интерпретация симплексного метода.

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

42. Приведение системы ограничений к каноническому виду.

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

44. Метод Монте-Карло. Суть метода. Применение.

Условие практического задания:

Имеется три поставщика и четыре потребителя некоторой продукции. Количество груза a_i, которое может отгрузить поставщик i , стоимость перевозки из пункта i в пункт j единицы груза c_ij, и потребности потребителей в грузе b_j, , таблицей:

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

Примечания:

План решения ТЗ:

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

2) Проверить план на оптимальность (с помощью метода потенциалов).

3) Найти оптимальный план транспортной задачи с помощью метода потенциалов.

ПЕРЕЧЕНЬ практических заданий контрольной работы

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

10.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

11.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

12.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

13.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

14.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

15.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

16.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

17.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

18.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

19.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

20.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

21.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

22.

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4
А1
А2
А3
Потребности

Пример решения типовой задачи контрольной работы

Примечания:

План решения ТЗ:

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

2) Проверить план на оптимальность (с помощью метода потенциалов).

3) Найти оптимальный план транспортной задачи с помощью метода потенциалов

Решение:

Строим математическую модель задачи. Через X_ij обозначаем объем продукции, доставленный от поставщика A_i(i=1, 2, 3) потребителю B_j(). Отметим, что в данном случае сумма количества продукции, которую могут отгрузить все поставщики, совпадает с суммой потребностей потребителей: 310+360+230=140+190+180+170+220=900.

Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:

(1)

(2)

(3)

Строим начальную распределительную таблицу:

Таблица 5

A_i B_j

B₁

B₂

B₃

B₄

B₅

a_i

U_i

A₁

-4

A₂

A₃

-6

b_j

V_j

Построенному опорному решению отвечают затраты:

Проверим полученный опорный план на оптимальность. Для этого i-ой строке j-ому столбцу ставим в соответствие числа U_i и V_j (потенциалы). Для каждой базисной переменной X_ij потенциалы должны удовлетворять условию U_i+V_j=c_ij. Получаем систему:

U₁+V₃=2

U₁+V₅=1

U₂+V₂=8

U₂+V₃=6

U₂+V₄=10

U₃+V₁=1

U₃+V₂=2.

Так как система состоит из 7 уравнений, а неизвестных 8, то, чтобы найти численное решение этой системы, одно из неизвестных зададим произвольно, тогда остальные переменные найдутся из системы однозначно.

Пусть U₂=0, тогда V₂=8, V₃=6, V₄=10, U₁=2, V₃=2, U₁=-4, U₃=2, V₂=2, U₃=-6, V₁=7, V₅=5.

Теперь для небазисных переменных (свободных клеток) найдем оценки S_ij=C_ij-(U_i+V_j):

S₁₁=5-(-4+7)=2

S₁₂=3-(-4+8)=-1

S₁₄=4-(-4+10)=-2

S₂₁=3-(0+7)=-4

S₂₅=5-(0+5)=0

S₃₃=3-(-6+6)=3

S₃₄=5-(-6+10)=1

S₃₅=4-(-6+5)=5

В силу критерия оптимальности опорного плана (все оценки S_ij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введем переменную X₂₁ (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки “+” и “-“, начиная с (2, 1), которой присваиваем знак “+”. Выбираем наименьшее значение из клеток со знаком “-“ (min(140, 100)=100) и перераспределим продукцию вдоль контура, прибавляя 100 к значениям в клетках со знаком “+” и вычитая из значений в клетках со знаком “-“. В результате приходим к таблице 6.

Таблица 6

A_i B_j

B₁

B₂

B₃

B₄

B₅

a_i

U_i

A₁

-4

A₂

A₃

-2

b_j

V_j

Полученному решению отвечают затраты: .

Проверяем полученный план на оптимальность и получаем, что S₃₄=-3<0.

Значит, решение не оптимальное и строим в таблице 6 новый цикл пересчета для клетки (3, 4). Так как min(170, 40)=40=X₃₁, то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком “+” и вычитая из значений в клетках со знаком “-“. В результате получаем таблицу 7.

Таблица 7

A_i B_j

B₁

B₂

B₃

B₄

B₅

a_i

U_i

A₁

-4

A₂

A₃

-5

b_j

V_j

Полученному решению отвечают затраты: .

Аналогично предыдущему, проверяем полученный план на оптимальность.

Получаем, что S₁₄=-2<0.

Теперь для улучшения плана загрузим клетку (1, 4). В итоге приходим к таблице 8.

Таблица 8

A_i B_j

B₁

B₂

B₃

B₄

B₅

a_i

U_i

A₁

-6

A₂

A₃

-5

b_j

V_j

Среди оценок свободных клеток имеем S₂₅=-2<0, следовательно, полученный план перевозок не является оптимальным и для его улучшения необходимо загрузить клетку (2, 5). В итоге вычислений приходим к таблице 9.

Таблица 9

A_i B_j

B₁

B₂

B₃

B₄

B₅

a_i

U_i

A₁

-4

A₂

A₃

-3

b_j

V_j

Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок 1-ый поставщик отправляет 130 ед. продукции потребителю B₄ и 180 ед. – B₅; 2-ой поставщик – 140 ед. потребителю B₁, 180 ед. потребителю B₃ и 40 ед. потребителю B₅; 3-ий поставщик – 190 ед. потребителю B₂ и 40 ед. потребителю B₄.

Критерий оценки домашней контрольной работы

1. ДКР подлежит зачету, если:

a. выполнены все задания без замечаний

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

2. ДКР будет не зачтена, если:

a. При ответах на теоретические вопросы допущены существенные ошибки или нет конкретного ответа.

Примечание:

· При отметке «не зачтено» - ДКР подлежит возврату, учащиеся дорабатывают её до сессии и получают допуск к экзамену.

· Если учащийся не успевает выполнить исправления до начала сессии, то во время сессии он получается новый вариант и выполняет его, после чего получает допуск к экзамену.

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

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

ПОКАЗАТЕЛИ ОЦЕНКИ ПОДГОТОВЛЕННОСТИ УЧАЩИХСЯ

Отметка в баллах	Показатели оценки
0 (ноль)	за отсутствие ответа или отказ от ответа;
(один)	за усвоение отдельных основных определений, понятий, фактов (модель, моделирование, базисные переменные, граф, сеть и т.д.) практическое задание выполнено не полностью, с многочисленными грубыми ошибками, не устраняемыми даже при дополнительных (наводящих) вопросах преподавателя;
(два)	за умение различить определения понятия при предъявлении в готовом виде (отличает базисные и искусственные переменные, отличает симплексную таблицу от транспортной, различает пару взаимно двойственных задач и т. д.), однако самостоятельно воспроизвести их не может; наличие нескольких грубых ошибок при ответе, устраняемых с помощью преподавателя. практическое задание выполнено не полностью, учащийся испытывает значительные затруднения в применении знаний и умений, наличие в работе нескольких грубых ошибок, устраняемых при дополнительных (наводящих) вопросах преподавателя;
(три)	за неполное или неосознанное воспроизведение или затруднения в изложении учебного материала по памяти (Этапы моделирования, построение начального опорного плана симплекс методом, признак оптимальности опорного плана, и т. д.), наличие одной - двух грубых ошибок, устраняемых при дополнительных (наводящих) вопросах преподавателя; учащийся механически, неосознанно осуществляет практические действия по образцу;
(четыре)	за неполное или недостаточно осознанное воспроизведение учебного материала или затруднения в его изложении (Транспортная задача, основные методы построения исходного опорного плана перевозок ТЗ, алгоритмы решения транспортной задачи и т. д.), наличие одной - двух существенных ошибок, устраняемых при дополнительных (наводящих) вопросах преподавателя; учащийся проявляет волевые усилия, интерес к учению, осмысленность действий; учащийся недостаточно осознанно воспроизводит большую часть учебного материала. Применяет знания в знакомой ситуации по образцу. Работа выполнена не полностью или с одной - двумя существенными ошибками, которые исправляет с помощью преподавателя;
(пять)	за осознанное воспроизведение большей части учебного материала (дает определения и основные понятия теории графов, дает определения дерева графа и алгоритм его построения и т. д.), с одной - двумя существенными ошибками, устраняемыми при дополнительных (наводящих) вопросах преподавателя; изложение материала последовательно, правильно, осмысленно, самостоятельно; учащийся заинтересован в учении и достижении результата; практическое задание выполнено с одной - двумя существенными ошибками, устраняемыми при дополнительных (наводящих) вопросах преподавателя;
(шесть)	за полное воспроизведение учебного материала (дает определения и основные понятия теории графов, дает определения остового дерева графа и алгоритмы его построения и т. д.), с несколькими несущественными ошибками, оперирование учебным материалом в типичной ситуации; учащийся излагает материал точно, системно, осмысленно, самостоятельно, дает ответ на любые вопросы по теме в рамках учебника и конспекта, умеет отобрать наиболее важные сведения из полученной информации, дает им сравнительную оценку, конкретизирует, обобщает материал; полное выполнение работы с несколькими несущественными ошибками, применение знаний и умений в типичной ситуации с незначительной помощью преподавателя;
(семь)	за полное, прочное владение учебным материалом (дает определения и основные понятия теории графов, дает определения остового дерева графа и алгоритмы его построения, дает определения алгоритмов нахождения кратчайших путей в графе, и т. д.), и оперирование им в типичной ситуации, наличие одной - двух несущественных ошибок при изложении материала; ответ структурируется в соответствии с собственной логической схемой учащегося, свободно используются наглядные средства для иллюстрации ответа; учащийся умеет обосновать и доказать сформулированные выводы; полное выполнение работы, наличие при выполнении работы одной - двух несущественных ошибок, самостоятельное применение знаний и умений в типичной ситуации;
(восемь)	за полное, прочное, глубокое, системное знание учебного материала (дает определения и основные понятия теории графов, дает определения остового дерева графа и алгоритмы его построения, дает определение и описание алгоритмов нахождения кратчайших путей в графе матричным и графическим способом и т. д.), оперирование им в знакомой ситуации; учащийся работает с дополнительной литературой, иногда допускает несущественные ошибки, которые сам и устраняет; имеет определенный опыт творческой деятельности, проявляет ответственность, добросовестность; Практическое задание выполнено безошибочно и в полном объеме. Самостоятельно применяет знания и умения в типичной ситуации;
(девять)	за свободное оперирование учебным материалом (дает определения и основные понятия теории графов, дает определения остового дерева графа и формулирует алгоритмы его построения, дает определение и описание алгоритмов нахождения кратчайших путей в графе матричным и графическим способом, формулирует общие принципы применения алгоритмов на графах для решения производственных задач и т. д.), умение отвечать на нестандартные вопросы, проявление познавательной активности, наличие одной - двух несущественных ошибок при изложении материала, самостоятельно исправляемых учащимся; учащийся выполняет задания творческого характера, импровизирует в процессе творческой работы, оперирует учебным материалом в частично измененной ситуации; учащийся полностью выполнил работу, свободно применяет знания и умения при выполнении заданий в частично измененной ситуации; наличие одной - двух несущественных ошибок при выполнении работы, самостоятельно исправляемых учащимся; проявляет высокий уровень самостоятельности, эрудиции;
(десять)	за свободное, безукоризненное оперирование учебным материалом (дает определения и основные понятия теории графов, дает определения остового дерева графа и формулирует алгоритмы его построения, дает определение и описание алгоритмов нахождения кратчайших путей в графах матричным и графическим способом, формулирует общие принципы применения алгоритмов на графах для решения производственных задач и т. д.), за умение отвечать на нестандартные вопросы, проявление познавательной активности, умение осознанно и оперативно использовать полученные знания для решения проблем в новых ситуациях; учащийся интерпретирует смысл событий, явлений, процессов на основе новейших достижений науки и техники, располагает в определенном порядке конкретные действия, проявляет целеустремленность, познавательную активность, творческое отношение к учебе, выполняет творческие работы и задания; практическое задание выполнено полностью и безукоризненно, не имеет замечаний преподавателя; оригинально, нестандартно применяет полученные знания и умения на практике в незнакомой ситуации.