Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Задание 1.
Задача 1.1. На кондитерской фабрике.
Маленькая кондитерская фабрика должна закрыться на реконструкцию, поэтому надо реализовывать оставшиеся запасы сырья, получив максимальную прибыль. Запасы и расход сырья для производства единицы продукции каждого вида, а также получаемая при этом прибыль представлены в таблице.
Ресурсы |
Кондитерские изделия |
Ограничения |
||||
Ореховый звон |
Райский вкус |
Батончик |
Белка |
Ромашка |
||
Темный шоколад |
0,8 |
0,5 |
1 |
2 |
1,1 |
1411 |
Светлый шоколад |
0,2 |
0,1 |
0,1 |
0,1 |
0,2 |
149 |
Сахар |
0,3 |
0,4 |
0,6 |
1,3 |
0,05 |
815,5 |
Карамель |
0,2 |
0,3 |
0,3 |
0,7 |
0,5 |
466 |
Орехи |
0,7 |
0,1 |
0,9 |
1,5 |
0 |
1080 |
Прибыль |
1 |
0,7 |
1,1 |
2 |
0,6 |
Требуется:
Обозначим через x1, x2, x3, x4, x5 количество производства кондитерских изделий.
Целевая функция это выражение, которое необходимо максимизировать:
f(x) = x1 + 0,7x2 + 1,1x3 + 2x4 + 0,6x5 → max
Ограничения задачи имеет вид:
0,8x1 + 0,5x2 + x3 + 2x4 + 1,1x5 1411
0,2x1 + 0,1x2 + 0,1x3 + 0,1x4 + 0,2x5 149
0,3x1 + 0,4x2 + 0,6x3 + 1,3x4 + 0,05x5 815,5
0,2x1 + 0,3x2 + 0,3x3 + 0,7x4 + 0,5x5 466
0,7x1 + 0,1x2 + 0,9x3 + 1,5x4 1080
x1, x2, x3, x4, x5 ≥ 0
Решение задачи выполним с помощью надстройки Excel Поиск решения.
Оптимальные значения вектора X = (X1, X2, X3, X4, X5), будут помещены в ячейках B3:F3, а оптимальное значение целевой функции в ячейке G4.
Введем исходные данные. Сначала опишем целевую функцию с помощью функции СУММАПРОИЗВ, а потом введем данные для левых частей ограничений.
Исходный рабочий лист Excel.
В Поиске решения введем направление целевой функции, адреса искомых переменных, добавим ограничения. Надо учитывать, что пакетиков может быть только целое количество, т.е. x1, x2, x3, x4, x5 могут принимать только целые значения. На экране появится диалоговое окно Поиска решения с введенными условиями.
Диалоговое окно Поиск решения.
В Параметрах поиска решения установим флажки в окнах Линейная модель и Неотрицательные значения.
Диалоговое окно Параметры поиска решения.
После ввода параметров для решения следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено.
Диалоговое окно Результаты поиска решения.
Полученное решение означает, что максимальный доход 1509 у.е. фабрика может получить при выпуске 450 пакетиков орехового звона, 60 пакетиков райского вкуса, 10 батончиков, 500 пакетиков белки и 10 пакетиков ромашки. При этом ресурсы будут полностью использованы. Прибыль составит 1509 у.е.
Задание 2.
Задача 2.1. Задача коммивояжера.
Коммивояжеру, находящему в Париже, необходимо посетить три города. Он получил информацию о стоимости перелета в каждый из выбранных городов из Парижа и стоимости перелета из одного города в другой. На основании полученных данных он составил матрицу стоимостей (см. таблицу) перелета в выбранные города и обратно. И теперь ему надо так составить маршрут поездки, чтобы затраты на дорогу были минимальными и чтобы каждый пункт посещался только один раз.
Пункты |
Париж |
Берлин |
Рим |
Лондон |
Париж |
0 |
270 |
430 |
160 |
Берлин |
70 |
0 |
160 |
10 |
Рим |
200 |
130 |
0 |
350 |
Лондон |
210 |
160 |
250 |
0 |
Исходные параметры задачи коммивояжера:
n количество вылетов;
m количество прилетов;
ai количество вылетов из данного города;
bj количество прилетов в данный город; cij стоимость проезда.
Искомые величины:
xij факт перелета из города Ai в город Bi:
0, если из города Ai не перелетали в город Bi,
xij = 1, если из города Ai перелетали в город Bi.
f(X) общая стоимость поездок.
n m
f(X) = ∑ ∑ cij ∙ xij → min,
i=1 j=1
n
∑ xij = 1, i = 1, …, n,
j=1
n
∑ xij = 1, j = 1, …, m,
i=1
0
xij = 1, i = 1, …, n, j = 1, …, m.
Решение задачи выполним с помощью надстройки Excel Поиск решения.
Оптимальные значения вектора xij, будут помещены в ячейках B3:E6, а оптимальное значение целевой функции в ячейке B16.
Введем исходные данные. Для того, чтобы компьютер не рассматривал перелет из какого-либо города в этот же город, введем в эти ячейки стоимость билетов гораздо выше основных. Сначала опишем целевую функцию с помощью функции СУММАПРОИЗВ, а потом введем данные для левых частей ограничений.
Исходный рабочий лист Excel.
В Поиске решения введем направление целевой функции, адреса искомых переменных, добавим ограничения. Надо учитывать, что переменные xij являются булевыми, т.е. могут принимать только значения 1 или 0. На экране появится диалоговое окно Поиска решения с введенными условиями.
Диалоговое окно Поиск решения.
В Параметрах поиска решения установим флажки в окнах Линейная модель и Неотрицательные значения.
Диалоговое окно Параметры поиска решения.
После ввода параметров для решения следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено.
Диалоговое окно Результаты поиска решения.
Полученное решение означает, что минимальные затраты будут на маршруте: Париж → Лондон → Рим → Берлин → Париж. Затраты на поездку составят 610.
PAGE 1