Основные этапы решения задачи параметрического целочисленного программирования:
1. При
2. Находят значения
3. Если найденный оптимальный план целочисленный, то переходят к следующему пункту. Если найденный оптимальный план не целочисленный, то вводят дополнительное ограничение и вычисления продолжают до получения нового оптимального плана. Если и он является не целочисленным, то вводят новое ограничение. Процесс продолжают до тех пор, пока не будет найден целочисленный оптимальный план, или будет доказано, что задача не имеет целочисленного оптимального решения. Находят значения
4. Выбирают
5. Вычисления продолжают до тех пор, пока не будут исследованы все значения параметра
II способ. При решении предыдущего примера мы, после нахождения оптимального плана, сначала находили значения параметра
Возьмем
Таблица 4.2.1.
БП | СЧ | | | | | | |
| 1 | 2 | -1 | 1 | 1 | 0 | 0 |
| 2 | -4 | 2 | -1 | 0 | 1 | 0 |
| 5 | 3 | 0 | 1 | 0 | 0 | 1 |
С | 0 | | 1 | 3+4 | 0 | 0 | 0 |
Таблица 4.2.2.
БП | СЧ | | | | | | |
| 1 | 2 | -1 | 1 | 1 | 0 | 0 |
| 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| 4 | 1 | 1 | 0 | -1 | 0 | 1 |
С | -3 | | | 0 | -3 | 0 | 0 |
Таблица 4.2.3.
БП | СЧ | | | | | | |
| 4 | 0 | 0 | 1 | 2 | 1 | 0 |
| 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| 1 | 3 | 0 | 0 | -2 | -1 | 1 |
С | -15 | | 0 | 0 | | | 0 |
Таблица 4.2.4.
БП | СЧ | | | | | | |
| 4 | 0 | 0 | 1 | 2 | 1 | 0 |
| 11/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 |
| 1/3 | 1 | 0 | 0 | -2/3 | -1/3 | 1/3 |
С | | 0 | 0 | 0 | | | |
План оптимальный, но не целочисленный. Составим дополнительное ограничение для переменной
Дополнительное ограничение имеет вид:
Таблица 4.2.5.
БП | СЧ | | | | | | | |
| 4 | 0 | 0 | 1 | 2 | 1 | 0 | 0 |
| 11/3 | 0 | 1 | 0 | -1/3 | 1/3 | 2/3 | 0 |
| 1/3 | 1 | 0 | 0 | -2/3 | -1/3 | 1/3 | 0 |
| -2/3 | 0 | 0 | 0 | -2/3 | -1/3 | -2/3 | 1 |
С | | 0 | 0 | 0 | | | | 0 |
Применим двойственный симплекс-метод. Получим: