Методы и способы решения задач целочисленного параметрического программирования (стр. 3 из 15)
1. Находят решение задачи целочисленного программирования (2.1.1)-(2.1.3).
2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (2.1.1)-(2.1.3) является дробным числом.
3. Находят решение задач
и 
, которые получаются из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительных ограничений.4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам
и , и находят их решение. Итерационный процесс продолжается до тех пор, пока не будет найден оптимальный целочисленный план задачи (2.1.1)-(2.1.4).2.2 Пример решения задачи целочисленного программирования
Пример 2.2.1. Найти наименьшее значение
при ограничениях 
Решение. Умножим второе неравенство на (-1):
Для того чтобы перейти от неравенств к равенствам, добавим к левым частям неравенств дополнительные переменные:
За базисные переменные примем дополнительные переменные
. тогда свободными переменными являются 
. Целевая функция в дополнительных преобразованиях не нуждается, так как уже выражена через свободные переменные. Далее начнем заполнять симплексные таблицы.Таблица 2.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 | 0 | 0 | 0 |
Таблица 2.2.2
| БП | СЧ | | | | | | |
 | 1 | 2 | -1 | 1 | 1 | 0 | 0 |
| | 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| | 4 | 1 | 1 | 0 | -1 | 0 | 1 |
| С | -3 | -7 | 4 | 0 | 0 | 0 | 0 |
Таблица 2.2.3
| БП | СЧ |  | | | | | |
| | 4 | 0 | 0 | 1 | 2 | 1 | 0 |
 | 3 | -2 | 1 | 0 | 1 | 1 | 0 |
| | 1 | 3 | 0 | 0 | -2 | -1 | 1 |
| С | -15 | 1 | 0 | 0 | -7 | -4 | 0 |
Таблица 2.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 |
| С | -46/3 | 0 | 0 | 0 | -19/3 | -11/3 | -1/3 |
Получили оптимальное решение этой задачи
, в котором 
- дробные. Составим дополнительное ограничение для переменной, имеющей наибольшую дробную часть. Имеем: 
Тогда согласно формуле (2.1.5), дополнительное ограничение имеет вид:
Умножим обе части последнего неравенства на (-1) и преобразуем его в уравнение:
Допишем коэффициенты этого уравнения снизу к таблице 2.2.4, добавим дополнительный столбец, соответствующий переменной
, получимТаблица 2.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 |
| С | -46/3 | 0 | 0 | 0 | -19/3 | -11/3 | -1/3 | 0 |
Применим двойственный симплекс – метод, в результате получим
Таблица 2.2.6
| БП | СЧ | | | | | | | |
| | 4 | 0 | 0 | 1 | 2 | 1 | 0 | 0 |
| | 3 | 0 | 1 | 0 | -1 | 0 | 0 | 1 |
| | 0 | 1 | 0 | 0 | -1 | -1/2 | 0 | 1/2 |
| | 1 | 0 | 0 | 0 | 1 | 1/2 | 1 | -3/2 |
| С | -15 | 0 | 0 | 0 | -6 | -7/2 | 0 | -1/2 |
Оптимальное целочисленное решение:
