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

Содержание
Введение
1. Исходные данные к задаче о выпуске продукции
2. Описание объекта
3. Теоретическая часть
3.1. Симплекс-метод
3.2. Транспортная задача
4. Практическая часть
4.1. Оптимальный план производства продукции
4.2. Транспортная задача
Заключение
Список литературы

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

1500
1
x6
12,0
4
8,00
1
x7
12,0
5
0,00
7
1
x8
3825,0
1467
1275,00
1083
1
ИС
-1141560
-1504300,00
-1761700
Шаг 1
 
 
 
 
 
 
 
 
 
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x4
7,180
2,560
4,853
1
-0,00260
x3
1,133
0,036
0,038
1
0,00067
x6
12,000
4,000
8,000
0,00000
1
x7
4,067
4,748
-0,264
-0,00467
1
x8
2597,600
1428,012
1234,135
-0,72200
1
ИС
1996661,333
-1078136,640
-1437822,923
1174,50667
 
 
 
 
Шаг 2
 
 
 
 
 
 
 
 
 
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x2
1,4795
0,5274
1
0,2061
-0,0005
x3
1,0775
0,0161
1
-0,0078
0,0007
x6
0,1636
-0,2195
-1,6485
0,0043
1
x7
4,4575
4,8873
0,0544
-0,0048
1
x8
771,6408
777,0753
-254,3119
-0,0608
1
ИС
4123986,4841
-319765,9637
296284,8399
404,1661
Шаг 3
 
 
 
 
 
 
 
 
 
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x 8
x2
0,9985
1
0,2002
0,0000
-0,1079
x3
1,0628
1
-0,0080
0,0007
-0,0033
x6
0,3639
-1,6461
0,0041
1
0,0449
x1
0,9120
1
0,0111
-0,0010
0,2046
x8
62,9111
-26,8520
0,7037
-158,9984
1
ИС
4415628,2468
299845,9804
89,5777
65427,7314
Определим затраты сырья по каждому виду:
железная руда: 2,7*0,9120+5,0*0,9985+3,9*1,0628=11,6 (тыс. т.);
марганец: 54*0,9120+56,6*0,9985+1500*1,0628=1700 (тыс. т.);
известняк: 4*0,9120+8*0,9985=11,6 (млн. т.);
цветные металлы: 5*0,9120+7*1,0628=12 (тыс. т.);
уголь: 1467*0,9120+1275*0,9985+1083*1,0628=3762 (тыс. т.).
Железная руда, марганец и цветные металлы будут израсходованы полностью. Значит, данные виды сырья являются дефицитными.
Остатки годовых запасов известняка составят 0,4 млн. т., угля – 63 тыс. т.
Вывод: годовой план производства продукции следующий: 3718 т. стали, 3065 т. чугуна, 3601 т. металлопроката; общая стоимость продукции составит 4415628 ($).
4.2. Транспортная задача
На станциях Ai (i=1,2,3) сосредоточен однородный груз в количестве ai тонн груза, который требуется перевезти на станции назначения Bj (j=1,2,3,4,5) в соответствии с потребностями каждой станции в bj тонн груза. Известны затраты cj на перевозку тонны груза с любой станции Ai на любую станцию Bj. Требуется составить такой план перевозок, чтобы весь груз был вывезен, все потребности были бы удовлетворены, а суммарные затраты были бы минимальны.
Пункты назначения
Запасы/потребности
85
65
90
30
30
Станции
A1
120
7
4
12
9
6
A2
80
11
2
7
3
15
A3
100
4
5
12
8
5
Решение
Имеется груза на станции: тонн.
Требуется пунктам назначения: тонн.
Т.к. , то данная задача – закрытого типа.
n = 3 (число строк); m= 5 (число столбцов).
n + m – 1 =7
Нам нужно заполнить 7 клеток матрицы значениями, показывающими, сколько тонн груза нужно отправить со станции Ai в пункт Bj. Остальные ячейки будут пустыми.
План X1 составим методом северо-западного угла.
bj
ai
85
65
90
30
30
120
7 85
4 35
12
9
6
80
11
2 30
7 50
3
15
100
4
5
12 40
8 30
5 30
Стоимость перевозки:
.
Введем числа и - потенциалы строк. Для всех ненулевых клеток выполняется равенство: . Вычислим значения потенциалов при . К матрице прибавим дополнительные строку и столбец, в который запишем значения потенциалов:
Вычисление потенциалов:

bj
ai
85
65
90
30
30
120
7 85
4 35
12
9
6
80
11
2 30
7 50
3
15
-2
100
4
5
12 40
8 30
5 30
3
7
4
9
5
2
План транспортной задачи оптимален, если для любой нулевой клетки сумма потенциалов не превосходит стоимости перевозки, т.е. для любой нулевой клетки таблицы выполняется неравенство: ; .
Проверим выполнение неравенств для свободных клеток плана X1:
; ;
; ;
; ;
;
.
План Х1 не оптимален, следовательно его можно улучшить.
Поскольку наибольшее значение , то значит, нужно включить перевозку в клетку (A3; B1).
Составим цикл – ломаную замкнутую линию, имеющую начало в свободной клетке, которую мы будем улучшать, а остальные вершины – в занятых клетках.
Цикл следует сначала нарисовать, а затем последовательно изменить перевозки на некоторую величину Q, прибавляя и вычитая ее, во всех клетках, соответствующим вершинам цикла.
Теперь определим величину Q как наименьшее из тех перевозок, где оно вычиталось: .
Новый план перевозок X2 получается подстановкой значения Q: