Контрольная работа: Решение задач линейного программирования различными методами
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 6. 06 вариант транспортной задачи
| Вид механизма | Себестоимость выполнения единицы работы механизма ,гр. | Количество единиц ai механизмов | |||
| B 1 | B 2 | B 3 | B 4 | ||
| A 1 | 11 | 4 | 3 | 1 | 15 |
| A 2 | 6 | 8 | 9 | 7 | 10 |
| A 3 | 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 | 3 5 |
| bj | 25 | 20 | 1 0 | 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 | 3 5 |
| bj | 25 | 20 | 1 0 | 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 | 3 5 |
| bj | 25 | 20 | 1 0 | 5 |
Так как, 
- то данный план является оптимальным и значение себестоимости по данному плану.
x 12 =15; x 21 =5; x 22 =5; x 31 =20; x 33 =10; x 34 =5.
Z =15*4+5*6+5*8+20*4+10*4+5*2=260.
Анализ оптимального плана
Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы.
Задание 5
Решение транспортной задачи на ЭВМ