Сайт о телевидении

Пусть оптимальный план, полученный симплекс-методом для задачи (5.1)-(5.3), следующий: и получен на базисе
Тогда последняя симплексная таблица имеет следующий вид:

Таблица 5.1

Приведённая к базису симплексная таблица для задачи целочисленного программирования

Предположим, что
дробное; тогда некоторое
также дробное (в противном случае задача не имеет целочисленного решения). Обозначим через
и
целые части чисели, т.е. наибольшие целые числа, не превосходящие числаи. Тогда величины дробных частейичиселиопределяются как разности:

где и

Например,

.

Так как по условию
– неотрицательные целые числа, то и разностьтакже целое неотрицательное число.

Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную
умножим уравнение на –1, добавим к последней симплексной таблице и, применяя симплексный метод (желательно двойственный), находим новый план. Если он не является целочисленным, то по последней симплексной таблице составляем новое дополнительное ограничение.

Если в оптимальном плане задачи (5.1)-(5.3) несколько дробных
то дополнительное ограничение составляют дляmax. Это ускоряет процесс получения оптимального целочисленного решения.

Рассмотрим геометрический смысл введения дополнительного ограничения (см. рис. 5.2). Пусть в точке A многогранника решений Q функция Z достигает максимального значения Z (A )=max, но координаты точки A – дробные. Тогда введенные ограничения по целочисленности I и II от области Q отсекают область с угловой точкой
, координаты которой целочисленные и в которой линейная функция достигает максимального значения.

Рис.5.2. Геометрический смысл ограничения Гомори

Метод Гомори рассмотрим на примере следующей задачи.

Пример 5.1. Найти максимальное значение функции

при условиях

Дать геометрическую интерпретацию решения задачи.

Решение. Для определения оптимального плана задачи (5.5)-(5.8) сначала находим оптимальный план задачи (5.5)-(5.7):

Таблица 5.2

базис
план
– неоптимальный,
.

Таблица 5.3

Симплекс-таблица, приведённая к базису

,
– неоптимальный, базис
,
.

Таблица 5.4

Симплекс-таблица, приведённая к базису

Оптимальный план
, базис
. Этот оптимальный план не является оптимальным планом задачи (5.5)-(5.8), поскольку две компонентыиимеют нецелочисленное значение. При этом дробные части этих чисел
равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной(чаще берут первую строку). Из последнейсимплекс-таблицы имеем:

.

Таким образом, к системе ограничений задачи (5.5)-(5.7) добавляем неравенство

Теперь находим максимальное значение функции (5.5) при выполнении условий (5.6), (5.7) и (5.9). В условие (5.9) вводим дополнительную переменную :

Таблица 5.5

Ввод в симплекс-таблицу дополнительной переменной

Выберем .
базис.

Таблица 5.6

Приведение симплекс-таблицы к базису

Базис
.
.

Запишем оптимальный план для исходной задачи:
При этом плане значение целевой функции равно
.

Геометрическая интерпретация решения задачи.

Рис.5.3. Геометрическая интерпретация решения задачи

Областью допустимых решений задачи (5.5)-(5.7) является многоугольник ОАВС D (рис. 5.3). Из рисунка видно, что максимальное значение целевая функция принимает в точке
т.е.
является оптимальным планом. Так как этот план не является оптимальным планом задачи (5.5)-(5.8) (числаи– дробные), то вводится дополнительное ограничение

Исключая из этого неравенства иподстановкой вместо них соответствующих значений из уравнений системы ограничений (5.6), получим
.

.

Этому неравенству соответствует полуплоскость, ограниченная прямой
отсекающей отмногоугольника ОАВСD треугольник EFC .

Как видно из рисунка, областью допустимых решений полученной задачи является многоугольник OABEFD . В точке E (9;4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты точки Е – целые числа и неизвестные
ипринимают целочисленные значения при подстановке в уравнения (5.6) значений
и
то
является оптимальным планом задачи (5.5)-(5.8). Это следует и из таблицы симплекс-метода.

Замечание к использованию метода Гомори: если в первоначальный базис задачи входили искусственные векторы, то при составлении дополнительного ограничения искусственные переменные необходимо опустить.

Вопросы для самопроверки

Области применения целочисленного программирования.

Постановка задачи целочисленного программирования.

Графический способ решения задачи целочисленного программирования.

Алгоритм метода Гомори.

Правило составления дополнительного ограничения (сечения Гомори).

Геометрический смысл введения сечения Гомори.

Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограниче­ниям задачи добавляется новое ограничение, обладающее сле­дующими свойствами:

Оно должно быть линейным;

Должно отсекать найденный оптимальный нецелочислен­ный план;

Не должно отсекать ни одного целочисленного плана.

Дополнительное ограничение, обладающее указанными свой­ствами, называется правильным отсечением.

Геометрически добавление ка­ждого линейного ограничения отвечает проведению прямой (ги­перплоскости), которая отсекает от многоугольника (многогран­ника) решений некоторую его часть вместе с оптимальной точ­кой с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранни­ка. В результате новый много­гранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полу­ченное при этом многограннике оптимальное решение будет целочисленным (рис. 8.1).

жающие основные переменные *1, *2, новные переменные Хт+1, Хт+2, ..., Хт+1, решения

Хт через неос- х„ оптимального

нецелая компонента. В этом случае можно доказать, что неравен­ство

{Р, } - {а," т+\}хт+1 ■ -~{ат }Хп ^ 0, (* )

сформированное по /-му уравнению системы (8.5), обладает всеми свойствами правильного отсечения.

Для решения задачи целочисленного линейного программиро­вания (8.1)-(8.4) методом Гомори используется следующий ал­горитм:

1. Симплексным методом решить задачу (8.1)-(8.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочис­ленного программирования (8.1)-(8.4). Если первая задача (8.1)-

(8.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (8.1)-(8.4) также неразре­шима.

2. Если среди компонент оптимального решения есть неце­лые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (8.5) сформировать пра­вильное отсечение (8.6).

3. Неравенство (8.6) введением дополнительной неотрицатель­ной целочисленной переменной преобразовать в равносильное уравнение

{Р(} - |а/ т+1 }*т+1- ■-{а|"л }хп + хп+1 > (®*^)

и включить его в систему ограничений (8.2).

4. Полученную расширенную задачу решить симплексным ме­тодом. Если найденный оптимальный план будет целочисленным,

то задача целочисленного программирования (8.1)-(8.4) решена. В противном случае вернуться к п. 2 алгоритма.

Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.

Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответст­вующее уравнение не имеет решения в целых числах. В этом слу­чае и данная задача не имеет целочисленного оптимального ре­шения.

^ 8.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден. ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать обо­рудование двух видов: менее мощные машины типа А стоимостью 3 ден. ед., требующие производственную площадь 3 кв. м (с уче­том проходов) и обеспечивающие производительность за смену 2 т зерна, и более мощные машины типа В стоимостью 4 ден. ед., занимающие площадь 5 кв. м и обеспечивающие производитель­ность за смену 3 т сортового зерна.

Требуется составить оптимальный план приобретения оборудо­вания, обеспечивающий максимальную общую производитель­ность при условии, что фермер может приобрести не более 8 ма­шин типа В.

Решение. Обозначим через х\, х2 количество машин соот­ветственно типа А и В, через Z - общую производительность. Тогда математическая модель задачи примет вид:

На рис. 8.2 ОКЬМ - область допустимых решений задачи (8.1") - (8.3"), ограниченная прямыми (1), (2), (3) и осями координат; />(2/3; 8) - точка оптимального, но нецелочисленного решения зада­чи (8.1") - (8.3"); (4) - прямая, отсекающая это нецелочисленное решение; 0№М - область допустимых решений расширенной зада­чи (8.1’) - (8.3’), (8.61); М2; 7) - точка оптимального целочисленно­го решения.

I шаг. Основные переменные х3, х4, *5; неосновные перемен­ные Х\, Х2.

Первое базисное решение Х\ = (0; 0; 60; 34; 8) - допустимое. Соответствующее значение линейной функции = 0.

Переводим В основные переменные переменную XI, которая входит в выражение линейной функции с наибольшим поло­жительным коэффициентом. Находим максимально возможное значение переменной хі, которое “позволяет” принять система ограничений, из условия минимума соответствующих отноше­ний:

Хг = 1ШП|т;т;Т| = 8,

т.е. разрешающим (выделенным) является третье уравнение. При *2 = 8 в этом уравнении Х5 = 0, и в неосновные переходит пере­менная Х5.

II шаг. Основные переменные х2, х3, х*; неосновные пере­менные Хь Х5.

Введя дополнительную целочисленную переменную х6 > О, получим равносильное неравенству (8.6") уравнение

~1*5 + Хб = °" ^8"7 ^

Уравнение (8.7") необходимо включить в систему ограничений (8.5") исходной канонической задачи, после чего повторить про­цесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (8.7") в систему, полученную на последнем шаге решения задачи (без условия целочисленности).

IV шаг. Основные переменные Х), *2, хз> *б‘> неосновные пе­ременные *1, *2-

Х1 = з - 3*4 +

х3 = 18 + х4 +___ х5,

х6 - + ^х4 + з"х5-

Базисное решение Х4 = (у; 8; 18; 0; 0; -у) - недопусти­мое. (Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение).

Для получения допустимого базисного решения необходи­мо перевести в основные переменную, входящую с положи­тельным коэффициентом в уравнение, в котором свободней член отрицательный, т.е. *1 или х$ (на этом этапе линейную функцию не рассматриваем). Переводим в основные, напри­мер, переменную Х5.

V шаг. Основные переменные Х\, Х2, Х3, Х5; неосновные пере­менные Я], Х£

Получим после преобразований:

ЛГ| = 2 - х4 + 2х6,

*2 = 7 + 2х* ~ 2Х("

х3 = 19 + -х4 + -х6,

*5 = 1 - 2х* + 2Х6’

2 = 25-|х4--|х6.

^5 =(2; 7; 19; 0; 1;0);^ = 25.

Так как в выражении линейной функции нет основных пере­менных с положительными коэффициентами, то Х5 - оптималь­ное решение.

Итак, 2тах = 25 при оптимальном целочисленном решении X* - Х$ =(2; 7; 19; 0; 1; 0), т.е. максимальную производительность 25 т сортового зерна за смену можно получить приобретением 2 машин типа А и 7 машин типа В\ при этом незанятая площадь помещения составит 19 кв. м, остатки денежных средств из выде­ленных равны 0, в резерве для покупки - 1 машина типа В (шестая компонента содержательного смысла не имеет).

Замечание. Для геометрической интерпретации на плос­кости Ох\Хг (см. рис.8.2) отсечения (8.6") необходимо вхо­дящие в него переменные х4 и х$ выразить через перемен­ные XI и х2. Получим (см. 2-е и 3-е уравнения системы ог­раничений (8.5")):

у - у (34 - Зх, - 4х2) - у (8 - х2) £ 0 или х, + 2х2 £ 16.

(см. отсечение прямой (4) на рис 8.2)>

^ 8.2. Имеется достаточно большое количество бревен длиной 3 м. Бревна следует распилить на заготовки двух видов: длиной 1,2 м и длиной 0,9 м, причем заготовок каждого вида должно быть полу­чено не менее 50 шт. и 81 шт. соответственно. Каждое бревно можно распилить на указанные заготовки несколькими способа­ми: 1) на 2 заготовки по 1,2 м; 2) на 1 заготовку по 1,2 м и 2 заго­товки по 0,9 м; 3) на 3 заготовки по 0,9 м. Найти число бревен,

распиливаемых каждым способом, с тем чтобы заготовок любого вида было получено из наименьшего числа бревен.

Решение. Обозначим через х\, хі, хт, число бревен, распили­ваемых соответственно 1,"2-и 3-м способами. Из них можно полу­чить 2хі + *2 заготовок по 1,2 м и 2л\ + Зх2 заготовок по 0,9 м. Общее количество бревен обозначим I. Тогда математическая модель задачи примет вид:

I 2х, + х2 - х4 = 50, , не превосходящее данного.

Под дробной частью некоторого числа а понимается наименьшее неотрицательное число
такое, что разность между ним иа есть [a ] – целая часть числа).

