Задание 1
Построить математическую модель следующей задачи о диете.
Доступны следующие продукты: пирожные, 30с. за шт., котлеты, 40с. за шт., кола, 80с. за бут., биг-маки, 70с. за шт.
В единице продукта содержится следующее количество приведенных ниже веществ.
|
|
калории |
сахар |
жир |
витамины |
|
пирожное |
300 |
5 |
4 |
0 |
|
котлета |
100 |
5 |
2 |
1 |
|
кола |
250 |
3 |
2 |
1 |
|
биг-мак |
200 |
3 |
7 |
0 |
Заданы ограничения на потребление веществ в день:
Сумма калорий 500 и Сумма витаминов Сумма сахара 10 и . Сумма жира 8 и .
Требуется определить набор из указанных продуктов на день минимальной стоимости при выполнении приведенных ограничений.
Задание 2
Найти множество Парето следующей двухкритериальной задачи.
при условии x{1, 2, 3,4, 5, 6, 7}.
Значения функций заданы таблицей.
|
x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
F1(x) |
½ |
1 |
3/2 |
1 |
3/2 |
2 |
3/2 |
|
F2(x) |
3 |
3 |
3 |
5/2 |
5/2 |
5/2 |
3/2 |
Задание 3
Геометрически решить задачу линейного программирования:
Задание 4
Перейти к двойственной и решить задачу линейного программирования:
Задание 5
Решить задачу линейного программирования симплекс-методом.
Задание 6
Решить транспортную задачу. Транспортная таблица имеет вид:
|
Ai / Bj |
B1 |
B2 |
B3 |
Запасы ai |
|
A1 |
3 |
2 |
4 |
100 |
|
A2 |
9 |
0 |
1 |
150 |
|
A3 |
2 |
7 |
5 |
80 |
|
Заявки bj |
80 |
140 |
110 |
|
Задание 7
Найти эйлеров цикл в графе. Вершина 5 отсутствует.
Задание 8
Найти кратчайшие пути из вершины 1 во все остальные вершины графа. Граф приведен в задаче 7. Дуги и их веса заданы в таблице.
Вес дуги (2,8) равен сумме дуг (2,5) и (5,8), а вес дуги (3,7) равен сумме весов дуг (3,5) и (5,7).
|
Дуги |
1,2 |
1,3 |
2,4 |
2,7 |
2,5 |
3,5 |
3,8 |
|
Веса |
3 |
1 |
4 |
2 |
5 |
3 |
2 |
|
Дуги |
3,6 |
4,7 |
5,7 |
5,8 |
6,8 |
7,9 |
8,9 |
|
Веса |
4 |
5 |
1 |
3 |
2 |
4 |
2 |
Задание 9
Решить задачу коммивояжера для 5 городов. Матрица расстояний (стоимостей переезда) представлена в виде.
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
5 |
2 |
1 |
|
|
2 |
4 |
6 |
5 |
1 |
|
|
3 |
2 |
4 |
3 |
6 |
|
|
4 |
1 |
1 |
5 |
4 |
|
|
5 |
4 |
3 |
4 |
5 |
Задание 10
Найти длину критического пути (длительность выполнения проекта) в сети, где дуги представляют собой работы проекта, начало и конец дуги - начало и конец работы, вес дуги - длительность работы.
Вычислить наиболее ранние и наиболее поздние моменты начала работ. Вершины s и t сопоставлены началу и завершению проекта соответственно.
Длительности выполнения работ (веса дуг) (2,7), (3,8), (8,5) равны 1, дуги (5,7) равна целой части от деления номера набора задач (N) на 15 (=), остальные равны 2.
Задание 11
Решить антагонистическую матричную игру.
Выигрыш от проведения операции в зависимости от условий задан следующей матрицей.
|
Ai \ Πj |
1 |
2 |
3 |
4 |
5 |
|
1 |
3 |
8 |
10 |
5 |
11 |
|
2 |
2 |
1 |
5 |
9 |
0 |
Задание 12
Найти оптимальные смешанные стратегии и цену игры в антагонистической матричной игре 2 х n.
|
Игрок 1 \ Игрок 2 |
1 |
2 |
3 |
|
1 |
0 |
3 |
5 |
|
2 |
6 |
18/4 |
3 |
Задание 13
В эксперименте 10 человек независимо друг от друга будут случайным образом выбирать одну из двух гирь - 1 кг или 2 кг. С помощью метода Монте-Карло определить предполагаемое значение суммарного выбранного веса. Использовать механизм случайного выбора типа "орел-решка". Число испытаний N = 15. Описать процесс получения решения.
Задание 14
Решить с помощью динамического программирования:
при ограничениях
Задание 15
Построить расписание обслуживания n=5 требований одним прибором, минимизирующее
Длительности обслуживания и веса заданы в таблице.
|
j |
1 |
2 |
3 |
4 |
5 |
|
4 |
2 |
3 |
5 |
7 |
|
|
2 |
6 |
4 |
3 |
9 |
Ход решения
Перед применением симплекс-метода необходимо преобразовать систему линейных ограничений и рассматриваемую нами функцию к каноническому виду.
Все свободные члены системы ограничений неотрицательны, значит, выполнено одно из необходимых условий применения симплекс-метода.
Осталось все условия системы представить в виде уравнений.
Для этого к левой части 1-го неравенства системы ограничений прибавляем неотрицательную переменную , к левой части 2-го неравенства прибавляем неотрицательную переменную , а к левой части 3-го - неотрицательную переменную , тем самым мы преобразуем
неравенства в равенства:
Определимся с начальным опорным решением. Наличие единичного базиса в системе ограничений позволяет легко найти его.
Переменные х3, и являются базисными. Остальные переменные являются свободными. Приравняв свободные переменные к 0 в системе ограничений, получаем опорное решение: = (0 , 0 , 2 , 1 , 3).
Теперь непосредственно составим таблицу 5.1...
Список использованной литературы:
Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. Вентцель Е.С. Исследование операций. - М: Сов. радио, 1972. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа, 1975 Костевич Л.С. Математическое программирование. - Мн.: ООО «Новое знание», 2003. Кузнецов А.В., Холод Н.И. Математическое программирование. - Мн.: Выш. школа, 1982. Сборник задач и упражнений по высшей математике. Математическое программирование / Под ред. А.В.Кузнецова - Мн.: Выш. школа, 1995.
