Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
РЕШЕНИЕ ТИПОВЫХ ЗАДАЧ №1,5,9, Лаба 11(1,2,5,6,9)
1. Вирішити цілочислову задачі лінійного програмування. Навести основні етапи алгоритму та обґрунтувати вибір методу.
max z=2x1+8x2
2x1+10x2<=19/3
x1+3x2<=10
x1,x2>=0 - цілі
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Помножим левую часть первого неравенства на (3), получим:
6x1+3x2<=19
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,.
При ограничениях
Таблица 1.1.1
|
2 |
8 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
6 |
3 |
1 |
0 |
19 |
0 |
19/3 |
|
|
S2 |
1 |
3 |
0 |
1 |
10 |
0 |
10/3 |
|
|
z |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
2 |
8 |
|||||
|
S1 |
5 |
0 |
1 |
-1 |
9 |
0 |
||
|
X2 |
1/3 |
1 |
0 |
1/3 |
10/3 |
8 |
||
|
z |
8/3 |
8 |
0 |
8/3 |
80/3 |
|||
|
1 |
c-z |
-2/3 |
0 |
0 |
-8/3 |
-80/3 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 1.1.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
S1 |
5 |
0 |
1 |
-1 |
9 |
0 |
|
|
X2 |
1/3 |
1 |
0 |
1/3 |
10/3 |
8 |
|
|
z |
8/3 |
8 |
0 |
8/3 |
80/3 |
||
|
1 |
c-z |
-2/3 |
0 |
0 |
-8/3 |
-80/3 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 8/3x1+8х2+8/3S2=80/3,
х2 – уравнение: 1/3х1+х2+1/3S2=10/3,
S1 – уравнение: 5х1+S1-S2=9.
Так как в этом примере х2 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
1/3х1+х2+1/3S2=10/3 (производящая х2-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х2-строки приводит к следующему уравнению.
(0+1/3)х1 + х2 + (0+1/3)S2=3 + 1/3
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
х2 -3 = 1/3 -1/3х1 – 1/3S2
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения. Перепишем ее следующим образом.
1/3 -1/3х1 – 1/3S2=1/3 –(1/3х1 + 1/3S2)
Поскольку х1,S2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/3 –(1/3х1 + 1/3S2), будучи целочисленной, не может превышать 1/3. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/3 –(1/3х1 + 1/3S2)≤0
Это и есть дробное отсечение, порожденное х2-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение x1=0; x2=10/3; S1=3; S2=0 не удовлетворяет отсечению (1/3≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х2- строкой записываем следующим образом.
– 1/3х1 - 1/3S2 + S3 = - 1/3
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 1.1.3
|
2 |
8 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
S1 |
5 |
0 |
1 |
-1 |
9 |
0 |
0 |
|
x2 |
1/3 |
1 |
0 |
1/3 |
10/3 |
8 |
8 |
|
S3 |
-1/3 |
0 |
0 |
-1/3 |
1 |
-1/3 |
0 |
|
z |
8/3 |
8 |
0 |
8/3 |
80/3 |
||
|
c-z |
-2/3 |
0 |
0 |
-8/3 |
-80/3 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 1.1.4
|
2 |
8 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
S1 |
5 |
0 |
1 |
-1 |
9 |
0 |
0 |
|
x2 |
1/3 |
1 |
0 |
1/3 |
10/3 |
8 |
8 |
|
S3 |
-1/3 |
0 |
0 |
-1/3 |
1 |
-1/3 |
0 |
|
z |
8/3 |
8 |
0 |
8/3 |
80/3 |
||
|
c-z |
-2/3 |
0 |
0 |
-8/3 |
-80/3 |
||
|
S1 |
0 |
0 |
1 |
-6 |
15 |
4 |
0 |
|
х2 |
0 |
1 |
0 |
0 |
1 |
3 |
8 |
|
Х1 |
1 |
0 |
0 |
1 |
-3 |
1 |
2 |
|
z |
2 |
8 |
0 |
2 |
2 |
26 |
|
|
c-z |
0 |
0 |
0 |
-2 |
-2 |
Оптимальное решение x1=1; x2=3; S1=4; S2=0; S3=0 Zmax=26 является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
9. Дана задача:
max z=2x1+4x2
при 2х1+х2<=19/3
xl+3x2<=10
xl, x2>=0 - цілі
Порівняти та проаналізувати результати, оптимальні при розв’язанні задачі методом Гоморі та графічним методом.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Помножим левую часть первого неравенства на (3), получим:
6x1+3x2<=19
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,.
При ограничениях
Таблица 1.9.1
|
2 |
4 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
6 |
3 |
1 |
0 |
19 |
0 |
19/3 |
|
|
S2 |
1 |
3 |
0 |
1 |
10 |
0 |
10/3 |
|
|
z |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
2 |
4 |
|||||
|
S1 |
5 |
0 |
1 |
-1 |
9 |
0 |
||
|
X2 |
1/3 |
1 |
0 |
1/3 |
10/3 |
4 |
||
|
z |
4/3 |
4 |
0 |
4/3 |
40/3 |
|||
|
1 |
c-z |
2/3 |
0 |
0 |
-4/3 |
|||
|
Х1 |
1 |
0 |
1/5 |
-1/5 |
9/5 |
2 |
||
|
X2 |
0 |
1 |
-1/15 |
2/5 |
41/15 |
4 |
||
|
z |
2 |
4 |
2/15 |
6/5 |
218/15 |
|||
|
2 |
c-z |
0 |
0 |
-2/15 |
-6/5 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 1.9.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
Х1 |
1 |
0 |
1/5 |
-1/5 |
9/5 |
2 |
|
|
X2 |
0 |
1 |
-1/15 |
2/5 |
41/15 |
4 |
|
|
z |
2 |
4 |
2/15 |
6/5 |
218/15 |
||
|
2 |
c-z |
0 |
0 |
-2/15 |
-6/5 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 2x1+4х2+2/15S1+6/5S2=218/15,
х2 – уравнение: х2-1/15S1+2/5S2=41/15,
X1 – уравнение: х1+1/5S1-1/5S2=9/5.
Разложение коэф.Х1-строки приводит к след.уравнению:
х1+(0+1/5)S1-(0+1/5)S2=(1+4/5)
Разложение коэф.Х2-строки приводит к след.уравнению:
х2+(-1+14/15)S1+(0+2/5)S2=(2+11/15)
В качестве производящей строки можно выбрать любую из строк таблицы, содержащих нецелевые компоненты решения. Обычно используется эмпирическое правило:
Если нецелочисленных переменных несколько, то лучше выбрать ту, у которой больше дробная часть. В нашем случае - Х1-строка.
Так как в этом примере х1 имеет наибольшее дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
х1+1/5S1-1/5S2=9/5 (производящая х1-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х1-строки приводит к следующему уравнению.
х1 +1/5S1+ (-1+4/5)S2=1 + 4/5
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
Х1-S2 -1 = -1/5S1 -4/5S2 +4/5
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения. Перепишем ее следующим образом.
-1/5S1 -4/5S2 +4/5=4/5-(1/5S1+4/5S2)
Поскольку S1,S2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 4/5-(1/5S1+4/5S2), будучи целочисленной, не может превышать 4/5. Следовательно, необходимое условие целочисленности можно записать следующим образом.
4/5-(1/5S1+4/5S2)≤0
Это и есть дробное отсечение, порожденное х1-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение x1=9/5; x2=41/15; S1=0; S2=0 не удовлетворяет отсечению (4/5≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х1- строкой записываем следующим образом.
-1/5S1 -4/5S2 + S3 = - 4/5
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 1.9.3
|
2 |
4 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
X1 |
1 |
0 |
1/5 |
-1/5 |
0 |
9/5 |
2 |
|
x2 |
0 |
1 |
-1/15 |
2/5 |
0 |
41/15 |
4 |
|
S3 |
0 |
0 |
-1/5 |
-4/5 |
1 |
-4/5 |
0 |
|
z |
2 |
4 |
2/15 |
6/5 |
218/15 |
||
|
c-z |
0 |
0 |
-2/15 |
-6/5 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 1.9.4
|
2 |
8 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
x1 |
1 |
0 |
1/5 |
-1/5 |
0 |
9/5 |
2 |
|
x2 |
0 |
1 |
-1/15 |
2/5 |
0 |
41/15 |
4 |
|
S3 |
0 |
0 |
-1/5 |
-4/5 |
1 |
-4/5 |
0 |
|
z |
2 |
4 |
2/15 |
6/5 |
218/15 |
||
|
c-z |
0 |
0 |
-2/15 |
-6/5 |
|||
|
x1 |
1 |
0 |
0 |
-1 |
1 |
1 |
2 |
|
х2 |
0 |
1 |
0 |
2/3 |
-1/3 |
3 |
4 |
|
S1 |
0 |
0 |
1 |
4 |
-5 |
4 |
0 |
|
z |
2 |
4 |
0 |
2/3 |
2/3 |
14 |
|
|
c-z |
0 |
0 |
0 |
-2/3 |
-2/3 |
Оптимальное решение x1=1; x2=3; S1=4; S2=0; S3=0 Zmax=14 является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
2. График:
Лаба 11
1.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,.
При ограничениях
Таблица 11.1.1
|
5 |
10 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
3 |
4 |
1 |
0 |
14 |
0 |
14/4 |
|
|
S2 |
2 |
3 |
0 |
1 |
10 |
0 |
||
|
z |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
5 |
10 |
0 |
0 |
|||
|
S1 |
1/3 |
0 |
1 |
-4/3 |
2/3 |
0 |
||
|
X2 |
2/3 |
1 |
0 |
1/3 |
10/3 |
10 |
||
|
z |
20/3 |
10 |
0 |
10/3 |
100/3 |
|||
|
1 |
c-z |
-5/3 |
0 |
0 |
-10/3 |
0 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 11.1.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
S1 |
1/3 |
0 |
1 |
-4/3 |
2/3 |
0 |
|
|
X2 |
2/3 |
1 |
0 |
1/3 |
10/3 |
10 |
|
|
z |
20/3 |
10 |
0 |
10/3 |
100/3 |
||
|
1 |
c-z |
-5/3 |
0 |
0 |
-10/3 |
0 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 20/3x1+10x2+10/3S2=100/3,
х2 – уравнение: 2/3х1+х2+1/3S2=10/3,
S1 – уравнение: 1/3S1-4/3S2=2/3.
Так как в этом примере х2 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
2/3х1+х2+1/3S2=10/3 (производящая х2-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х2-строки приводит к следующему уравнению.
(0+2/3)х1 + х2 + (0+1/3)S2=3 + 1/3
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
х2 -3 = 1/3 -2/3х1 – 1/3S2
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения. Перепишем ее следующим образом.
1/3 -2/3х1 – 1/3S2=1/3 –(2/3х1 + 1/3S2)
Поскольку х1,S2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/3 –(2/3х1 + 1/3S2), будучи целочисленной, не может превышать 1/3. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/3 –(2/3х1 + 1/3S2)≤0
Это и есть дробное отсечение, порожденное х2-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение x1=0; x2=10/3; S1=2/3; S2=0 не удовлетворяет отсечению (1/3≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х2- строкой записываем следующим образом.
– 2/3х1 - 1/3S2 + S3 = - 1/3
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 11.1.3
|
5 |
10 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
S1 |
1/3 |
0 |
1 |
-4/3 |
0 |
2/3 |
0 |
|
x2 |
2/3 |
1 |
0 |
1/3 |
0 |
10/3 |
10 |
|
S3 |
-2/3 |
0 |
0 |
-1/3 |
1 |
||
|
z |
20/3 |
10 |
0 |
10/3 |
100/3 |
||
|
c-z |
-5/3 |
0 |
0 |
-10/3 |
0 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.1.4
|
2 |
8 |
0 |
0 |
0 |
|||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|
|
S1 |
1/3 |
0 |
1 |
-4/3 |
0 |
2/3 |
0 |
|
x2 |
2/3 |
1 |
0 |
1/3 |
0 |
10/3 |
10 |
|
S3 |
-2/3 |
0 |
0 |
-1/3 |
1 |
||
|
z |
20/3 |
10 |
0 |
10/3 |
100/3 |
||
|
c-z |
-5/3 |
0 |
0 |
-10/3 |
0 |
||
|
S1 |
0 |
0 |
1 |
-3/2 |
1/2 |
1/2 |
0 |
|
х2 |
0 |
1 |
0 |
0 |
1 |
3 |
10 |
|
Х1 |
1 |
0 |
0 |
1/2 |
-3/2 |
1/2 |
5 |
|
z |
5 |
10 |
0 |
5/2 |
5/2 |
65/2 |
|
|
c-z |
0 |
0 |
0 |
-5/2 |
-5/2 |
Оптимальное решение x1=1/2; x2=3; S1=1/2; S2=0; S3=0 Zmax=65/2 является частично целочисленным. Значение переменной Х1 пока еще нецелочисленное. Так как в этом примере х1 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
х1+1/2S2-3/2S3=1/2 (производящая х1-строка)
Разложение коэффициентов х1-строки приводит к следующему уравнению.
х1 + 1/2S2 + (-2+1/2)S3=1/2
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
Х1 -2S3 = 1/2 -1/2S2– 1/2S3
Необходимое условие целочисленности можно записать следующим образом.
1/2 –(1/2S2 + 1/2S3)≤0
Это и есть дробное отсечение, порожденное х1-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение x1=1/2; x2=3; S1=1/2; S2=0; S3=0 не удовлетворяет отсечению (1/2≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х1- строкой записываем следующим образом.
– 1/2S2 - 1/2S3 + S4 = - 1/2
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.1.5
|
2 |
8 |
0 |
0 |
0 |
||||
|
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
b |
c |
|
|
S1 |
0 |
0 |
1 |
-3/2 |
1/2 |
0 |
1/2 |
0 |
|
x2 |
0 |
1 |
0 |
0 |
1 |
0 |
3 |
10 |
|
S3 |
1 |
0 |
0 |
1/2 |
-3/2 |
0 |
1/2 |
5 |
|
S4 |
0 |
0 |
0 |
-1/2 |
-1/2 |
1 |
-1/2 |
0 |
|
z |
5 |
10 |
0 |
5/2 |
5/2 |
0 |
65/2 |
|
|
c-z |
0 |
0 |
0 |
-5/2 |
-5/2 |
0 |
||
|
S1 |
0 |
0 |
1 |
0 |
2 |
-3 |
2 |
0 |
|
х2 |
0 |
1 |
0 |
0 |
1 |
0 |
3 |
10 |
|
Х1 |
1 |
0 |
0 |
0 |
-2 |
1 |
0 |
5 |
|
S2 |
0 |
0 |
0 |
1 |
1 |
-2 |
1 |
0 |
|
z |
5 |
10 |
0 |
0 |
0 |
5 |
30 |
|
|
c-z |
0 |
0 |
0 |
0 |
0 |
-5 |
Оптимальное решение x1=0; x2=3; S1=2; S2=1; S3=0; S4=0 Zmax=30 является целочисленным.
То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
При решении задачи на первой итерации в качестве вводимой переменной, использовалась переменная S2.
Решим данную задачу двойственным симплекс-методом, вводя в базис переменную S3.
Таблица 11.1.5
|
2 |
8 |
0 |
0 |
0 |
||||
|
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
b |
c |
|
|
S1 |
0 |
0 |
1 |
-3/2 |
1/2 |
0 |
1/2 |
0 |
|
x2 |
0 |
1 |
0 |
0 |
1 |
0 |
3 |
10 |
|
S3 |
1 |
0 |
0 |
1/2 |
-3/2 |
0 |
1/2 |
5 |
|
S4 |
0 |
0 |
0 |
-1/2 |
-1/2 |
1 |
-1/2 |
0 |
|
z |
5 |
10 |
0 |
5/2 |
5/2 |
0 |
65/2 |
|
|
c-z |
0 |
0 |
0 |
-5/2 |
-5/2 |
0 |
||
|
S1 |
0 |
0 |
1 |
-2 |
0 |
1 |
0 |
0 |
|
х2 |
0 |
1 |
0 |
-1 |
0 |
2 |
2 |
10 |
|
Х1 |
1 |
0 |
0 |
2 |
0 |
2 |
2 |
5 |
|
S3 |
0 |
0 |
0 |
1 |
1 |
-2 |
1 |
0 |
|
z |
5 |
10 |
0 |
0 |
0 |
30 |
30 |
|
|
c-z |
0 |
0 |
0 |
0 |
0 |
-30 |
Оптимальное решение x1=2 x2=2 S1=0 S2=0 S3=1 S4=0 Zmax=30 является целочисленным.
Таким образом, можно сказать, что данная задача имеет параллельное решение.
ГРАФИК:
2.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,, .
При ограничениях
Таблица 11.2.1
|
10 |
12 |
0 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
|||
|
S1 |
5 |
4 |
1 |
0 |
0 |
13 |
0 |
13/4 |
|
|
S2 |
2 |
-1 |
0 |
1 |
0 |
5 |
0 |
- |
|
|
S3 |
4 |
1 |
0 |
0 |
1 |
10 |
0 |
10 |
|
|
z |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
10 |
12 |
0 |
0 |
0 |
|||
|
X2 |
5/4 |
1 |
1/4 |
0 |
0 |
13/4 |
12 |
||
|
S2 |
13/4 |
0 |
1/4 |
1 |
0 |
33/4 |
0 |
||
|
S3 |
11/4 |
0 |
-1/4 |
0 |
1 |
27/4 |
0 |
||
|
z |
15 |
12 |
3 |
0 |
0 |
39 |
|||
|
1 |
c-z |
-5 |
0 |
-3 |
0 |
0 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 11.2.2
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
X2 |
5/4 |
1 |
1/4 |
0 |
0 |
13/4 |
12 |
|
|
S2 |
13/4 |
0 |
1/4 |
1 |
0 |
33/4 |
0 |
|
|
S3 |
11/4 |
0 |
-1/4 |
0 |
1 |
27/4 |
0 |
|
|
z |
15 |
12 |
3 |
0 |
0 |
39 |
||
|
1 |
c-z |
-5 |
0 |
-3 |
0 |
0 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 15x1+12x2+3S1=39,
х2 – уравнение: 5/4х1+х2+1/4S1=13/4,
Так как в этом примере х2 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
5/4х1+х2+1/4S1=13/4 (производящая х2-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х2-строки приводит к следующему уравнению.
(1+1/4)х1 + х2 + (0+1/4)S1=3 + 1/4
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
х2 +x1-3 = 1/4 -1/4х1 – 1/4S1
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения. Перепишем ее следующим образом.
1/4 -1/4х1 – 1/4S1=1/4 –(1/4х1 + 1/4S1)
Поскольку х1,S1 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/4 –(1/4х1 + 1/4S1), будучи целочисленной, не может превышать 1/4. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/4 –(1/4х1 + 1/4S1)≤0
Это и есть дробное отсечение, порожденное х2-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение не удовлетворяет отсечению (1/4≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х2- строкой записываем следующим образом.
– 1/4х1 - 1/4S1 + S4 = - 1/4
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 11.2.3
|
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
b |
c |
||
|
X2 |
5/4 |
1 |
1/4 |
0 |
0 |
0 |
13/4 |
12 |
|
|
S2 |
13/4 |
0 |
1/4 |
1 |
0 |
0 |
33/4 |
0 |
|
|
S3 |
11/4 |
0 |
-1/4 |
0 |
1 |
0 |
27/4 |
0 |
|
|
S4 |
-1/4 |
0 |
-1/4 |
0 |
0 |
1 |
-1/4 |
0 |
|
|
z |
15 |
12 |
3 |
0 |
0 |
0 |
39 |
||
|
1 |
c-z |
-5 |
0 |
-3 |
0 |
0 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.2.4
|
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
b |
c |
||
|
X2 |
5/4 |
1 |
1/4 |
0 |
0 |
0 |
13/4 |
12 |
|
|
S2 |
13/4 |
0 |
1/4 |
1 |
0 |
0 |
33/4 |
0 |
|
|
S3 |
11/4 |
0 |
-1/4 |
0 |
1 |
0 |
27/4 |
0 |
|
|
S4 |
-1/4 |
0 |
-1/4 |
0 |
0 |
1 |
-1/4 |
0 |
|
|
z |
15 |
12 |
3 |
0 |
0 |
0 |
39 |
||
|
1 |
c-z |
-5 |
0 |
-3 |
0 |
0 |
|||
|
X2 |
1 |
1 |
0 |
0 |
0 |
1 |
3 |
12 |
|
|
S2 |
3 |
0 |
0 |
1 |
0 |
1 |
8 |
0 |
|
|
S3 |
3 |
0 |
0 |
0 |
1 |
-1 |
7 |
0 |
|
|
S1 |
1 |
0 |
1 |
0 |
0 |
-4 |
1 |
0 |
|
|
z |
12 |
12 |
0 |
0 |
0 |
12 |
36 |
||
|
2 |
c-z |
-2 |
0 |
0 |
0 |
0 |
-12 |
Оптимальное решение x1=0; x2=3; S1=1; S2=8; S3=7; S4=0 Zmax=36 является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
2. График:
5.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,.
При ограничениях
Таблица 11.5.1
|
10 |
12 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
4 |
-7 |
1 |
0 |
10 |
0 |
- |
|
|
S2 |
6 |
3 |
0 |
1 |
16 |
0 |
16/3 |
|
|
z |
0 |
0 |
0 |
0 |
||||
|
0 |
c-z |
10 |
12 |
0 |
0 |
|||
|
S1 |
18 |
0 |
1 |
7/3 |
142/3 |
0 |
||
|
X2 |
2 |
1 |
0 |
1/3 |
16/3 |
12 |
||
|
z |
24 |
12 |
0 |
4 |
64 |
|||
|
1 |
c-z |
-14 |
0 |
0 |
-4 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 11.5.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
S1 |
18 |
0 |
1 |
7/3 |
142/3 |
0 |
|
|
X2 |
2 |
1 |
0 |
1/3 |
16/3 |
12 |
|
|
z |
24 |
12 |
0 |
4 |
64 |
||
|
1 |
c-z |
-14 |
0 |
0 |
-4 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 24x1+12x2+4S2=64,
х2 – уравнение: 2х1+х2+1/3S2=16/3,
Так как в этом примере х2 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
2х1+х2+1/3S2=16/3, (производящая х2-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х2-строки приводит к следующему уравнению.
2х1 + х2 + (0+1/3)S2=5 + 1/3
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
х2 +2x1-5 = 1/3 – 1/3S2
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения.
Поскольку S2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/3 – 1/3S2, будучи целочисленной, не может превышать 1/3. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/3 – 1/3S2≤0
Это и есть дробное отсечение, порожденное х2-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение не удовлетворяет отсечению (1/3≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х2- строкой записываем следующим образом.
- 1/3S2 + S3 = - 1/3
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 11.5.3
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
S1 |
18 |
0 |
1 |
7/3 |
0 |
142/3 |
0 |
|
|
X2 |
2 |
1 |
0 |
1/3 |
0 |
16/3 |
12 |
|
|
S3 |
0 |
0 |
0 |
-1/3 |
1 |
-1/3 |
||
|
z |
24 |
12 |
0 |
4 |
0 |
64 |
||
|
1 |
c-z |
-14 |
0 |
0 |
-4 |
0 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.5.4
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
S1 |
18 |
0 |
1 |
7/3 |
0 |
122/3 |
0 |
|
|
X2 |
2 |
1 |
0 |
1/3 |
0 |
16/3 |
12 |
|
|
S3 |
0 |
0 |
0 |
-1/3 |
1 |
-1/3 |
||
|
z |
24 |
12 |
0 |
4 |
0 |
64 |
||
|
1 |
c-z |
-14 |
0 |
0 |
-4 |
0 |
||
|
S1 |
18 |
0 |
1 |
0 |
7 |
45 |
0 |
|
|
X2 |
2 |
1 |
0 |
0 |
1 |
5 |
12 |
|
|
S2 |
0 |
0 |
0 |
1 |
-3 |
1 |
0 |
|
|
z |
24 |
12 |
0 |
0 |
12 |
60 |
||
|
2 |
c-z |
-14 |
0 |
0 |
0 |
-12 |
Оптимальное решение x1=0; x2=5; S1=45; S2=1; S3=0; Zmax=60 является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
2. График:
6.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,, .
При ограничениях
Таблица 11.6.1
|
10 |
4 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
3 |
-4 |
1 |
0 |
12 |
0 |
4 |
|
|
S2 |
3 |
2 |
0 |
1 |
10 |
0 |
10/3 |
|
|
z |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
10 |
4 |
0 |
0 |
|||
|
S1 |
0 |
-6 |
1 |
-1 |
2 |
0 |
||
|
X1 |
1 |
2/3 |
0 |
1/3 |
10/3 |
10 |
||
|
z |
0 |
20/3 |
0 |
10/3 |
100/3 |
|||
|
1 |
c-z |
0 |
-8/3 |
0 |
-10/3 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 11.6.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
S1 |
0 |
-6 |
1 |
-1 |
2 |
0 |
|
|
X1 |
1 |
2/3 |
0 |
1/3 |
10/3 |
10 |
|
|
z |
0 |
20/3 |
0 |
10/3 |
100/3 |
||
|
1 |
c-z |
0 |
-8/3 |
0 |
-10/3 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+20/3x2+10/3S2=100/3,
х1 – уравнение: х1+2/3х2+1/3S2=10/3,
Так как в этом примере х1 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
х1+2/3х2+1/3S2=10/3 (производящая х1-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х1-строки приводит к следующему уравнению.
(1+0)х1 +(0+2/3) х2 + (0+1/3)S2=3 + 1/3
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
x1-3 = 1/3 -2/3х2 – 1/3S2
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения. Перепишем ее следующим образом.
1/3 -2/3х2 – 1/3S2=1/3 –(2/3х2 + 1/3S2)
Поскольку х2,S2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/3 –(2/3х2 + 1/3S2), будучи целочисленной, не может превышать 1/3. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/3 –(2/3х2 + 1/3S2))≤0
Это и есть дробное отсечение, порожденное х1-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение не удовлетворяет отсечению (1/3≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х1- строкой записываем следующим образом.
– 2/3х2 - 1/3S2 + S3 = - 1/3
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 11.6.3
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
S1 |
0 |
-6 |
1 |
-1 |
0 |
2 |
0 |
|
|
X1 |
1 |
2/3 |
0 |
1/3 |
0 |
10/3 |
10 |
|
|
S3 |
0 |
-2/3 |
0 |
-1/3 |
1 |
-1/3 |
0 |
|
|
z |
10 |
20/3 |
0 |
10/3 |
0 |
100/3 |
||
|
1 |
c-z |
0 |
-8/3 |
0 |
-10/3 |
0 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.6.4
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
S1 |
0 |
-6 |
1 |
-1 |
0 |
2 |
0 |
|
|
X1 |
1 |
2/3 |
0 |
1/3 |
0 |
10/3 |
10 |
|
|
S3 |
0 |
-2/3 |
0 |
-1/3 |
1 |
-1/3 |
0 |
|
|
z |
10 |
20/3 |
0 |
10/3 |
0 |
100/3 |
||
|
1 |
c-z |
0 |
-8/3 |
0 |
-10/3 |
0 |
||
|
S1 |
0 |
0 |
1 |
2 |
-9 |
5 |
0 |
|
|
X1 |
1 |
0 |
0 |
0 |
1 |
3 |
10 |
|
|
X2 |
0 |
1 |
0 |
1/3 |
-3/2 |
1/2 |
4 |
|
|
z |
10 |
4 |
0 |
2 |
4 |
32 |
||
|
2 |
c-z |
0 |
0 |
0 |
-2 |
-4 |
32 |
Оптимальное решение x1=3; x2=1/2; S1=5; S2=0; S3=0; Zmax=32 является частично целочисленным. Значение переменной Х2 пока еще нецелочисленное. Так как в этом примере х2 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
Х2+1/2S2-3/2S3=1/2 (производящая х2-строка)
Разложение коэффициентов х2-строки приводит к следующему уравнению.
Х2 + 1/2S2 + (-2+1/2)S3=1/2
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
Х2 -2S3 = 1/2 -1/2S2– 1/2S3
Необходимое условие целочисленности можно записать следующим образом.
1/2 –(1/2S2 + 1/2S3)≤0
Это и есть дробное отсечение, порожденное х2-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение x1=3; x2=1/2; S1=5; S2=0; S3=0 не удовлетворяет отсечению (1/2≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х2- строкой записываем следующим образом.
– 1/2S2 - 1/2S3 + S4 = - 1/2
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.6.5
|
10 |
4 |
0 |
0 |
0 |
||||
|
x1 |
x2 |
S1 |
S2 |
S3 |
S4 |
b |
c |
|
|
S1 |
0 |
0 |
1 |
2 |
-9 |
0 |
5 |
0 |
|
X1 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
10 |
|
Х2 |
0 |
1 |
0 |
1/2 |
-3/2 |
0 |
1/2 |
4 |
|
S4 |
0 |
0 |
0 |
-1/2 |
-1/2 |
1 |
-1/2 |
0 |
|
z |
10 |
4 |
0 |
2 |
4 |
0 |
32 |
|
|
c-z |
0 |
0 |
0 |
-2 |
-4 |
0 |
||
|
S1 |
0 |
0 |
1 |
0 |
-11 |
4 |
3 |
0 |
|
Х1 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
10 |
|
Х2 |
0 |
1 |
0 |
0 |
-2 |
1 |
0 |
4 |
|
S2 |
0 |
0 |
0 |
1 |
1 |
-2 |
1 |
0 |
|
z |
10 |
4 |
0 |
0 |
2 |
4 |
30 |
|
|
c-z |
0 |
0 |
0 |
0 |
-2 |
-4 |
Оптимальное решение x1=3; x2=0; S1=3; S2=1; S3=0; S4=0 Zmax=30 является целочисленным.
То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
ГРАФИК:
9.
РЕШЕНИЕ
1. Данная задача относится к задачам ЗЦЛП, поэтому решать ее будем с помощью метода отсекающих плоскостей (дробный алгоритм).
Метод отсекающих плоскостей начинает работу с решения непрерывной задачи линейного программирования.
Линейную задачу решаем прямым симплекс-методом.
Приведем нашу задачу к канонической форме:
1) Все ограничения записываются в виде равенств с неотрица тельной правой частью;
2) значения всех переменных модели неотрицательны;
3) целевая функция подлежит максимизации или минимизации.
К первому и второму ограничению прибавим остаточные переменные ,.
При ограничениях
Таблица 11.9.1
|
10 |
7 |
0 |
0 |
|||||
|
x1 |
x2 |
S1 |
S2 |
b |
c |
|||
|
S1 |
6 |
7 |
1 |
0 |
8 |
0 |
4/3 |
|
|
S2 |
3 |
1 |
0 |
1 |
10 |
0 |
10/3 |
|
|
z |
0 |
0 |
0 |
0 |
0 |
|||
|
0 |
c-z |
10 |
7 |
0 |
0 |
0 |
||
|
Х1 |
1 |
7/6 |
1/6 |
0 |
4/3 |
10 |
||
|
S2 |
0 |
-5/2 |
-1/2 |
1 |
6 |
0 |
||
|
z |
10 |
70/6 |
10/6 |
0 |
40/3 |
|||
|
1 |
c-z |
0 |
-14/3 |
-10/6 |
0 |
40/3 |
Поскольку, , то оптимальное решение найдено:
В симплекс-таблице, соответствующей оптимальному решению задачи линейного программирования, следует выбрать одну из строк (называемую производящей), для которой базисная переменная нецелочисленная. Искомое отсечение строится на основании дробных составляющих коэффициентов производящей строки. По этой причине его называют дробным отсечением. Построим дробное отсечение для нашей задачи.
Таблица 11.9.2
|
x1 |
x2 |
S1 |
S2 |
b |
c |
||
|
Х1 |
1 |
7/6 |
1/6 |
0 |
4/3 |
10 |
|
|
S2 |
0 |
-5/2 |
-1/2 |
1 |
6 |
0 |
|
|
z |
10 |
70/6 |
10/6 |
0 |
40/3 |
||
|
1 |
c-z |
0 |
-14/3 |
-10/6 |
0 |
40/3 |
Информация, содержащаяся в симплекс-таблице, соответствующей оптимальному решению, может быть записана в виде следующих уравнений.
z – уравнение: z+ 10x1+70/6x2+10/6S1=40/3,
х1 – уравнение: х1+7/6х2+1/6S1=4/3,
Так как в этом примере х1 на данный момент имеет дробное значение в оптимальной симплекс-таблице, именно это уравнение используем в качестве производящей строки для построения отсечения.
х1+7/6х2+1/6S1=4/3, (производящая х1-строка)
Для построения дробного отсечения каждый из нецелочисленных коэффициентов раскладывается на целую и дробную часть.
Разложение коэффициентов х2-строки приводит к следующему уравнению.
х1 + (1+1/6)х2 + 1/6S1=1 + 1/3
При переносе всех целочисленных слагаемых в левую часть уравнения, а всех дробных слагаемых в правую часть получаем следующее.
Х1 +x2-1 = 1/3 – 1/6X2-1/6S1
Поскольку все переменные в рассматриваемой задаче принимают целочисленные значения, левая часть последнего уравнения должна быть целочисленной, откуда следует, что и правая часть должна принимать целые значения.
Поскольку S1,x2 ≥0, выражение в скобках является неотрицательным. Поэтому величина 1/3 – 1/6X2-1/6S1, будучи целочисленной, не может превышать 1/3. Следовательно, необходимое условие целочисленности можно записать следующим образом.
1/3 – 1/6X2-1/6S1≤0
Это и есть дробное отсечение, порожденное х1-строкой. Нетрудно убедиться, что ранее найденное оптимальное решение не удовлетворяет отсечению (1/3≤0). Следовательно, если мы присоединим отсечение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет двигаться в направлении выполнения ограничения целочисленности.
Отсечение, порожденное х1- строкой записываем следующим образом.
1/6X2-1/6S1+ S3 = - 1/3
Это ограничение добавляется в качестве дополнительного в оптимальную симплекс-таблицу.
Таблица 11.9.3
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
X1 |
1 |
7/6 |
1/6 |
0 |
0 |
4/3 |
10 |
|
|
S2 |
0 |
-5/2 |
-1/2 |
1 |
0 |
6 |
0 |
|
|
S3 |
0 |
-1/6 |
-1/6 |
0 |
1 |
-1/3 |
0 |
|
|
z |
10 |
70/6 |
10/6 |
0 |
0 |
40/3 |
||
|
1 |
c-z |
0 |
-14/3 |
-10/6 |
0 |
0 |
Таблица представляет оптимальное, но недопустимое решение. Для восстановления допустимости решения применим двойственный симплекс-метод, что приведет к следующей симплекс-таблице.
Таблица 11.9.4
|
x1 |
x2 |
S1 |
S2 |
S3 |
b |
c |
||
|
X1 |
1 |
7/6 |
1/6 |
0 |
0 |
4/3 |
10 |
|
|
S2 |
0 |
-5/2 |
-1/2 |
1 |
0 |
6 |
0 |
|
|
S3 |
0 |
-1/6 |
-1/6 |
0 |
1 |
-1/3 |
0 |
|
|
z |
10 |
70/6 |
10/6 |
0 |
0 |
40/3 |
||
|
1 |
c-z |
0 |
-14/3 |
-10/6 |
0 |
0 |
||
|
X1 |
1 |
1 |
0 |
0 |
1 |
1 |
10 |
|
|
S2 |
0 |
-2 |
0 |
1 |
-3 |
7 |
0 |
|
|
S1 |
0 |
1 |
1 |
0 |
-6 |
2 |
0 |
|
|
z |
10 |
10 |
0 |
0 |
10 |
10 |
||
|
2 |
c-z |
0 |
-3 |
0 |
0 |
0 |
Оптимальное решение x1=1; x2=0; S1=2; S2=7; S3=0; Zmax=10 является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными не случайность. Это типичное явление при использование дробных отсечений.
2. График:
5. Задачі розподілення капіталовкладень розглядаються п'ять проектів, які можуть бути здійснені на протязі наступних трьох років. Прибуток, що очікують від реалізації кожного з проектів, та розподілення необхідних капіталовкладень по рокам (в тис. $) наведенні у таблиці. Передбачається, що кожен затверджений проект буде реалізовано за три роки. Треба вибрати сукупність проектів, який відповідає максимум сумарного прибутку.
|
Проект |
Розподіл Капіталовкладень |
Прибуток |
||
|
рік 1 |
рік 2 |
рік 3 |
||
|
1 |
5 |
1 |
8 |
20 |
|
2 |
4 |
7 |
5 |
40 |
|
3 |
13 |
9 |
12 |
20 |
|
4 |
7 |
4 |
1 |
15 |
|
5 |
8 |
6 |
10 |
30 |
|
Максимальний об'єм Капіталовкладень |
20 |
25 |
15 |
Побудувати математичну модель, знайти оптимальне рішення задачі. Дати оцінку методів розв’язання даної задачі.
РЕШЕНИЕ
Задача сводится к решению типа «да - нет» относительно каждого участка. Определим двоичные переменные :
= 1 , если проект j утвержден,
= 0 , если проект j неутвержден.
Задача ЦЛП будет записана следующим образом:
Максимизировать
при ограничениях
,
.
Данную задачу можно преобразовать в задачу минимизации, целевая функция которой содержит неотрицательные коэффициенты при всех переменных. При умножении на -1 получается задача минимизации.
Минимизировать
Поскольку все коэффициенты в ЦФ должны быть неотрицательны, сделаем замену:
Тогда:
Минимизировать
при ограничениях
Теперь все коэффициенты целевой функции неотрицательны. Запишем задачу в виде следующей таблицы.
|
Правые части |
||||||||
|
20 |
40 |
20 |
15 |
30 |
0 |
0 |
0 |
|
|
-5 |
-4 |
-13 |
-7 |
-8 |
1 |
0 |
0 |
-17 |
|
-1 |
-7 |
-9 |
-4 |
-6 |
0 |
1 |
0 |
-2 |
|
-8 |
-5 |
-12 |
-1 |
-10 |
0 |
0 |
1 |
-21 |
Пусть Jt— частичное решение, соответствующее вершине t (на начальной итерации , откуда следует, что все переменные являются свободными), — значение z на итерации t. Через обо значим текущее значение верхней границы (на начальной итерации ).
Итерация 0. Так как сначала все =0, дополнительные переменные принимают следующие значения:
,
, .
Легко видеть, что полученное решение не является допустимым , так как значения отрицательно. Следовательно, по крайней мере одной из переменных должно быть присвоено значение 1.Конечная цель этой процедуры – устранение недопустимости решения; критерием достижения цели служат значения дополнительных переменных.
Тест 1 – не исключает никакую переменную, т.к. все
Тест 2 также неприменим, т.к. нижняя граница
Тест 3 свидетельствует о том, что множество нельзя исключить из рассмотрения, так как:
Используя тест 4 ( Если и где
то переменную хк следует выбрать в качестве переменной, иниции рующей процесс ветвления.), получаем :
Отсюда k=3
Итерация 1.
PAGE 1