Линейное программирование
Работа из раздела: «
Экономико-математическое моделирование»
/
/
Федеральное агентство железнодорожного транспорта
Уральский государственный университет путей сообщения
Кафедра высшей математики
КУРСОВОЙ ПРОЕКТ
по предмету
Математическое моделирование
тема:
Линейное программирование
Выполнил: студент группы ЭкТ
Сычёв А.В.
Проверил: преподаватель
Филипова Е.Г.
Екатеринбург, 2010 г.
Графическое решение задач линейного программирования
Задача: Фирма выпускает два вида варенья: клубничное и малиновое. Для изготовления варенья используют три исходных продукта: ягоды, сахар и вода, расходы которых приведены в таблице, и известны суточные запасы.
|
продукт
|
расход на 1 кг.
|
запас, кг.
|
|
|
клубничное
|
малиновое
|
|
|
|
ягоды
|
2
|
5
|
50
|
|
|
сахар
|
4
|
3
|
44
|
|
|
вода
|
4
|
1
|
36
|
|
|
Розничная цена 1 килограмма клубничного варенья равна 2 евро, а малинового 1 евро.
Найти: Какое количество каждого вида повидла должна производить фирма, чтобы доход от реализации был максимальным.
Решение:
Пусть x1, кг. - необходимое количество клубничного варенья; x2, кг. - необходимое количество малинового варенья. ( 1, 2 ?0)
Тогда получим систему ограничений:
> max
Задача составлена. Решим ее графически.
1. Построим прямые
:
|
10
|
0
|
|
|
6
|
10
|
|
|
5
|
8
|
|
|
8
|
4
|
|
|
7
|
8
|
|
|
8
|
4
|
|
|
Общее решение: A, B, C
Общее допустимое решение: A, B, C, D, 0, A
2. ={16;14} - нормальный вектор целевой функции. Строи линию уровня и передвигаем ее в сторону нормального вектора целевой функции до тех пор, пока она не коснется фигуру ровно один раз.
3. Таким образом оптимальное решение достигается в вершине С, С =
4. C: ?- 4 ?
5. Таким образом, для того, чтобы доход был максимальным необходимо изготавливать 8 килограмм клубничного варенья и 4 килограмма малинового. При этом доход от реализации продукции составляет:
6. Сосчитаем остаток продукции на складе фирмы:
Умножаем значение оптимального количества килограмм на количество килограмм затраченных на приготовление 1 килограмма обоих варений. Затем их складываем и вычитаем из запасов. То же самое проделываем с остальными двумя продуктами.
· 50 - (8*2+4*5) =14 кг. - остаток ягод;
· 44 - (8*4+4*3)=0 кг. - остаток сахара;
· 36 - (8*4+4*1)=0 кг. - остаток воды.
Ответ: для того чтобы реализация от продажи было максимальным, фирме ежедневно нужно выпускать 8 килограмм клубничного варенья и 4 килограмма малинового. При таком выпуске продукции доход фирмы составляет 20 евро, при стоимости 1 килограмма клубничного варенья в 2 евро, а малинового - 1 евро. При этом на складе от суточного запаса продуктов, входящих в состав варенья остается: 14 килограмм ягод, 0 килограмм сахара и 0 килограмм воды.
Симплекс метод
Задача: рассматриваем условие предыдущей задачи.
Найти: Какое количество каждого вида повидла должна производить фирма, чтобы доход от реализации был максимальным, остаток продукции на складе.
Решение:
1. Составляем каноническую модель
2. Нулевой шаг. Составим симплекс таблицу
|
bi
|
x1
|
x2
|
x3
|
x4
|
x5
|
|
|
50
|
2
|
5
|
1
|
0
|
0
|
|
|
44
|
4
|
3
|
0
|
1
|
|
|
|
36
|
4
|
1
|
0
|
0
|
:4 *(-1) *(-0,5)
|
|
|
0
|
2
|
1
|
0
|
0
|
0
|
|
|
X0 = (0; 0; 50; 44; 36) - опорное решение
=0
Из последней строки выбираем наибольшее значение. Это число 2 ? х1 - разрешающий столбец. Ищем минимальное значение в этом столбце.
Выбираем разрешающий элемент равный 4, получим новую симплекс таблицу.
3. Первый шаг
|
bi
|
x1
|
x2
|
x3
|
x4
|
x5
|
|
|
32
|
0
|
4,5
|
1
|
0
|
-0,5
|
|
|
8
|
0
|
2
|
0
|
1
|
-1
|
:2 *(-2,25) *(-0,125) *(-0,25)
|
|
|
9
|
1
|
0,25
|
0
|
0
|
0,25
|
|
|
-18
|
0
|
0,5
|
0
|
0
|
-0,5
|
|
|
X1 = (9; 0; 32; 8; 0) - опорное решение
=18
Так как в последней строке есть положительный элемент, необходимо сделать еще один шаг, выбираем столбец с положительным значением в последней строке. Он будет являться разрешающим.
Переводим х2 в базис, получим новую симплекс таблицу.
4. Второй шаг.
|
bi
|
x1
|
x2
|
x3
|
x4
|
x5
|
|
|
14
|
0
|
0
|
1
|
-2,25
|
1,75
|
|
|
4
|
0
|
1
|
0
|
0,5
|
-0,5
|
|
|
8
|
1
|
0
|
0
|
-0,125
|
0,375
|
|
|
-20
|
0
|
0
|
0
|
-0,25
|
-0,25
|
|
|
X2 = (8; 4; 14; 0; 0) - оптимальное решение
=20 (евро)
В последней строке нет положительный элементов. Следовательно, симплекс метод закончен.
Ответ: в ходе решения задачи симплекс методом получили оптимальное решение (8;4;14;0;0), где первые две цифры являются значением х1 (количество килограмм клубничного варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) и х2 (количество килограмм малинового варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) соответственно, а остальные - это остаток сырья на складе. Так же получили значение =20 (евро), являющиеся максимальным доходом от реализации продукции.
Правильность вычислений можно проверить сравнением ответов с задачей, решенной графическим способом:
линейный программирование графический транспортный
|
ответ полученный графическим способом
|
ответ полученный симплекс методом
|
|
|
х1, кг
|
8
|
8
|
|
|
х2, кг
|
4
|
4
|
|
|
, евро
|
20
|
20
|
|
|
остаток ягод, кг
|
14
|
14
|
|
|
остаток сахара, кг
|
0
|
0
|
|
|
остаток воды, кг
|
0
|
0
|
|
|
Двойственная задача линейного программирования
Задача: рассматриваем условие первой задачи.
Найти: какую цену следует назначить единице каждого из составляющих продуктов, для минимальной общей стоимости затрат на производство клубничного и малинового варенья.
Решение:
1. Составим двойственную задачу из исходной (см. условие графической задачи). Для этого все матрицы исходной задачи транспонируются. При этом неравенство исходной системы имеют одинаковый знак (? или ?)
Исходная задача:
> max,
где х1 и х2 - количество килограмм каждого из варений.
Двойственная задача:
,
где - цена одного килограмма ягод, сахара и воды соответственно
- опорное решение двойственной задачи.
2. Имеем х1=8 и х2=4. Подставим их в ограничения исходной задачи и найдем строгое неравенство.
? ? ?- ?
=2
;
(евро)
Ответ: продавец согласен продать, а покупатель купить за 0,25 евро один килограмм сахара, за такую же цену килограмм воды, а килограмм ягод отдать бесплатно. При этом минимальные затраты на производство варенья составят 20 евро.
Правильность решения можно проверить, сравнив данные из этой задачи с данными из последней таблицы, полученной в ходе решения симплекс методом. Эти данные должны быть равны друг другу, но только с обратным знаком.
Проверка:
;
0,25=;
0,25=0,25;
;
0,25=;
0,25=0,25;
Транспортная задача
Задача: в порту стоят три рыболовецких судна А1, А2, А3, вмещающих рыбу в количествах 125 тонн, 125 тонн и 105 тонн соответственно. Необходимо доставить свежо пойманную рыбу в пять магазинов, находящиеся от порта на 60, 65, 95, 35 и 100 километров соответственно. Стоимость перевозки одной тонны из судна Аi в магазин Bj заданы в виде матрицы.
C= ; A= ; B=
Найти: минимальные суммарные затраты на перевозку рыбы из суден в магазины.
Решение:
?
355=355 ? закрытая транспортная задача.
1. Метод северо-западного угла
|
B1
|
B2
|
B3
|
B4
|
B5
|
запас
|
|
|
A1
|
|
8
|
|
7
|
|
15
|
|
2
|
|
4
|
125
|
|
|
60
|
65
|
0
|
|
|
|
|
|
A2
|
|
2
|
|
10
|
|
23
|
|
7
|
|
18
|
125
|
|
|
|
|
95
|
30
|
|
|
|
|
A3
|
|
24
|
|
15
|
|
6
|
|
9
|
|
35
|
105
|
|
|
|
|
|
5
|
100
|
|
|
|
потребности
|
60
|
65
|
95
|
35
|
100
|
355
|
|
|
n+m-1=5+3-1=7
F - суммарные затраты на перевозку
F1=
(рублей)
2. Метод наименьшей стоимости в таблице
|
V1
|
V2
|
V3
|
V4
|
V5
|
запас
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
|
|
|
U1
|
A1
|
|
8
|
|
7
|
|
15
|
|
2
|
|
4
|
125
|
|
|
|
|
0
|
|
35
|
90
|
|
|
|
U2
|
A2
|
|
2
|
|
10
|
|
23
|
|
7
|
|
18
|
125
|
|
|
|
60
|
65
|
|
|
|
|
|
|
U3
|
A3
|
|
24
|
|
15
|
|
6
|
|
9
|
|
35
|
105
|
|
|
|
|
|
95
|
|
10
|
|
|
|
потребности
|
60
|
65
|
95
|
35
|
100
|
355
|
|
|
n+m-1=5+3-1=7
F - суммарные затраты на перевозку
F2=
(рублей)
3. Метод потенциалов
Проверим на оптимальность план, полученный во второй таблице.
|
V1
|
V2
|
V3
|
V4
|
V5
|
запас
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
|
|
|
U1
|
A1
|
|
8
|
|
7
|
|
15
|
|
2
|
|
4
|
125
|
|
|
|
|
0
|
|
35
|
90
|
|
|
|
U2
|
A2
|
|
2
|
|
10
|
|
23
|
|
7
|
|
18
|
125
|
|
|
|
60
|
65
|
|
|
|
|
|
|
U3
|
A3
|
|
24
|
|
15
|
|
6
|
|
9
|
|
35
|
105
|
|
|
|
|
|
95
|
|
10
|
|
|
|
потребности
|
60
|
65
|
95
|
35
|
100
|
355
|
|
|
1) Для занятых клеток
2) Для свободных клеток
Так как имеются нарушения, то проверяемый план не является оптимальным. Среди нарушений выбираем наибольшее и строим цикл перерасчета данной клетки. Наибольшим нарушением является
|
V1
|
V2
|
V3
|
V4
|
V5
|
запас
|
|
|
B1
|
B2
|
B3
|
B4
|
B5
|
|
|
|
U1
|
A1
|
|
8
|
|
7
|
|
15
|
|
2
|
|
4
|
125
|
|
|
|
|
0
|
|
25
|
100
|
|
|
|
U2
|
A2
|
|
2
|
|
10
|
|
23
|
|
7
|
|
18
|
125
|
|
|
|
60
|
65
|
|
|
|
|
|
|
U3
|
A3
|
|
24
|
|
15
|
|
6
|
|
9
|
|
35
|
105
|
|
|
|
|
|
95
|
10
|
|
|
|
|
потребности
|
60
|
65
|
95
|
35
|
100
|
355
|
|
|
n+m-1=5+3-1=7
F - суммарные затраты на перевозку
F3=
(рублей)
1) Для занятых клеток
2) Для свободных клеток
Так как нарушений не наблюдается, то считается что план, полученный в последней таблице является оптимальным.
Ответ: в ходе решения задачи получили следующие данные:
§ минимальные суммарные затраты на перевозку
F1 = 6875 рублей (метод северо-западного угла);
F2 = 2120 рублей (метод наименьшей стоимости);
F3 = 1880 рублей (метод потенциалов)
§ оптимальный план перевозок можно представить в виде матрицы
C=
Транспортная задача на сети
Задача: даны узлы (обозначены кругом или квадратом) и дуги (прямые, соединяющие узлы). На каждой дуге указывается длина или стоимость перевозки единицы груза. На каждой вершине показываются запасы груза со знаком «+» (склад - квадрат) и потребности в этом грузе со знаком «-» (потребители - круг).
Найти: задача состоит в том, чтобы распределить между станциями перевозки с наименьшими затратами.
Решение:
1. составим схему
2. Число загруженных дуг n-1, где n - количество вершин
n=10; 10 - 1 = 9 - загруженные дуги
3. Один из потенциалов выбираем произвольно. Пусть А1=100. Далее двигаемся по загруженным дугам, если направление совпадает, то к известному потенциалу прибавляем значение указанное на дуге, если направление встречное - вычитаем.
4. Выполняем проверку по свободным дугам. Для этого из большего потенциала вычитаем меньший и полученную разность должна быть меньше либо равна расстоянию, указанного на дуге.
/
/
Нарушений среди свободных дуг нету, значит этот план является оптимальным.
5. Суммарные затраты на перевозку считаются путем сложения произведения значения загруженной дуги на значение перевозки.
.
Ответ: оптимальный план перевозок представлен на схеме. При таком раскладе суммарные затраты на перевозку составляют
