Задача целочисленного программирования

Математическая модель ЗЦП

Задача целочисленного программирования — это задача линейного программирования, в которой решение ищется в целых числах. Ниже представлена основная задача целочисленного программирования.

Математическая модель

Математическая модель задачи целочисленного программирования имеет следующий вид:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L^{\text{ц}}(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \le b_i, \ \forall i\in N_m \\ x_j \in \mathbb{N} \cup 0, \forall j\in N_n\end{cases}}

или

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L^{\text{ц}}(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \le b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \le b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \le b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \\ x_1 \in \mathbb{Z}, \ x_2 \in \mathbb{Z}, \ldots, \ x_n \in \mathbb{Z} \end{cases}}

Метод решения

Задача целочисленного программирования решается методом Гомори. Суть метода состоит в первоначальном решении симплекс-методом вспомогательной задачи линейного программирования (без ограничения целочисленности) вида:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \le b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_n\end{cases}}

или

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n \le b_1 \\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n \le b_2 \\ \ldots \\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n \le b_m \\ x_1 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \end{cases}}

Затем для нецелочисленной переменной оптимального решения вспомогательной задачи составляется ограничение отсечения и вновь решается вспомогательная задача, но уже М-методом. Причём если в r-ой строке последней симплекс-таблицы базисная переменная не является целочисленной (а она должна быть целочисленной по условию задачи), то составляется ограничение отсечения вида:

, где

{a_rj}=a_rj-[a_rj] - дробная часть числа.

Повторяя процедуру добавления ограничения отсечения и решения вспомогательной задачи, в конце получаем оптимальное целочисленное решение.

Пример решения

Задача целочисленного программирования имеет вид:

Строим вспомогательную задачу линейного программирования (без ограничения целочисленности):

Вспомогательную задачу приводим к каноническому виду:

Решаем первую вспомогательную задачу симплекс-методом:

Составляем первое ограничение отсечения (в ограничении используются десятичные дроби):

Решаем вторую вспомогательную задачу М-методом:

Составляем второе ограничение отсечения (в ограничении используются правильные дроби):

Решаем третью вспомогательную задачу М-методом:

Оптимальное решение последней вспомогательной задачи x₁=5, x₂=2, x₃=0, x₄=7, x₅=4, x₆=1, x₇=0, x₈=0, L=38.

Оптимальное решение задачи целочисленного программирования x₁=5, x₂=2, L^ц =38.

Другие задачи:

1. Каноническая задача;
2. Производственная задача;
3. Общая прямая задача линейного программирования;
4. Общая двойственная задача линейного программирования;
5. Задачи транспортного типа;
6. Задача целочисленного программирования;
7. Задача о рюкзаке;
8. Задача распределения средств;
9. Задача замены оборудования.

Литература

• Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование, «Наука», М., 1969.

Ссылки

• Участник:Logic-samara