ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 815
Скачиваний: 2
соответствующих переменных целевой функции задачи,
выраженной через свободные переменные её оптимального решения;
üМатрица коэффициентов свободных переменных симплекс-таблицы оптимального решения двойственной задачи (кроме строки целевой функции) получается путем
транспонирования матрицы коэффициентов свободных переменных симплекс-таблицы оптимального решения исходной задачи с противоположными знаками;
üКоэффициенты при свободных переменных в строке целевой функции в симплекс-таблице оптимального решения
двойственной задачи равны соответствующим свободным членам симплекс-таблицы оптимального решения исходной задачи (с противоположным знаком, если исходная задача является задачей максимизации).
В результате последняя симплекс-таблица оптимального решения двойственной задачи будет иметь вид:
Базисные |
|
Свободные |
|
|
Свободные переменные |
|
|
|
|||||||||||||||||
переменные |
|
|
члены |
y4 |
|
|
|
y1 |
y5 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y2 |
|
|
2 |
|
3 |
|
|
|
|
4 |
|
|
|
|
-1 |
|
|
1 |
|
|
|||||
|
11 |
|
|
11 |
|
|
11 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
y3 |
|
|
1 |
|
5 |
|
|
|
|
3 |
|
|
|
|
-1 |
− |
2 |
|
|||||||
|
11 |
|
|
|
11 |
|
|
11 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
F |
|
|
87 |
|
5 |
|
|
13 |
3 |
|
|
|
-23 |
7 |
9 |
|
|||||||||
|
11 |
|
|
11 |
|
||||||||||||||||||||
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|||||||||||
F |
|
= 87 |
5 |
при Y* = (0; 2 |
3 |
; 1 |
5 |
; 0; 0) . |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
min |
|
|
11 |
11 |
11 |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
8. Задача целочисленного линейного программирования
Задача линейного программирования, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного линейного программирования.
45
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
М а т ем а т и ч е с к а я м о д е л ь :
n
Z = å c j x j ® max(min) j=1
n
å aij x j = bi ,i = 1, m j=1
x j ³ 0, j = 1, n
x j - целые.
Для решения задач целочисленного линейного программирования используется ряд методов.
М ет о д ы о т с е ч е н и я .
Сущность методов отсечения состоит в том, что сначала задача решается без учета целочисленности. Если полученный оптимальный план целочисленный, то задача решена. В
противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
−Ограничение должно быть линейным;
−Ограничение должно исключать из ОДР найденный оптимальный нецелочисленный план;
−Ограничение не должно исключать из ОДР ни одно целочисленное решение.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением. Далее задача решается с учетом нового ограничения.
М ет о д Г о м о р и ( о т с е ч е н и я ) . Этапы:
1.Решить симплекс-методом задачу линейного программирования без учета целочисленности. Если оптимальное решение целое, то это решение исходной задачи. Если целевая функция не ограничена, или ограничения несовместны, то решение целочисленной задачи линейного программирования не существует.
2.Если среди компонент есть нецелые, то необходимо
выбрать компоненту с дробной частью и сформировать правильное отсечение- неравенство.
46
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Предположим, |
что |
{x1, x2,..., xm} |
- |
базисные |
переменные, {xm+1,..., xn} - свободные переменные. |
|
|||
Оптимальное |
решение |
(из последней |
|
симплекс- |
таблицы) имеет вид xi = βi -αim+1 × xm+1 - ... -αinxn ,i =1, m . В
результате оптимальное |
решение запишется в |
виде |
X* = {β1, β2,...,βm,0,...,0} - |
нецелочисленное решение |
( βi - |
нецелые).
Составляется неравенство правильного отсечения:
{βi}- {aim+1}xm+1 - ... - {ain}xn £ 0 , где { } - дробная часть числа1.
Правильное отсечение–неравенство преобразовать в
уравнение путем введения неотрицательной целочисленной переменной и ввести это уравнение в систему ограничений.
{βi}- {αim+1}× xm+1 - ... - {αin}xn + xn+1 = 0 |
|
xn+1 = -{βi} -{-αim+1}xm+1 - ... -{-xin}xn |
(1) |
Соотношение (1) добавляется в последнюю симплекс- таблицу как дополнительная строка. В результате симплекс- таблица представляет недопустимое решение.
4.Полученная расширенная задача снова решается симплекс–методом. Если вновь полученное оптимальное решение нецелочисленное, то итерации повторяются.
П р и з н а к н е с у щ е с т в о в а н и я о п т и м а л ь н о г о ц ел о ч и с л е н н о г о р е ш ен и я : Если в процессе решения появляется уравнение (выражающее базисную переменную через свободные) с нецелым свободным членом и целыми коэффициентами при свободных переменных, то исходная задача не имеет целочисленного оптимального решения.
1 Целой частью числа а называется наибольшее целое число [а], не превосходящее само число а. Дробной частью числа а называется число {а}, равное
разности между этим числом и его целой частью {а} = |
а - [а]. Пример: 1. a = 2 |
1 |
, |
|||||||||
3 |
||||||||||||
[a]= 2 , {a}= |
1 |
|
1 |
, [a]= −3 , {a}= −2 |
1 |
|
|
2 |
|
|
||
; 2. a = −2 |
− (−3) = |
|
. |
|
|
|||||||
3 |
3 |
3 |
3 |
|
|
|||||||
|
|
|
|
|
|
|
||||||
47
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
П р и м е р . Найти |
решение |
задачи целочисленного |
||
линейного программирования: |
|
|
|
|
Z = 6 × x1 |
+ x2 ® max |
|||
ì3× x1 - x2 ³ 9 |
||||
ï |
× x1 + 3× x2 |
£ 50 |
||
í2 |
||||
ï- x + 4 |
× x |
2 |
³ 18 |
|
î |
1 |
|
|
|
x1³ 0, x2 ³ 0
x1, x2 - целые
В результате решения данной задачи симплексным методом без условия целочисленности получили симплекс- таблицу, соответствующую оптимальному решению (см. Таб.3.)
и |
оптимальное |
|
|
решение |
Z max = 87 |
5 |
|
при |
||||||
|
||||||||||||||
|
|
3 |
|
|
9 |
|
|
|
|
11 |
|
|||
|
X* = (13 |
; 7 |
; 23; 0; 0) . |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|||||||
|
|
11 |
11 |
|
|
|
|
|
|
|
|
|||
|
Поскольку среди компонент оптимального решения есть |
|||||||||||||
нецелые |
(13 |
3 |
|
|
и |
7 |
9 |
), то для нахождения целочисленного |
||||||
11 |
|
|||||||||||||
|
|
|
|
|
11 |
|
|
|
|
|||||
оптимального решения среди нецелых компонент выбирается компонента с наибольшей дробной частью, и по соответствующей строке в симплекс-таблице формируется правильное отсечение.
Наибольшую дробную часть имеет 7119 , т.к.
ì |
3 ü |
= |
3 |
|
ì |
|
9 ü |
= |
9 |
. |
||||
í13 |
|
ý |
|
|
, |
í7 |
|
|
ý |
|
|
|||
|
11 |
|
11 |
|||||||||||
î |
11þ |
|
|
î |
11þ |
|
|
|||||||
Поэтому сформируем правильное отсечение - неравенство по строке, соответствующей этой компоненте.
ì |
|
9 ü |
ì |
1 ü |
× x4 |
ì |
|
2 ü |
× x5 |
|
|||
í7 |
|
|
ý |
- í |
|
ý |
- í- |
|
|
ý |
£ 0 |
||
|
|
|
|
||||||||||
î |
11þ |
î11þ |
|
î |
11þ |
|
|
||||||
Это неравенство введением дополнительной неотрицательной целочисленной переменной преобразуем в равносильное уравнение:
48
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
ì |
|
9 ü |
ì |
1 ü |
× x4 |
ì |
|
2 ü |
× x5 |
+ x6 |
|
|||
í7 |
|
|
ý |
- í |
|
ý |
- í- |
|
|
ý |
= 0 |
|||
|
|
|
|
|||||||||||
î |
11þ |
î11þ |
|
î |
11þ |
|
|
|
||||||
119 - 111 × x4 - 119 × x5 + x6 = 0
x6 = - 119 + 111 × x4 + 119 × x5
Полученное соотношение добавляем в симплекс- таблицу дополнительной строкой (свободный член вносим без изменения знака, а коэффициенты при свободных переменных - с противоположным знаком).
|
Базисные |
|
Свободные |
|
|
|
|
|
Свободные |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
переменные |
|
|
|
|
|||||||||||||||||||
|
переменные |
|
члены |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
x4 |
|
x5 |
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
13 |
|
3 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|||
|
11 |
|
|
11 |
|
|
|
|
11 |
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
x3 |
|
23 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
x2 |
|
7 |
|
9 |
|
|
|
|
|
|
1 |
|
|
|
|
|
- |
|
2 |
|
|
|
|
|
|
||||
|
11 |
|
|
|
11 |
|
|
|
|
11 |
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
x6 |
|
- |
|
9 |
|
|
|
|
- |
|
1 |
|
|
|
|
- |
|
9 |
|
|
|
|
|
|
|||||
|
11 |
|
|
11 |
|
|
|
11 |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
Z |
|
87 |
|
5 |
|
|
|
2 |
|
3 |
|
|
|
|
1 |
5 |
|
|
|
|
|
|
|||||||
|
11 |
|
11 |
|
|
|
|
11 |
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
Полученную расширенную задачу решаем симплекс- |
|||||||||||||||||||||||||||||
методом. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Базисное |
решение X = (13 |
3 |
|
; 7 |
9 |
; 23; 0; 0; - |
|
9 |
) - |
||||||||||||||||||||
|
11 |
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
11 |
|
||||||||||
недопустимое, т.к. имеется |
отрицательный |
|
|
|
|
|
|
элемент, |
||||||||||||||||||||||
ограничения совместны (в строке, имеющей отрицательный свободный член есть отрицательные элементы).
Столбец, соответствующий X 4 , принимаем в качестве
разрешающего. Для определения разрешающей строки найдем
минимальное положительное отношение свободных членов к
49
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com