Курсовая работа: Решение задач линейного программирования транспортной задачей
а11, а12,…,аnk - стоимость перевозки из пункта Аi в пункт Вj.
А1=100; А2=200; А3=150; В1=80; В2=90; В3=120; В4=160.
Распределить продукцию так со склада, чтобы затраты были минимальные.
Построим начальную таблицу для заполнения ячеек:
Таблица 1
Начальная таблица для заполнения ячеек
| 4 | 7 | 7 | 1 | 100 | |||||
| 80 | 20 | ||||||||
| 12 | 3 | 8 | 8 | 200 | |||||
| 70 | 120 | 10 | |||||||
| 8 | 10 | 16 | 5 | 150 | |||||
| 150 | |||||||||
| 80 | 90 | 120 | 160 | ||||||
Прежде чем начать заполнение ячеек, необходимо проверить условие:
Сумма запаса и сумма потребления были равны:
100+200+150=80+90+120+160; 450=450.
Принцип заполнения ячеек состоит в том, чтобы в выбранную ячейку заносилось минимальное число из стоящих напротив ячеек с параметрами, например: для заполнения ячейки 1-А берутся значения 80 и 100: min= (80;100). Затем меньшее число вычитается из обеих ячеек-значений.
После заполнения необходимо найти целевую функцию:
Z=80*4+20*7+70*3+120*8+10*8+150*5=3180
Получение начального опорного плана
- метод северо-западного угла
- метод наименьшей стоимости
I. Метод наименьшей стоимости:
· Определим ячейку с наименьшей стоимостью;
· Распределим как можно больше единиц в эту ячейку и вычеркнем строку или столбец, который исчерпан;
· Найдем ячейку с наименьшей стоимостью из оставшихся;
· Повторим пункт 2 и 3 пока все единицы не будут распределены.
Таблица 2
Определение ячеек методом наименьшей стоимости.
| 4 | 7 | 7 | 1 | 100 | ||||
| 100 | ||||||||
| 12 | 3 | 8 | 8 | 200 | ||||
| 90 | 110 | |||||||
| 8 | 10 | 16 | 5 | 150 | ||||
| 80 | 10 | 60 | ||||||
| 80 | 90 | 120 | 160 | |||||
Находим целевую функцию:
100*1+90*3+110*8+80*8+10*16+60*5=2350
Получили начальное решение.
II. Проверка решения на оптимальность:
- метод по камням
- метод Modi.
Проверка на оптимальность заключается в оценке пустых ячеек, используя так называемый цикл.