- •Введение
- •1. Линейное программирование
- •1.1 Решение задачи 1.1
- •1.2 Решение задачи 1.2
- •1.3 Решение задачи 1.3
- •1.4 Выводы к Главе 1
- •2. Целочисленное программирование
- •2.1 Решение полностью целочисленных задач Решение задачи методом отсекающих плоскостей
- •Решение задачи методом ветвей и границ
- •2.2 Решение частично целочисленной задачи
- •Глава 3. Нелинейное программирование
- •1) Критерий Сильвестра.
- •2) Метод характеристических чисел.
- •3.2Квадратичный симплекс метод (метод Била)
- •3.3 Преобразование нелинейной модели к сепарабельному виду. Аппроксимация нелинейной сепарабельной функции кусочно-линейной функцией
- •3.4 Решение задачи сепарабельным симплекс-методом
- •3.5 Определение погрешности решения
- •3.6. Выводы к главе 3
1.2 Решение задачи 1.2
Максимизировать целевую функцию:
Y=2x1-5x2+7x3 → max
При ограничениях:
0x1-2x2+x3 ≤ 1
2x1+x2+x3 ≤ 4
-x1-2x2+0x3 ≤ -1
0x1+2x2+0x3≤3
x1,2,3 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6 и х7.
0x1-2x2+x3+1x4+0x5+0x6+0x7 = 1
2x1+x2+x3+0x4+1x5+0x6+0x7 = 4
x1+2x2+0x3+0x4+0x5+1x6+0x7 = 1
0x1+2x2+0x3+0x4+0x5+0x6+1x7=3
Выразим допустимый базис в форме Таккера:
X4=1-(0x1-2x2+x3)
X5=4-(2x1+x2+x3)
X6=-1-(-x1-2x2+0x3)
X7=3-(0x1+2x2+0x3)
Целевая функция в форме Таккера:
Y=0-(-2x1+5x2-7x3)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.5).
Таблица 1.5
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X4 |
1 |
0 |
-2 |
1 |
1 |
0 |
0 |
0 |
|
X5 |
4 |
2 |
1 |
1 |
0 |
1 |
0 |
0 |
|
X6 |
-1 |
-1 |
-2 |
0 |
0 |
0 |
1 |
0 |
|
X7 |
3 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
|
Y |
0 |
-2 |
5 |
-7 |
0 |
0 |
0 |
0 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.6.
Таблица 1.6
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X4 |
1 |
0 |
-2 |
1 |
1 |
0 |
0 |
0 |
|
X5 |
2 |
0 |
-3 |
1 |
0 |
1 |
2 |
0 |
|
X1 |
1 |
1 |
2 |
0 |
0 |
0 |
-1 |
0 |
|
X7 |
3 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
|
Y |
2 |
0 |
9 |
-7 |
0 |
0 |
-2 |
0 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X4. Результат отображен в таблице 1.7.
Таблица 1.7
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X3 |
1 |
0 |
-2 |
1 |
1 |
0 |
0 |
0 |
|
X5 |
1 |
0 |
-1 |
0 |
-1 |
1 |
2 |
0 |
|
X1 |
1 |
1 |
2 |
0 |
0 |
0 |
-1 |
0 |
|
X7 |
3 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
|
Y |
9 |
0 |
-5 |
0 |
7 |
0 |
-2 |
0 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X1. Результат отображен в таблице 1.8.
Таблица 1.8
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X3 |
2 |
1 |
0 |
1 |
1 |
0 |
-1 |
0 |
|
X5 |
3/2 |
1/2 |
0 |
0 |
-1 |
1 |
3/2 |
0 |
|
X2 |
1/2 |
1/2 |
1 |
0 |
0 |
0 |
-1/2 |
0 |
|
X7 |
2 |
-1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
Y |
23/2 |
5/2 |
0 |
0 |
7 |
0 |
-9/2 |
0 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X6, выводим из базиса X5. Результат отображен в таблице 1.9.
Таблица 1.9
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X3 |
3 |
4/3 |
0 |
1 |
1/3 |
2/3 |
0 |
0 |
|
X6 |
1 |
1/3 |
0 |
0 |
-2/3 |
2/3 |
1 |
0 |
|
X2 |
1 |
2/3 |
1 |
0 |
-1/3 |
1/3 |
0 |
0 |
|
X7 |
1 |
-4/3 |
0 |
0 |
2/3 |
-2/3 |
0 |
1 |
|
Y |
16 |
4 |
0 |
0 |
4 |
3 |
0 |
0 |
В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.
Ответ : Решение оптимально
Y=16
X=(0;1;3;0;0;1;1)
Количество итераций=4