Xreferat.com » Рефераты по информатике и программированию » Решение задач линейного программирования

Решение задач линейного программирования

COLSPAN=4>Себестоимость выполнения единицы работы механизма ,гр. Количество единиц ai механизмов
B1 B2 B3 B4
A1 11 4 3 1 15 A2 6 8 9 7 10 A3 4 8 4 2 35 Потребности bj участков в механизмах 25 20 10 5

Исходные массивы для решения транспортной задачи по программе TRAN2


Решение задач линейного программирования


Распечатка с ЭВМ с результатом решения


Решение задач линейного программирования


Оптимальный план транспортной задачи


x12=15; x­21=5; x22=5; x31=20;x33=10; x­34=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.


Анализ результатов и выводы

Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.

Задание 6


Решение многоэтапных задач методом динамического программирования


Цель задания: приобрести практические навыки решения многоэтапных задач методом динамического программирования.

Индивидуальное задание.

В таблице 11 приведены значения gi(x) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x.

Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f4(100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр.

Таблица 11


Предприятие Прирост выпуска продукции, тыс. гр. Средства c, тыс. гр. Номер варианта


20 40 60 80 100
1 G1(x) 11 21 40 54 62 6
2 G2(x) 13 20 42 45 61
3 G3(x) 12 22 34 55 60
4 G4(x) 10 27 33 57 69

Функциональное уравнение Беллмана для рассматриваемой задачи

f1(x)=max[g1(x)]=g1(x) – для первого предприятия;

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

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

Таблица 12


Средства с, тыс. гр. Предприятие

1 2 3 4

G1(x) G2(x) G3(x) G4(x)
20 11 13 12 10
40 21 20 22 27
60 40 42 34 33
80 54 45 55 57
100 62 62 60 69

Таблица 13


X1*(c) 20 40 60 80 100
F1(c) 11 21 40 54 62

Таблица 14


x

С

0 20 40 60 80 100 F2(c) X2*(c)
20 0+13 12+0



13 0
40 0+24 12+13 22+0


25 20
60 0+42 12+24 22+13 34+0

42 0
80 0+45 12+42 22+24 34+13 55+0
55 80
100 0+67 12+45 22+42 34+24 55+3 60+0 68 80

Таблица 15


x

С

0 20 40 60 80 100 F3(c) X3*(c)
20 0+13 10+0



13 0
40 0+29 10+13 27+0


27 40
60 0+42 10+25 27+13 33+0

42 0
80 0+55 10+42 27+25 33+13 57+0
57 80
100 0+68 10+55 27+42 33+25 52+13 69+0 69 40

Таблица 16


С X1*(c) F1(c) X2*(c) F2(c) X3*(c) F3(c) X4*(c) F4(c)
0 0 0 0 0 0 0 0 0
20 20 11 20 13 0 13 0 13
40 40 21 20 24 20 25 40 27
60 60 40 60 42 0 42 0 42
80 80 54 80 45 80 55 80 57
100 100 62 20 67 80 68 40 69

Итак, из таблицы 16 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. При этом четвертому предприятию нужно выделить 40 тыс. грн., а остальным 60 тыс. грн.

Оптимальное распределение оставшихся 60 тыс. грн. между 3-мя предприятиями обеспечит прирост продукции на сумму 42 тыс. грн., при условии, что 3-му предприятию не будут выделены средства. Остается 60 тыс. грн., которые надо распределить между 2-мя предприятиями. Выделив всю оставшуюся сумму (60 тыс. грн.) второму, прибыль составит 42 тыс. грн. первому предприятию средств не остается.

Максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. и будет получен, если первому предприятию не выделять средств, второму — 60 тыс. грн., третьему не выделять, а четвертому — 40 тыс. грн.

Это решение можно записать в виде:

X*=(0,0,60,40); f*=f4(100)=69 тыс. гр.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: