- •Пермская сельскохозяйственная академия имени академика д. Н. Прянишникова
- •«Решение задач линейного программирования распределительным методом»
- •Пермь 2009
- •Содержание
- •Задание……………………………………………………………………………….……3
- •Введение…………………………………………………………………………….…….4
- •Введение
- •2. Составление базисного плана способом северо-западного угла, расчет функции цели базисного плана.
- •3.Составление базисного плана методом наилучшего элемента. Расчет минимального значения функции цели базисного плана
- •4. Составление базисного плана методом аппроксимации (Фогеля) на минимальное значение функции цели. Расчет минимального значения функции цели базисного плана.
- •5. Сравнение результатов решения двух базисных планов
- •6. Проверка базисного плана, составленного методом наилучшего элемента на максимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата
- •7. Проверка базисного плана, составленного методом аппроксимации (Фогеля) на минимальное значение функции цели, на оптимальность методом потенциалов. Улучшение плана до оптимального результата.
2. Составление базисного плана способом северо-западного угла, расчет функции цели базисного плана.
Решение задачи на минимум методом северо-западного угла.
Заполнение начинается с крайней северо-западной клетки с последовательным удовлетворением потребности за счет отдельных производителей.
Проверка плана на вырождаемость m+n-1,
m – количество производителей,
n – количество потребителей.
В данном случае m+n-1=5+5-1=9, данное значение соответствует количеству занятых клеток, условие плана не вырождается.
Таблица 3 – Распределение ресурсов между потребителями методом северо-западного угла при решении задачи на минимум
|
В1 |
В2 |
В3 |
В4 |
ВФ |
Объем потребления |
А1 |
15 200 |
2 120 |
4 - |
19 - |
0 - |
320 |
А2 |
3 - |
4 780 |
14 - |
19 - |
0 - |
780 |
А3 |
22 - |
13 750 |
5 680 |
15 - |
0 - |
1430 |
А4 |
2 - |
6 - |
15 460 |
3 - |
0 - |
460 |
А5 |
8 - |
25 - |
11 360 |
29 600 |
0 100 |
1060 |
Объем производства |
200 |
1650 |
1500 |
600 |
100 |
4050
4050 |
F=200*15+120*2+780*4+13*750+680*5+460*15+360*11+600*29+100*0=47770руб.
3.Составление базисного плана методом наилучшего элемента. Расчет минимального значения функции цели базисного плана
Заполнение таблицы начинается с клетки с наилучшей оценкой, при исследовании функции на минимум – наименьшей оценкой, последовательно увязывая потребности в грузах с их наличием. Каждый шаг начинается только с наилучшей оценки. Если встречаются две одинаковые оценки, выполняется маршрут, по которому с наименьшим тарифом можно вывести наибольшее количество грузов. В данном случае получился следующий опорный базисный план.
Таблица 5 – Распределение ресурсов между потребителями методом наилучших оценок при решении задачи на минимум
|
В1 |
В2 |
В3 |
В4 |
ВФ |
Объем потребления |
А1 |
15 - |
2 320 |
4 - |
19 - |
0 - |
320 |
А2 |
3 200 |
4 580 |
14 - |
19 - |
0 - |
780 |
А3 |
22 - |
13 - |
5 1430 |
15 - |
0 - |
1430 |
А4 |
2 - |
6 - |
15 - |
3 460 |
0 - |
460 |
А5 |
8 - |
25 750 |
11 70 |
29 140 |
0 100 |
1060 |
Объем производства |
200 |
1650 |
1500 |
600 |
100 |
4050
4050 |
F=320*2+100*0+580*4+1430*5+200*3+460*3+750*25+140*29+70*11=35670руб.
4. Составление базисного плана методом аппроксимации (Фогеля) на минимальное значение функции цели. Расчет минимального значения функции цели базисного плана.
При решении задачи на минимум выбираются две клетки с наименьшими оценками, находят их разность (записывается в шагах). Из всех значений выбирается наибольший в этом столбце или строке. Находят клетку с наименьшей оценкой и в нее распределяют ресурс.
Метод аппроксимации требует более сложных вычислений, но дает опорное решение более близкое к оптимальному.
Таблица 6 – Распределение ресурсов между потребителями методом аппроксимации при решении задачи на минимум
|
В1 |
В2 |
В3 |
В4 |
Аф |
Объем потреб. |
1шаг |
2шаг |
3шаг |
4шаг |
5шаг |
6шаг |
7шаг |
8шаг |
|
А1 |
15 - |
2 320 |
4 - |
19 - |
0 - |
320 |
2 |
2 |
2 |
|
|
|
|
|
3 |
А2 |
3 - |
4 780 |
14 - |
19 - |
0 - |
780 |
1 |
1 |
1 |
1 |
|
|
|
|
4 |
А3 |
22 - |
13 550 |
5 740 |
15 140 |
0 - |
1430 |
8 |
8 |
8 |
8 |
8 |
17 |
17 |
|
7 |
А4 |
2 - |
6 - |
15 - |
3 460 |
0 - |
460 |
1 |
|
|
|
|
|
|
|
1 |
А5 |
8 200 |
25 - |
11 760 |
29 - |
0 100 |
1060 |
3 |
3 |
3 |
3 |
3 |
3 |
14 |
14 |
8 |
Объем пр-ва |
200 |
1650 |
1500 |
600 |
100 |
4050 4050 |
|
|
|
|
|
|
|
|
|
1шаг |
1 |
2 |
1 |
12 |
|
|
|
|
|
|
|
|
|
|
|
2шаг |
1 |
2 |
1 |
4 |
|
|
|
|
|
|
|
|
|
| |
3шаг |
1 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
| |
4шаг |
1 |
2 |
1 |
|
|
|
|
|
|
|
|
| |||
5шаг |
1 |
7 |
1 |
|
|
|
|
|
|
|
| ||||
6шаг |
1 |
12 |
1 |
|
|
|
|
|
|
|
|
|
| ||
7шаг |
1 |
|
1 |
|
|
|
|
|
|
|
|
| |||
8шаг |
|
|
1 |
|
|
|
|
|
|
|
|
|
| ||
|
7 |
6 |
8 |
2 |
|
|
|
|
|
|
|
|
|
F=320*2+780*4+740*5+550*13+140*15+460*3+200*8+760*11+100*0=28050 руб.