Методы и способы решения задач целочисленного параметрического программирования (стр. 11 из 15)
- 
, 
.Основные этапы решения задачи параметрического целочисленного программирования:
1. При
находят оптимальный план без условия целочисленности или устанавливают неразрешимость задачи.2. Находят значения
, для которых задача имеет один и тот же план, или неразрешима.3. Если найденный оптимальный план целочисленный, то переходят к следующему пункту. Если найденный оптимальный план не целочисленный, то вводят дополнительное ограничение и вычисления продолжают до получения нового оптимального плана. Если и он является не целочисленным, то вводят новое ограничение. Процесс продолжают до тех пор, пока не будет найден целочисленный оптимальный план, или будет доказано, что задача не имеет целочисленного оптимального решения. Находят значения
, для которых задача имеет одно и то же целочисленное оптимальное решение, или неразрешима.4. Выбирают
из оставшейся части 
и устанавливают возможность определения нового оптимального плана. Если он не целочисленный, то его приводят к целочисленному или доказывают, что задача не имеет целочисленного оптимального решения.5. Вычисления продолжают до тех пор, пока не будут исследованы все значения параметра
.II способ. При решении предыдущего примера мы, после нахождения оптимального плана, сначала находили значения параметра
, при которых план оставался оптимальным, и только потом приводили решение задачи к целочисленному виду. Попробуем при решении этой задачи сначала найти целочисленное оптимальное решение, а потом определить удовлетворяющий этому решению промежуток значения . Перейдем от неравенств к равенствам, добавляя к левым частям неравенств дополнительные переменные: 
Возьмем
(число 0 выбрано произвольно) и найдем симплекс-методом оптимальный план.Таблица 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 | 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 |
Применим двойственный симплекс-метод. Получим: