Условно-стандартная задача линейного программирования

 















Условно-стандартная задача линейного программирования

двойственный линейный программирование гомори


Необходимо выполнить в указанном порядке следующие задания.

. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

. Построить двойственную задачу.

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

. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

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

. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений.



1. а) Найдем оптимальный план прямой задачи графическим методом

Решение: Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):



Область допустимых решений определяется множеством АВСDЕ.



Для линий уровня 2х1 + 3х2 = h (h - const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рисунке она проходит через начало координат) Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L6 и L4, т.е. через точку . Для определения координат точки А решаем систему уравнений:


Это и будет оптимальным решением данной задачи, которому соответствует максимальное значение целевой функции Zmax:


.


. б) Найдем оптимальный план прямой задачи симплекс-методом.

Приводим задачу к каноническому виду. Умножим первое ограничение на -1:



Для этого в левую часть ограничений-неравенств типа «£» вводим по дополнительной переменной с коэффициентом (+1). В целевую функцию эти переменные входят с коэффициентом (0). Получаем


В 3-м ограничении отсутствует базисная переменная. Формулируем задачу искусственного базиса.



Полученную задачу будем решать модифицированным симплексным методом [1].

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



Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю х1 = х2 = 0. Получаем опорное решение Х1 = (0,0,19,28,0,47,19) с единичным базисом

Б1 = (А3, А4, А7, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения,


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


Сб000000-1xbbx1¯x2x3x4x5x6х7b/x1b/x20x3195-4100003 4/5-0x428-2-501000---1¬x744100-10114Min0x64767000107 5/66 5/7Dk-4-4-10010044

Начальное опорное решение не является оптимальным, так как оценки D1 = -4, D2 = -1 для векторов А1 и А2 противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.

Определим, введение, какого из двух векторов приведёт к большему приращению целевой функции. Приращения целевой функции найдём по формуле . Вычислим значения параметра q01 для первого и третьего столбцов по правилу Креко, получим q01 = 1 при l = 2 и q02 =4 при l =2. Находим приращение целевой функции при введении в базис первого вектора и второго вектора . Следовательно, для наиболее быстрого нахождении оптимального решения необходимо ввести в базис опорного решения вектор А2 вместо вектора базиса А7.

Далее выполним преобразование Жордана-Гаусса с элементом х22 = 1, получим второе опорное решение Х2:


Сб000000-1xbbx1x2x3x4x5x6х70x33521010-4040x44818001-5050x244100-1010x619-2200071-7Dk00000001

Так как оценки неотрицательны, построенный план оптимален.

Искусственные переменные выведены из базиса.

Оптимальное решение вспомогательной задачи - это х7=х8=0, max G=0.

Попутно построен опорный план исходной канонической задачи:


x335x448x24x619

Вернемся к ней. Используем последнюю симплекс-таблицу, из которой исключим переменную х7 и изменим цены базисных переменных, взяв их из заданной целевой функции. Получим


Сб230000xbbx1x2x3x4¯x5x6b/x50x33521010-40-0x44818001-50-3x244100-10-0¬x619-22000712 5/7MinDk1210000-30

План необходимо улучшить. Вводим в базис х5, выводим х6


Сб230000xbbx1x2x3x4x5x60x345 6/78 3/701004/70x461 4/72 2/700105/73x26 5/76/710001/70x52 5/7-3 1/700011/7Dk20 1/74/700003/7

Проверим план на оптимальность. Оценки неотрицательны, план оптимален.

Ответ: max Z(X) = 20 1/7 при Х*= (0; 6 5/7; 45 6/7; 61 4/7; 2 5/7; 0).


2. Построим двойственную задачу к исходной. Так как исходная задача на максимизацию, то приведём все неравенства системы ограничений к виду «£», для чего обе части 1-го и 3-го неравенств умножим на (-1). Получим



Составим расширенную матрицу системы


.


Найдём матрицу , транспонированную к А


.


Сформулируем двойственную задачу:



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

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



Так как прямая задача разрешима, то двойственная тоже имеет решение, и, в силу первой теоремы двойственности, . Найдем значения переменных.

Подставим найденное оптимальное решение Х*= (0; 6 5/7) в систему ограничений исходной задачи:



В силу условия 1 дополняющей нежесткости получаем: .

Получаем систему уравнений для нахождения оставшихся неизвестных:



Ответ: оптимальное решение двойственной задачи


.


. Найдем оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Решению двойственной задачи соответствуют оценки переменных х3 - х6..

Проверим утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают», то есть то есть равенство выполняется.

. Двойственную задачу решим симплекс-методом.



Запишем задачу в каноническом виде.

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



Сформулируем задачу искусственного базиса



Сформулируем вспомогательную задачу искусственного базиса. Ее решение даст нам опорный план исходной канонической задачи (см. [1])


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


Сб000000-1-1xbby1y2y3¯y4y5y6y7y8b/y1b/y4-1¬y725-2-46-10102/51/3Min-1y83-4-5-170-101-3/7Dk-5-175-1311002/54 1/3

Сб000000-1-1xbby1y2y3y4¯y5y6y7y8b/y3b/y50y41/35/6- 1/3- 2/31- 1/601/60---1¬y82/3-9 5/6-2 2/33 2/301 1/6-1-1 1/612/114/7Dk- 2/39 5/62 2/3-3 2/30-1 1/612 1/602/32/3

Сб000000-1-1xbby1y2y3y4y5y6y7y80y43/7- 4/7- 5/7- 1/710- 1/701/70y54/7-8 3/7-2 2/73 1/701- 6/7-16/7Dk000000011

Оценки неотрицательны, следовательно, решение задачи искусственного базиса, т.е. , max (-G(y))=0. Параллельно построен начальный опорный план исходной канонической задачи: .

Исключим из рассмотрения искусственные переменные, перепишем последнюю таблицу, заменив в ней нулевые цены на цены переменных из исходной задачи.

Пересчитаем оценки.


Сб-19-284-4700xbby1y2y3y4y5y6-47y43/7- 4/7- 5/7- 1/710- 1/70y54/7-8 3/7-2 2/73 1/701- 6/7Dk-20 1/745 6/761 4/72 5/7006 5/7

Так как оценки неотрицательны, построенный план не требует дальнейшего улучшения.

Решение двойственной задачи:


.


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

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


.


Сравним результат с результатом, который был получен графическим методом (см. п. 1а).

Очевидно, что результаты совпадают.

. а) Найдем оптимальное целочисленное решение графическим методом.

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



Точка максимума с целочисленными координатами - это, очевидно, F (2; 5). Максимальное значение функции в этом случае равно Z=2*2+3*5= 19.

. б) Найдем оптимальное целочисленное решение методом Гомори.

Для этого используем последнюю таблицу п. 1 б)


Сб-19-284-4700xbby1y2y3y4y5y6-47y43/7- 4/7- 5/7- 1/710- 1/70y54/7-8 3/7-2 2/73 1/701- 6/7Dk-20 1/745 6/761 4/72 5/7006 5/7

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

Построим отсечение дробной части по переменной х4.

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


Сб02300000xbbx1x2x3x4x5¯x6х7b/x1b/x60x345 6/78 3/701004/705 26/5980 1/40x461 4/72 2/700105/7026 15/1686 1/53x26 5/76/710001/707 5/6470x52 5/7-3 1/700011/70-190¬x7- 4/7- 2/70000- 5/7124/520 1/74/700003/70

Оценки переменных остались неизменными. Но в столбце свободных членов появился отрицательный элемент. Следовательно, выводим из базиса х7. Наименьшее отношение дает 4/5, поэтому вводим в базис х6.


Сб023000000xbb¯x1x2x3x4x5x6х7х8b/x1b/x70x345 2/58 1/5010004/505 22/4156 3/40x4612001001030 1/2613x26 3/54/5100001/508 1/4330x52 3/5-3 1/5000101/50- 13/16130x64/52/500001-1 2/502- 4/70¬x8- 3/5- 4/500000- 1/513/43minDk19 4/52/5000003/50

Получено оптимальное, но нецелочисленное решение. Выполним отсечение дробной части по переменной х2. Дробные части чисел строки х2 запишем в строку х8 с отрицательными знаками. Введем в базис х1, выведем х8. Получим следующую таблицу:


Сб0230000000xbbx1x2x3x4x5x6х7¯х8х9b/x7b/x80x339 1/4001000-1 1/410 1/40-3 34/410x459 1/20001001/22 1/2011923 4/53x26010000010-60x550000101-405-0x61/2000001-1 1/21/20-12х13/41000001/4-1 1/403-0¬х9- 1/2-000000- 1/2- 1/2111Dk19 1/20000001/21/20

0x1x20000000xbbx1x2x3x4x5x6х7х8х90x329-001000-11 1/2020 1/20x457-000100-2053x25-010000-1020x5900001050-80x60000001-2012х121000001 1/20-2 1/20х9100000011-219000000001

Так как оценки Dk неотрицательны, а числа в столбце «b» целые, получено оптимальное целочисленное решение задачи: х1=2, х2=5, max Z= 19.

Сравним значения функций целочисленного и нецелочисленного решений: значение функции, полученное без условия целочисленности, больше: 20 1/7 > 19.


Условно-стандартная задача линейного программирования двойственный линейный программирование гомори

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