|
p align="left"> 6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000 7 0.000 30.000 0.200 0.100 0.200 0.250 0.300 8 0.000 400.000 3.000 4.000 5.000 4.000 2.000 9 0.000 800.000 6.000 5.000 4.000 6.000 4.000 0.000 300.000 260.000 320.000 400.000 450.000 КОД ОШИБКИ=0 ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 0.0000 ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА Бx Cб Po 1 2 3 4 5 6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000 7 0.000 30.000 0.200 0.100 0.200 0.250 0.300 8 0.000 400.000 3.000 4.000 5.000 4.000 2.000 9 0.000 800.000 6.000 5.000 4.000 6.000 4.000 0.000 -300.000 -260.000 -320.000 -400.000 -450.000 В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА Бx Cб Po 1 2 3 4 7 6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667 5 450.000 100.000 0.667 0.333 0.667 0.833 3.333 8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667 9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333 45000.000 -0.000 -110.000 -20.000 -25.000 1500.000 В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА Бx Cб Po 1 3 4 6 7 2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235 5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412 8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118 9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471 46941.176 45.294 5.882 2.500 9.706 1144.118 КОД ОШИБКИ=0 ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ X2=17.6471 X5=94.1176 ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765 РЕШЕНИЕ НАЙДЕНО !!! Оптимальный план. Экономическая интерпретация оптимального решения. В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен. Задание 4 Моделирование транспортных задач и их решение методом потенциалов Цель задания: приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов. Индивидуальное задание Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6. Таблица 6. 06 вариант транспортной задачи |
Вид механизма | Себестоимость выполнения единицы работы механизма ,гр. | Количество единиц 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 | | | |
Математическая формулировка транспортной задачи Пусть xij - количество единиц работы, выполненной механизмом вида ai, на участке работы bj.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы: при ограничениях: 1) ; - все механизмы должны быть задействованы; 2); - все участки должны быть загружены; 3) ; - количество единиц работы не может быть отрицательным Условие разрешимости задачи выполняется: 25+20+10+5=15+10+35; 60=60. Исходный опорный план, составленный по методу северо-западного угла Таблица 7 |
I | | ai | | | B1 | B2 | B3 | B4 | | | A1 | 11 | 4 15 | 3 | 1 | 15 | | A2 | 6 5 | 8 5 | 9 | 7 | 10 | | A3 | 4 20 | 8 | 4 10 | 2 5 | 35 | | bj | 25 | 20 | 10 | 5 | | | |
Решение транспортной задачи методом потенциалов Итак, видно что в число занятых клеток следует ввести клетку (2,1). Получим новый улучшенный план - таблица 8. Таблица 8 |
I | | ai | | | B1 | B2 | B3 | B4 | | | A1 | 11 | 4 15 | 3 | 1 | 15 | | A2 | 6 5 | 8 5 | 9 | 7 | 10 | | A3 | 4 20 | 8 | 4 10 | 5 5 | 35 | | bj | 25 | 20 | 10 | 5 | | | |
Введём в число занятых клетку (1,4) . Получим новый улучшенный план - Таблица 9. Таблица 9 |
I | | ai | | | B1 | B2 | B3 | B4 | | | A1 | 11 | 4 10 | 3 5 | 1 | 15 | | A2 | 6 | 8 10 | 9 | 7 | 10 | | A3 | 4 25 | 8 | 4 5 | 2 5 | 35 | | bj | 25 | 20 | 10 | 5 | | | |
Так как, - то данный план является оптимальным и значение себестоимости по данному плану. x12=15; x-21=5; x22=5; x-31=20;x33=10; x-34=5. Z=15*4+5*6+5*8+20*4+10*4+5*2=260. Анализ оптимального плана Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы. Задание 5 Решение транспортной задачи на ЭВМ Цель задания: приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2. Индивидуальное задание: Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6. Таблица 10. 06 вариант транспортной задачи |
Вид механизма | Себестоимость выполнения единицы работы механизма ,гр. | Количество единиц 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 тыс. гр.
Страницы: 1, 2
| 
