Условно-стандартная задача линейного программирования
Условно-стандартная задача линейного программирования
двойственный линейный программирование гомори
Необходимо выполнить в указанном порядке следующие задания.
. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
. Построить двойственную задачу.
. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 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 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