Для выбранной базисной переменной с наибольшей дробной частью находим дробную часть
этой переменной и дробные части всех коэффициентов при переменныхi - й строки системы ограничений
(производящей строкой).

Обозначим
и
целые части чисел и . Величины дробных частей
и
(
) определяются следующим образом

Для этого по производящей строке симплексной таблицы выписывается уравнение, предполагая, что первые m переменных являются базисными для данного оптимального плана

или

Переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой:

Так как
<1, то заменяя в правой части
, получим строгое неравенство

Так как левая часть неравенства должна принимать целые значения, то, следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:

Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.

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

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

Решение . Выравнивая неравенства с помощью вспомогательных переменных х 3 , х 4 , получаем задачу линейного программирования в канонической форме:

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

В найденном оптимальном плане значение переменной х 2 равно дробному числу. Находим его дробную часть и дробные части всех элементов строки, содержащей переменную х 2 , а именно:

Теперь составляем для найденных значений дробных частей неравенство Гомори:

.

х 5 , переносим свободный член уравнения в правую часть и получаем новое ограничение:

.

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

Полученное оптимальное решение расширенной задачи содержит нецелое значение переменной х 1 , поэтому находим для этой строки дробные части всех нецелых чисел, а именно:

и новое неравенство Гомори имеет вид:

Выравниваем неравенство Гомори с помощью новой вспомогательной переменной х 6 , переносим свободный член уравнения в правую часть и получаем новое ограничение:
.

Добавляем его к решаемой задаче, выравниваем с помощью вспомогательной переменной и решаем расширенную задачу

Таким образом, найдено оптимальное решение задачи целочисленного программирования: Z max =11 при
.

Замечания :

Если в процессе решения в симплексной таблице появится уравнение с нецелой компонентой и целыми коэффициентами в соответствующей строке системы ограничений
, то данная задача не имеет целочисленного решения.

Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:

· оно должно быть линейным;

· должно отсекать найденный оптимальный нецелочисленный план;

· не должно отсекать ни одного целочисленного плана.

Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением .

Геометрически добавление каждого линейного ограничения отвечает проведению прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) решений некоторую его часть вместе с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полученное при этом многограннике оптимальное решение будет целочисленным (рис. 6.24).

Один из алгоритмов решения задачи линейного целочисленного программирования (6.59)…(6.62), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Рис. 6.18. Графическая иллюстрация целочисленного решения

Пусть задача линейного программирования (6.52)…(6.55) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие основные переменные через неосновные переменные оптимального решения

(6.56)

так, что оптимальным решением задачи (6.52)…(6.55) является , в котором, например β i − нецелая компонента. В этом случае можно доказать, что неравенство

сформированное по i -му уравнению системы (6.56), обладает всеми свойствами правильного отсечения.

В неравенстве (6.57) присутствует символ , означающий дробную часть числа. Число а называется конгруэнтным числу в (обозначается ) тогда и только тогда, когда разность а - в − целое число.

Целой частью числа а называется наибольшее целое число , не превосходящее а . Дробная часть числа определяется как разность между этим числом и его целой частью, т.е. . Например, для = 2, ; для = -3 и .

Для решения задачи целочисленного линейного программирования (6.52)…(6.55) методом Гомори используется следующий алгоритм:

1. Симплексным методом решить задачу (6.52)…(6.55) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (6.52)…(6.55). Если первая задача (6.52)…(6.54) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то вторая задача (6.52)…(6.55) также неразрешима.

2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (6.56) сформировать правильное отсечение (6.57).

3. Неравенство (6.57) введением дополнительной неотрицательной целочисленной переменной преобразовать в равносильное уравнение

и включить его в систему ограничений (6.53).

4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (6.52)…(6.55) решена. В противном случае вернуться к п. 2 алгоритма.

Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.

Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения.

Недостатком метода Гомори является требование целочисленности для всех переменных − как основных (выражающих, например, в задаче об использовании ресурсов единицы продукции), так и дополнительных переменных (выражающих величину неиспользованных ресурсов, которые могут быть и дробными).

Отметим, что переход к каноническому виду в полностью целочисленной задаче линейного программирования, содержащей ограничения − неравенства

