- •Министерство образования и науки рф
- •Тема: Создание экономико-математических моделей для задач линейного программирования
- •2. Теоретические сведения
- •Тема: Графический метод решения задачи линейного программирования
- •2. Теоретические сведения
- •3.Задание
- •Тема: Нахождение опорного (базисного) решения методами Гаусса и м-базиса
- •2. Теоретические сведения
- •2.1 Метод Гаусса
- •2.2 Искусственный базис (м - базис)
- •3. Задание
- •Тема: Решение задач линейного программирования симплекс-методом
- •2. Теоретические сведения
- •2.1 Алгоритм симплекс-метода
- •3. Задание.
- •Тема: Решение двойственных задач линейного программирования
- •1.Цель работы
- •2. Теоретические сведения
- •3. Задание
- •Тема: Решение транспортных задач
- •1. Цель работы
- •2.2 Построение первого опорного плана - методом наименьших тарифов
- •2.3 Построение первого опорного плана - методом “северо-западного угла“
- •2.4 Построение первого опорного плана методом двойного предпочтения
- •2.5 Проверка опорного плана на оптимальность
2.2 Искусственный базис (м - базис)
Исходную ОЗЛП представленную в виде:
F = min (c1x1+….+cnxn)
при условии хi > 0 и
a11x1 + a12x2 +…+ a1nxn = b1;
a21x1 + a22x2 +…+ a2nxn = b2; (6)
………………………….
am1x1 + am2x2 +…+ amnxn =bm;
заменяем расширенной задачей следующим образом:
а) Свободные члены ( bi ) должны быть неотрицательны.
б) К каждому уравнению добавляется по одной неотрицательной переменной zi (i=1,2,….m)
в) К целевой функции добавляем сумму переменных zi, умноженную на большое число М (допустим на три порядка больше коэффициентов ai, bi, ci)
В результате получаем:
F = min [(c1x1+….+cnxn)+M(z1+z2+…+zm)]
при условии хi > 0 и ограничениях:
a*11x1 + a*12x2 +…+ a*1nxn + у1 = b*1;
a*21x1 + a*22x2 +…+ a*2nxn + у2 = b*2; (7)
………..………………………….
a*m1x1 + a*m2x2 +…+ a*mnxn + уm= b*m;
где a*I= ai если bi ≥ 0 b*I= b i если bi ≥ 0
-ai если bi ≤ 0 -bi если bi ≤ 0
В задаче (7) опорное решение получим, приняв в качестве базисных переменных уi,. Оно имеет вид при х1,…..xn =0;
у1=b *1;…. уm = b*m
Пример.
Определить состав продуктов на сутки, содержащий необходимые питательные вещества и обеспечивающий минимальную общую стоимость продуктов.
Содержание питательных веществ в 1 кг продуктов. Таблица 2
Питательные вещества |
Нормы суточной потребности |
Содержание питательных веществ в 1 кг продуктов | ||||
Молоко |
Масло |
Сыр |
Крупа |
Картофель | ||
Белки, г |
118 |
30 |
70 |
260 |
130 |
21 |
Жиры ,г
|
56 |
40
|
865 |
310
|
30 |
2
|
Углеводы, г
|
500 |
50 |
6 |
20 |
650 |
200 |
Минеральные вещества, г |
8
|
7
|
12 |
60
|
20 |
70
|
Стоимость 1 кг продукта |
|
8 |
60 |
70 |
10 |
4 |
Количество продуктов |
|
х1
|
х2 |
х3
|
х4 |
х5
|
Составляем математическую модель.
Целевая функция имеет вид:
F(X) = max (8x1 + 60x2 +70x3 +10x4 +4x1+ M•(y1+ y2 +y3 +y4))
При ограничениях:
30x1 + 70x2 + 260x3 + 130x4 + 21x5 + у1 = 118
40x1 + 865x2 + 310x3 + 30x4 + 2x5 + у2 = 56
50x1 + 6x2 + 20x3 + 650x4 + 200x5 + у3 = 500
7x1 + 12x2 + 60x3 + 20x4 + 70x5 + у4 = 8
Выразим у1 – у4 через основные переменные
у1 = 118 - 30x1 - 70x2 - 260x3 - 130x4 - 21x5
у2 = 56 - 40x1 - 865x2 - 310x3 - 30x4 - 2x5
у3 = 500 - 50x1 - 6x2 - 20x3 - 650x4 - 200x5
у4 = 8 - 7x1 - 12x2 - 60x3 - 20x4 - 70x5
Найдем значение целевой функции при x1= x2= x3= x4= x5=0 (свободные переменные)
F(х)= max (M(118 - 30x1 - 70x2 - 260x3 - 130x4 - 21x5 + 56 - 40x1 -865x2 –
-310x3 - 30x4 - 2x5 + 500 - 50x1 - 6x2 - 20x3 - 650x4 - 200x5 +8 - 7x1 - 12x2 –
-60x3 - 20x4 -70x5))
F(x) = M (682 - 127x1 - 953x2 - 650x3 - 830x4 - 293x5)
Начальный опорный план задачи. Таблица 3
Коэффициенты целевой функции |
-127 |
-953 |
-650 |
-830 |
-293 |
0 |
0 |
0 |
0 |
| ||
План |
Базисные переменные |
Значения базисных переменных |
х1 |
х2 |
х3 |
х4 |
х5 |
y1 |
y 2 |
y3 |
y4 |
zi |
1 |
y1
y2
y3
y4
|
118
56
500
8 |
30
40
50
7 |
70
865
6
12 |
260
310
20
60 |
130
30
650
20 |
21
2
200
70
|
1
0
0
0 |
0
1
0
0 |
0
0
1
0 |
0
0
0
1
|
|
Индексная строка |
F(X) |
682*М |
127*М |
953*М |
650*М |
830*М |
293*М |
0 |
0 |
0 |
0 |
|
Где М = 100000