- •2) Переход от общей (стандартной) формы злп к канонической.
- •Переход от канонической формы к стандартной.
- •1.1.3. Контрольные вопросы:
- •1.1.4. Варианты индивидуальных заданий:
- •1.2 Графический метод решения задач
- •1.2.2. Теоретическая часть:
- •1.2.3. Контрольные вопросы:
- •1.2.4. Варианты индивидуальных заданий:
- •1.3 Симплекс-метод решения задач линейного программиро-вания
- •1.3.2. Теоретическая часть
- •1.3.2.1. Симплекс-метод
- •1.3.2.2. Cимплекс-метод для неполного базиса (м-метод).
- •1.3.3. Контрольные вопросы:
- •1.3.4. Варианты индивидуальных занятий
- •1.4 Двойственность в линейном программировании
- •1.4.2. Теоретическая часть:
- •1.4.2.1. Общая модель задачи
- •1.4.2.2. Решение злп с помощью графического анализа двойственной задачи
- •1.4.3. Контрольные вопросы:
- •1.4.4. Варианты индивидуальных заданий.
- •1.5 Транспортная задача (т-задача)
- •1.5.2. Теоретическая часть:
- •1.5.2.1. Алгоритм решения т-задачи.
- •1.5.2. Примеры решения т-задачи.
- •1.5.3. Контрольные вопросы.
- •1.5.4. Варианты индивидуальных заданий:
- •1.6 Целочисленное программирование
- •1.6.2. Теоретическая часть: Описание метода отсечений (метода Гомори).
- •1.6.3. Контрольные вопросы:
- •1.6.4. Варианты индивидуальных заданий.
- •2.1.2.2. Метод Франка-Вулфа решения задач квадратичного программирова-
- •2.2 Контрольные вопросы.
- •2.3. Индивидуальные задания.
1.3.2.2. Cимплекс-метод для неполного базиса (м-метод).
Не всегда рассматриваемая ЗЛП имеет полный единичный базис, которому соот-ветствует начальное опорное решение. В решении таких задач прибегают к приему
введения искусственных переменных xn1 0,i 1, m. , создавая таким образом систему ограничений с полным базисом. Эти же искусственные переменные добавляются в ли-нейную функцию, умноженные на коэффициент (-М), где М – очень большое положи-тельное число (М>>0, М>>Сj). То есть по отношению к исходной задаче, записанной в канонической форме, составляется расширенная М-задача, которая решается, как обычно, с помощью табличного симплекс-метода.
-
оптимальном решении ЗЛП все искусственные переменные должны быть равны нулю, Если хотя бы одна из искусственных переменных в оптимальном решении М-задачи не равна нулю, то исходная задача недопустима. Если М-задача неразрешима, то
-
исходная неразрешима. Если на какой-то итерации получится базис без искусствен-ных векторов, то с этого момента решается не расширенная задача, а исходная.
Результаты вычислений оформляются в виде табл. 7.
Таблица 7
i |
базис |
Сi |
|
|
|
C1 |
C2 |
… |
Cn |
-M |
… |
-M |
Q(i) |
|
|
|
|
х1 |
х2 |
… |
xn |
xn+1 |
… |
xn+m |
|
||||
|
X 1 |
|
||||||||||||
|
|
|
(ai0) |
|
|
|
|
|
|
|
|
|
||
1 |
xn+1 |
-M |
a10 |
a11 |
a12 |
… |
a1n |
1 |
… |
0 |
Q1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 |
xn+2 |
-M |
a20 |
a21 |
a22 |
… |
a2n |
0 |
… |
0 |
Q2 |
|
||
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
||
l |
xn+l |
-M |
al0 |
al1 |
al2 |
… |
aln |
0 |
… |
0 |
Ql |
|
||
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
||
m |
xn+m |
-M |
am0 |
am1 |
am2 |
… |
amn |
0 |
… |
1 |
Qm |
|
||
m+1 |
Z j C j |
|
0 |
|
-c1 |
-c2 |
|
-cn |
0 |
… |
0 |
|
|
|
m+2 |
|
|
ai0 |
ai1 |
ai2 |
… |
ain |
0 |
… |
0 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23
Оценки векторов условий j=Zj-Cj (j=1,2,…,n) будут линейными функциями от М. Каждая из них состоит из двух независимых частей, одна из которых зависит от М, а другая нет, т.е. j j Mj . Поэтому симплекс-таблица имеет две строки, соответ-
ствующие линейной форме: (m+1)-я строка содержит коэффициент свободный от М, а (m+2)-я строка содержит коэффициент при М.
Обработка таблицы 7 производится аналогично (r+1)-й итерации обычной сим-плекс-таблицы.
Просматривается (m+2)-я строка, и вектор, вводимый в базис, определяется наи-меньшим отрицательным числом этой строки,
Критерием оптимальности плана по-прежнему является выполнение условия
-
j (rj c j ) 0, j (1, n) .
Пример: найти минимум функции Z 15x1 33x2 , при условии, что
3x1 2x2 6,
6x1 x2 6,
x j 0, j 1,2.
Приведем ЗЛП к канонической форме записи, добавив балансовые переменные с соответствующим знаком (минусом) и устремив ЦФ к максимуму, получим такую сис-тему:
Z '15x1 33x2 max,
3x1 2x2 x3 6,
6x1 x2 x4 6,
x j 0, j 1,4.
Переменные х3 и х4 не являются базисными, т.к. имеют знак (минус) , противопо-ложный знаку свободного члена (плюс), поэтому введем искусственные базисные неот-рицательные переменные х5 и х6. Эти же переменные вводим и в ЦФ по указанному выше правилу. Получаем новую, искусственно созданную задачу
Z"15x1 33x2 M (x5 x6 ) max,
3x1 2x2 x3 x5 6,
6x1 x2 x4 x6 6,
x j 0, j 1,6.
Приведем новую задачу к новой форме, для чего в ЦФ избавимся от базисных пе-ременных х5 и х6.
Z"15x1 33x2 M (6 3x1 2x2 x3 6 6x1 x2 x4 ) 15x1 33x2 M (12 9x1 3x2
-
x3 x4 ) x1 (15 9M ) x2 (33 3M ) x3 M x4 M 12M max
Для удобства перенесем все переменные в левую часть ЦФ и получим:
Z"x1 (15 9M ) x2 (33 3M ) x3 M x4 M 12M .
Теперь можно заполнять симплекс-таблицу (см. табл.8)
Таблица 8.
i |
Сi |
ба- |
-0 |
-15 |
-33 |
0 |
0 |
-M |
-M |
|
|
|||||||||
зис |
|
|
|
|
|
|
|
|
|
ai0 |
|
|||||||||
ai0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
aip |
|
|||||||
1 |
-M |
x5 |
6 |
3 |
|
2 |
-1 |
0 |
1 |
0 |
2 |
|
||||||||
2 |
-M |
x6 |
6 |
6 |
|
1 |
0 |
-1 |
0 |
1 |
1 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
m+1 |
|
Z” |
0 |
15 |
33 |
0 |
0 |
0 |
0 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
m+2 |
|
с М |
-12 |
-9 |
-3 |
1 |
1 |
0 |
0 |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Переменную, вводимую в базис определяем по наименьшей отрицательной оцен-ке (-9) в (m+2)-й строке таблицы. Разрешающий элемент определяется минимальным отношением свободных членов к соответствующим положительным элементам разре-шающего столбца (х1). Им оказался элемент а21=6. Проводим итерацию симплекс-метода (см. табл.9)
Таблица 9.
i |
Сi |
ба- |
-0 |
-15 |
-33 |
|
0 |
0 |
-M |
-M |
|
|
||||||||||
зис |
|
|
|
|
|
|
|
|
|
ai0 |
|
|||||||||||
ai0 |
x1 |
|
x2 |
x3 |
x4 |
x5 |
x6 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
aip |
|
|||||||||
1 |
-M |
x5 |
3 |
0 |
3 |
|
-1 |
1 |
1 |
1 |
2 |
|
||||||||||
|
|
|
|
|
|
2 |
|
|
2 |
|
2 |
|
|
|||||||||
2 |
-15 |
x1 |
1 |
1 |
1 6 |
|
0 |
1 6 |
0 |
1 6 |
6 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
m+1 |
|
Z” |
-5 |
0 |
61 |
|
0 |
15 |
0 |
5 |
|
|
||||||||||
|
|
|
|
|
2 |
|
|
6 |
|
2 |
|
|
||||||||||
m+2 |
|
с М |
-3 |
0 |
3 |
1 |
1 |
0 |
3 |
|
|
|||||||||||
|
|
|
|
|
2 |
|
2 |
|
2 |
|
|
Вводим в базис х2, соответствующую минимальной отрицательной оценке 32 .
Выполняя следующий шаг преобразований получаем таблицу 10.
Таблица 10.
i |
Сi |
ба- |
-0 |
-15 |
-33 |
0 |
0 |
|
-M |
-M |
|
|
|||||
зис |
|
|
|
|
|
|
|
|
|
ai0 |
|
||||||
ai0 |
x1 |
x2 |
x3 |
|
x4 |
x5 |
x6 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
aip |
|
||||
1 |
-33 |
x2 |
2 |
0 |
1 |
2 |
1 |
|
2 |
1 |
6 |
|
|||||
|
|
|
|
|
|
3 |
|
3 |
|
3 |
3 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
2 |
-15 |
x1 |
2 3 |
1 |
0 |
1 |
2 9 |
1 |
2 9 |
-- |
|
||||||
|
|
|
|
|
|
9 |
|
|
|
18 |
|
|
|
||||
m+1 |
|
Z” |
-76 |
0 |
0 |
61 |
23 |
61 |
46 |
|
|
||||||
|
|
|
|
|
|
3 |
3 |
3 |
6 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
m+2 |
|
с М |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Обратите внимание, что в таблице 10 все искусственные переменные выведены из базиса, значит исходная задача может иметь решение. В дальнейшие вычисления мы уже можем и не включать столбцы, соответствующие искусственным переменным. Во-дим в базис столбец x4, содержащий только один положительный элемент, который и будет разрешающим (см. табл.11).
Таблица 11.
i |
Сi |
ба- |
-0 |
-15 |
-33 |
0 |
0 |
|
|
зис |
|
|
|
|
|
ai0 |
|
||
ai0 |
x1 |
x2 |
x3 |
x4 |
|
||||
|
|
|
aip |
|
|||||
|
|
|
|
|
|
|
|
|
|
1 |
0 |
x4 |
6 |
0 |
3 |
1 |
1 |
|
|
|
|
|
|
|
|
2 |
|
|
|
2 |
-15 |
x1 |
2 |
1 |
2 |
5 |
0 |
|
|
|
|
|
|
|
3 |
9 |
|
|
|
m+1 |
|
Z” |
-30 |
0 |
23 |
5 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
m+2 |
|
с М |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Т.к. в таблице 11 в (m+2)-й строке все элементы неотрицательны и в (m+1)-й строке нет отрицательных элементов при нулевых элементах (m+2)-ой строки, то най-денный базис является оптимальным, т.е. хопт=(2; 0; 0; 6; 0; 0). Соответствующий опти-мальный план исходной задачи хопт=(2; 0), Zmin=30.