не приводит, вообще говоря, к полностью целочисленной задаче в каноническом виде, так как в преобразованных ограничениях (6.59)

вспомогательные переменные x n + i не подчинены требованию целочисленности.

Однако если все коэффициенты a ij , b i в (6.59) − целые числа, то условие целочисленности можно распространить и на x n + i , как это сделано при решении примера 6.10.

Полностью целочисленную задачу в каноническом виде можно получить также, если в (6.59) a ij , b i − рациональные числа. Для этого следует умножить (6.59) на общее кратное знаменателей коэффициентов − a ij , b i (т.е. перейти к целым коэффициентам в (6.59)) и лишь после этого ввести вспомогательные переменные .

Пример 6.20. Решить задачу полностью целочисленного программирования

при ограничениях

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

Решаем задачу симплексным методом. Для наглядности решение иллюстрируем графически (рис. 6.19).

Рис. 6.19. Графическая иллюстрация решения задачи

На рис. 6.19 0KLM – область допустимых решений задачи ограниченная прямыми (1), (2), (3) и осями координат; L (2/3;8) – точка оптимального, но нецелочисленного решения задачи ; (4) – прямая, отсекающая это нецелочисленное решение; 0KNM – область допустимых решений расширенной задачи (6.64") N (2; 7) – точка оптимального целочисленного решения.

I шаг

Первое базисное решение Х 1 = (0;0;60;34;8) – допустимое. Соответствующее значение линейной функции f 1 = 0.

Переводим в основные переменные переменную х 2 , которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной х 2 , которое позволяет принять система ограничений, из условия минимума соответствующих отношений:

,

т.е. разрешающим (выделенным) является третье уравнение. При х 2 = 8 в этом уравнении х 5 = 0, и в неосновные переменные переходит х 5 .

II шаг . Основные переменные ; неосновные переменные .

Х 2 = (0;8;20;2;0); f = 24. Переводим в основные переменные х 1 , , а в неосновные х 4 .

Ш шаг . Основные переменные ; неосновные переменные . После преобразований получим:

Базисное решение Х 3 оптимально для задачи , так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами.

Однако решение Х 3 не удовлетворяет условию целочисленности (6.55"). По первому уравнению с переменной х 1 , получившей нецелочисленное значение в оптимальном решении (2/3), составляем дополнительное ограничение (6.57):

Обращаем внимание на то, что согласно (6.56) и (6.57) берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при неосновных переменных х 4 и х 5 − с противоположными знаками.

Так как дробные части

то последнее неравенство запишем в виде

Введя дополнительную целочисленную переменную х 6 ≥ 0, получим равносильное неравенству (6.57") уравнение

Уравнение (6.58) необходимо включить в систему ограничений (6.56") исходной канонической задачи, после чего повторить процесс решения задачи симплексным методом применительно к расширенной задаче. При этом для сокращения числа шагов (итераций) рекомендуется вводить дополнительное уравнение (6.58") в систему, полученную на последнем шаге решения задачи (без условия целочисленности).

IV шаг . Основные переменные ; неосновные переменные .

Базисное решение − недопустимое. Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение.

Для получения допустимого базисного решения необходимо перевести в основные переменную, входящую с положительным коэффициентом в уравнение, в котором свободный член отрицательный, т.е. х 4 или х 5 (на этом этапе линейную функцию не рассматриваем). Переводим в основные, например, переменную х 5 .

V шаг . Основные переменные ; неосновные переменные . Получим после преобразований:

Х 5 = (2;7;19;0;1;0); f 5 = 25.

Так как в выражении линейной функции нет основных переменных с положительными коэффициентами, то Х 5 − оптимальное решение.

Итак, f max = 25 при оптимальном целочисленном решении Шестая компонента содержательного смысла не имеет.

Для геометрической интерпретации на плоскости 0х 1 х 2 (см. рис. 6.19) отсечения (6.57") необходимо входящие в него переменные х 4 и х 5 выразить через переменные х 1 и х 2 . Получим (см. 2-е и 3-е уравнения системы ограничений (6.56"):

(см. отсечение прямой (4) на рис. 6.19).