- •Введение
- •1 Общая формулировка задания на курсовой проект
- •2 Линейное программирование
- •2.1.6 Метод допустимого базиса
- •2.1.7 Решение двойственной задачи
- •2.2 Задача целочисленного линейного программирования
- •2.2.1 Постановка задачи целочисленного линейного программирования
- •2.2.2 Метод Гомори
- •2.2.3 Метод ветвей и границ
- •2.3 Задача целочисленного линейного программирования с булевскими переменными
- •2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными
- •2.3.2 Метод Баллаша
- •2.3.3 Определение снижения трудоемкости вычислений
- •3.2 Задача одномерной оптимизации функции
- •Заключение
- •Библиографический список
- •Приложение а Текст программы глобальной многомерной оптимизации
- •Б. Результаты работы программы
2.3.2 Метод Баллаша
№ |
x4 |
x3 |
x2 |
x1 |
x5 |
Выполнение ограничений |
Значение F | |||||
0 |
1 |
2 |
3 |
4 |
5 | |||||||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
Fф=0 |
2 |
0 |
0 |
0 |
0 |
1 |
44 |
|
|
|
|
|
|
3 |
0 |
0 |
0 |
1 |
0 |
17 |
|
|
|
|
|
|
4 |
0 |
0 |
0 |
1 |
1 |
61 |
|
|
|
|
|
|
5 |
0 |
0 |
1 |
0 |
0 |
13 |
|
|
|
|
|
|
6 |
0 |
0 |
1 |
0 |
1 |
57 |
|
|
|
|
|
|
7 |
0 |
0 |
1 |
1 |
0 |
30 |
|
|
|
|
|
|
8 |
0 |
0 |
1 |
1 |
1 |
74 |
|
|
|
|
|
|
9 |
0 |
1 |
0 |
0 |
0 |
-10 |
+ |
+ |
+ |
+ |
+ |
Fф=-10 |
10 |
0 |
1 |
0 |
0 |
1 |
34 |
|
|
|
|
|
|
11 |
0 |
1 |
0 |
1 |
0 |
7 |
|
|
|
|
|
|
12 |
0 |
1 |
0 |
1 |
1 |
51 |
|
|
|
|
|
|
13 |
0 |
1 |
1 |
0 |
0 |
3 |
|
|
|
|
|
|
14 |
0 |
1 |
1 |
0 |
1 |
47 |
|
|
|
|
|
|
15 |
0 |
1 |
1 |
1 |
0 |
20 |
|
|
|
|
|
|
16 |
0 |
1 |
1 |
1 |
1 |
64 |
|
|
|
|
|
|
17 |
1 |
0 |
0 |
0 |
0 |
-49 |
+ |
+ |
+ |
+ |
+ |
Fф=-49 |
18 |
1 |
0 |
0 |
0 |
1 |
-5 |
|
|
|
|
|
|
19 |
1 |
0 |
0 |
1 |
0 |
-32 |
|
|
|
|
|
|
20 |
1 |
0 |
0 |
1 |
1 |
12 |
|
|
|
|
|
|
21 |
1 |
0 |
1 |
0 |
0 |
-36 |
|
|
|
|
|
|
22 |
1 |
0 |
1 |
0 |
1 |
8 |
|
|
|
|
|
|
23 |
1 |
0 |
1 |
1 |
0 |
-19 |
|
|
|
|
|
|
24 |
1 |
0 |
1 |
1 |
1 |
25 |
|
|
|
|
|
|
25 |
1 |
1 |
0 |
0 |
0 |
-59 |
+ |
+ |
+ |
+ |
+ |
Fф=-59 |
26 |
1 |
1 |
0 |
0 |
1 |
-15 |
|
|
|
|
|
|
27 |
1 |
1 |
0 |
1 |
0 |
-42 |
|
|
|
|
|
|
28 |
1 |
1 |
0 |
1 |
1 |
2 |
|
|
|
|
|
|
29 |
1 |
1 |
1 |
0 |
0 |
-46 |
|
|
|
|
|
|
30 |
1 |
1 |
1 |
0 |
1 |
-2 |
|
|
|
|
|
|
31 |
1 |
1 |
1 |
1 |
0 |
-29 |
|
|
|
|
|
|
32 |
1 |
1 |
1 |
1 |
1 |
15 |
|
|
|
|
|
|
Фильтрующее ограничение: