Автор работы: Пользователь скрыл имя, 02 Апреля 2013 в 20:05, контрольная работа
Задание 3 Совет директоров изучает предложения по модернизации 5-ти предприятий. Для этих целей выделено 7,2 миллионов долларов. Рассчитать оптимальное распределение средств в объеме 7,2 миллионов долларов между 5-ю предприятиями, при котором суммарная прибыль будет максимальной, если средства Х, выделенные каждому предприятию, приносят прибыль fk(x) (табл.1). Вложенные средства кратны 1,2 и не превышают 6 миллионов долларов для каждого предприятия. Как изменится данное решение, если начальные средства уменьшатся на 1,2 миллиона долларов.
Задание 1 - 3
Список литературы
Поставщик |
Потребитель |
Запас | ||||||||||||||
B 1 |
B 2 |
B 3 | ||||||||||||||
A 1 |
|
|
|
30 | ||||||||||||
A 2 |
|
|
|
40 | ||||||||||||
A 3 |
|
|
|
20 | ||||||||||||
A 4 |
|
|
|
20 | ||||||||||||
Потребность |
40 |
40 |
30 |
|||||||||||||
Находим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1,2),(1,1),(2,1),(2,2) (цикл показан пунктирной линией). Вычисляем оценку Δ12 =(5+6)-(5+4) = 1, так Δ12 > 0, переходим к следующей свободной клетке (2, 3). По такому же принципу строим циклы для остальных свободных клеток. Для клетки (2,3) цикл: (2,3),(1,3),(1,1),(2,1). Оценка Δ23 =(6+5)-(4+6) = 1 > 0, переходим к клетке (3,1). Для нее цикл: (3,1), (1,1),(1,3),(3,3). Оценка Δ31 = (4+4)-(5+3) = 0, переходим к клетке (3,2) . Для нее цикл (3,2), (3,3), (1,3), (1,1), (2,1), (2,2). Оценка Δ32 = (4+4+6)-(3+5+4) = 2 > 0, переходим к клетке (4,2). Для нее цикл: (4,2), (2,2), (2,1), (4,1). Оценка Δ42 = (0+6)-(4+0)=2 > 0, переходим к клетке (4,3). Для нее цикл: (4,3), ((1,3), (1,1), (4,1). Оценка Δ43 = (0+5) – (4+0) = 1> 0 Все оценки свободных клеток положительны, следовательно, полученный опорный план является оптимальным.
Таким образом, от первого поставщика продукция поступает первому потребителю в количестве 20 ед. и третьему потребителю в количестве 10 ед. Продукция первого поставщика вывезена полностью.
От второго поставщика продукция поступает второму потребителю в количестве 40 ед. Продукция второго поставщика вывезена полностью и потребность второго потребителя полностью удовлетворена.
Продукция третьего поставщика поступает третьему потребителю в количестве 20 ед. Продукция третьего поставщика вывезена полностью, потребность третьего поставщика удовлетворена полностью. А потребность первого потребителя остается неудовлетворенной на 20 единиц.
Совет директоров изучает предложения по модернизации 5-ти предприятий. Для этих целей выделено 7,2 миллионов долларов. Рассчитать оптимальное распределение средств в объеме 7,2 миллионов долларов между 5-ю предприятиями, при котором суммарная прибыль будет максимальной, если средства Х, выделенные каждому предприятию, приносят прибыль fk(x) (табл.1). Вложенные средства кратны 1,2 и не превышают 6 миллионов долларов для каждого предприятия. Как изменится данное решение, если начальные средства уменьшатся на 1,2 миллиона долларов.
Таблица 1 – Исходные данные по прибыли
Х |
f1(x) |
f2(x) |
f3(x) |
f4(x) |
f5(x) |
1,2 |
3 |
2 |
3 |
4 |
2 |
2,4 |
4 |
4 |
5 |
5 |
5 |
3,6 |
7 |
8 |
7 |
8 |
7 |
4,8 |
9 |
10 |
9 |
11 |
10 |
S0 = 7,2 млн.долл. (начальное состояние системы)
хk – средства, выделенные к-му предприятию (управление на к-ом шаге);
Sк – количество денежных средств, которые необходимо распределить между оставшимися к предприятиями (состояние системы после к-го шага);
n = 5 (число этапов или шагов);
- оптимальная прибыль,
Математическая модель задачи:
1) ограничения на выделяемы средства
,
2) уравнения состояния
Sk = Sk-1 – xk , 0 ≤ Sk-1 ≤ 7,2
3) целевая функция
Z =
Уравнения Беллмана
к = 5, 5 этап
к = 4, 4 этап
к = 3, 3 этап
к = 2, 2 этап
к = 1, 1 этап
Заполним таблицу.
Этап5. к = 5
В столбце S3 и строке х4 указаны все возможные значения. Все оставшиеся перед 5-м шагом средства нужно выделить 5-му предприятию. Поэтому числа из столбца f5(x) исходной таблицы запишем в нашу таблицу в столбцы со 2-го по 5-й. В столбцах со 2-го по 5-й определяем максимум в каждой строке, и результат пишем в 6-й столбец. Те x5, которым соответствуют числа из 6-го столбца, пишем в 7-й столбец.
2 |
3 |
4 |
5 |
6 |
7 | |
х5 S4 |
1,2 |
2,4 |
3,6 |
4,8 |
||
|
1,2 |
2 |
2 |
1,2 | |||
2,4 |
5 |
5 |
2,4 | |||
3,6 |
7 |
7 |
3,6 | |||
4,8 |
10 |
10 |
4,8 |
Этап 4. к=4
Определим оптимальную стратегию при распределении средств между 4-м и 5-м предприятиями. По первоначальной таблице и таблице при k = 5 заполним следующую таблицу.
В 1-м столбце указано, сколько средств осталось для 4-го и 5-го предприятий. В строке х4 дана информация о том, сколько из этих оставшихся средств досталось 4-му предприятию. Поясним, как заполняются столбцы со 2-го по 5-й. В клетке (2, 2) (2-я строка, 2-й столбец) на долю 4-го и 5-го предприятий приходится S4 = 1,2, из них на долю 4-го предприятия приходится х4 = 1,2. Поэтому нужно сложить значения из исходной таблицы для f4(x) при х=1,2 (это 4) и из предпоследнего столбца предыдущей таблицы при S4 = S3 – х4 = 1,2 – 1,2 = 0 (это 0 – если средств не выделяется, предприятие прибыли не приносит), то есть 4 + 0 = 4.
В клетке (3, 2) (3-я строка, 2-й столбец) на долю 4-го и 5-го предприятий приходится S3 = 2,4, из них на долю 4-го предприятия приходится х4 = 1,2. Поэтому нужно сложить значения из исходной таблицы для f4(x) при х4 = 1,2 (это 4) и из предпоследнего столбца предыдущей таблицы при S4 = S3 – х4 = 2,4 – 1,2 = 1,2 (это 2), то есть 4+ 2 = 6.
В клетке (6, 3) (6-я строка, 3-й столбец) на долю 4-го и 5-го предприятий приходится S3 = 6, из них на долю 4-го предприятия приходится х4 = 2,4. Поэтому нужно сложить значения из исходной таблицы для f4(x) при х4 = 2,4 (это 5) и из предпоследнего столбца предыдущей таблицы при S4 = S3 – х4 = 6 – 2,4 = 3,6 (это 7), то есть 5 + 7 = 12. И т. д.
2 |
3 |
4 |
5 |
6 |
7 | ||
1 |
х4 S3 |
1,2 |
2,4 |
3,6 |
4,8 |
||
|
2 |
1,2 |
4+0=4 |
4 |
1,2 | |||
3 |
2,4 |
4+2=6 |
5+0=5 |
6 |
1,2 | ||
4 |
3,6 |
4+5=9 |
5+2=7 |
8+0=8 |
9 |
1,2 | |
5 |
4,8 |
4+7=11 |
5+5=10 |
8+2=10 |
11+0=11 |
11 |
1,2 или 4,8 |
6 |
6 |
4+10=14 |
5+7=12 |
8+5=13 |
11+2=13 |
14 |
1,2 |
7 |
7,2 |
5+10=15 |
8+7=15 |
11+5=16 |
16 |
4,8 |
Этап 3. к=3
Определим оптимальную стратегию при распределении средств между 3-м, 4-м и 5-м предприятиями. По первоначальной таблице и таблице при k = 4 заполним следующую таблицу.
В 1-м столбце указано, сколько средств осталось для 3-го, 4-го и 5-го предприятий. В строке х3 дана информация о том, сколько из этих оставшихся средств досталось 3-му предприятию. Поясним, как заполняются столбцы со 2-го по 5-й. В клетке (2, 2) (2-я строка, 2-й столбец) на долю 3-го, 4-го и 5-го предприятий приходится S2 = 1,2, из них на долю 3-го предприятия приходится х2 = 1,2. Поэтому нужно сложить значения из исходной таблицы для f3(x) при х3=1,2 (это 3) и из предпоследнего столбца предыдущей таблицы при S3 = S2 – х3 = 1,2 – 1,2 = 0 (это 0 – если средств не выделяется, предприятия прибыли не приносят), то есть 3 + 0 = 3.
В клетке (3, 2) (3-я строка, 2-й столбец) на долю 3-го, 4-го и 5-го предприятий приходится S2 = 2,4, из них на долю 3-го предприятия приходится х3 = 1,2 Поэтому нужно сложить значения из исходной таблицы для f3(x) при х3 = 1,2 (это 3) и из предпоследнего столбца предыдущей таблицы при S3 = S2 – х3 = 2,4 – 1,2 = 1,2 (это 4), то есть 3+ 4 = 7. И.т.д.
2 |
3 |
4 |
5 |
6 |
7 | ||
1 |
х3 S2 |
1,2 |
2,4 |
3,6 |
4,8 |
||
|
2 |
1,2 |
3+0=3 |
3 |
1,2 | |||
3 |
2,4 |
3+4=7 |
5+0=5 |
7 |
1,2 | ||
4 |
3,6 |
3+6=9 |
5+4=9 |
7+0=7 |
9 |
1,2 или 2,4 | |
5 |
4,8 |
3+9=12 |
5+6=11 |
7+4=11 |
9+0=9 |
12 |
1,2 |
6 |
6 |
3+11=14 |
5+9=14 |
7+6=13 |
9+4=13 |
14 |
1,2 или 2,4 |
7 |
7,2 |
3+14=17 |
5+11=16 |
7+9=16 |
9+6=15 |
17 |
1,2 |