Пример решения контрольной работы
Задача 1
Составить математическую модель и решить задачу графическим методом с последующим вычислением точных значений.
В производстве пользующихся спросом двух изделий принимают участие 3 цеха фирмы. На изготовление первого изделия 1-й цех затрачивает С1 часов, 2-й цех — С2 часов, 3-й цех — С3 часов. На изготовление одного второго изделия 1-й цех затрачивает D1 ч, 2-й цех — D2 ч, 3-й цех — D3 ч. На производство обоих изделий 1-й цех может затратить не более А1 ч, 2-й цех — не более А2 ч, 3-й цех — не более А3 ч.
От реализации первого изделия фирма получает доход Z1 р., а второго изделия - Z2 р.
Определить максимальный доход от реализации всех изделий. Значения коэффициентов условия задачи представлены в таблице.
С1 |
С2 |
С3 |
D1 |
D2 |
D3 |
A1 |
A2 |
A3 |
Z1 |
Z2 |
4 |
1 |
1 |
1 |
1 |
4 |
600 |
210 |
600 |
4 |
7 |
Решение
Предположим, что х – это количество первых изделий, а у – вторых.
Тогда целевая функция имеет вид:
L = Z1*x + Z2*y = 4*x + 7*y = Lmax
Ограничения выявляем по каждому цеху в отдельности:
1 цех С1*x+D1*y ≤ A1
2 цех С2*x+D2*y ≤ A2
3 цех С3*x+D3*y ≤ A3
Или:
4*x+1*y ≤ 600
1*x+1*y ≤ 210
1*x+4*y ≤ 600
Графически находим область допустимых значений:
(она выделена штриховкой на графике).
Находим вектор градиента и строим его на плоскости
Находим координаты точки экстремума и значение целевой функции в ней по правилу:
опптимальное решение (если оно существует) всегда достигается в одной из вершин области допустимых значений.
Наиболее отдаленной в направлении вектора градиента является точка А, для которой правомочна система уравнений:
1*x+1*y = 210
1*x+4*y = 600
Решение этой системы вычитанием первого уравнения из второго приводит к результату:
у = 130 х = 80
Целевая функция равна:
L = 4*x + 7*y = 4*80 + 7*130 = 1230.
Ответ: 1230.
Задача 2 по теме "Сетевые модели"
Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 14. На рис. 1 показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами. Определить маршрут доставки груза, которому соответствуют наименьшие затраты.
Рис.1
Задача 3
Решение
А1-2 = 16
А1-3 = 15
А1-4 = 17
А1-5 = А1-2 + d25 = 16+17 = 33
A1-6 = min(A1-2+d26; A1-3+d36; А1-5 + d56) = min(16+15; 15+16; 33+16) = 31
A1-7=min(A1-3+d37; A1-4+d47)= min(15+14; 17+19)=29
A1-8 = min(A1-4+d48; A1-7+d78) = min(17+18; 29+10) = 35
A1-9 = min(A1-5+d59; A1-6+d69) = min(33+17; 31+16) = 47
A1-10 = min(A1-6+d6 10; A1-7+d7 10) = min(31+20; 29+12) = 41
A1-11 = min(A1-7+d7 11; A1-8+d8 11) = min(29+11; 35+9) = 40
A1-12 = min(A1-9+d9 12; A1-10+d10 12) = min(47+13; 41+14) = 55
A1-13 = min(A1-10+d10 13; A1-11+d11 13) = min(41+20; 40+20) = 60
A1-14 = min(A1-12+d12 14; A1-10+d10 14; А1-13 + d13 14) = min(55+18; 41+19; 60+19) = 60
Жирным выделен маршрут:
1-3-7-10-14