Задача минимизации целевой функции

Задачу о минимизации целевой функции можно решать двумя спо­собами: 1. Задачу линейного программирования по определению минимального

значения целевой функции сводим к задаче максимизации заменой

при неизменных ограничениях, затем после решения задачи перехо­дим к функции Z_min = -Z_{x max}.

2. Непосредственное решение задачи минимизации целевой функции симплексным методом, при этом признаком оптимальности является условие отсутствия положительных коэффициентов в Z-строке и ве­личина Z_minравна значению свободного члена в симплекс-таблице. Разрешающий элемент теперь следует брать в столбце над положи­тельным коэффициентом Z-строки, а разрешающая строка выбира­ется из условия минимального отношения свободных членов к соот­ветствующим коэффициентам этого столбца.

Пример 4.11

Определить минимальное значение целевой функции

(4.60)

при линейных ограничениях-неравенствах

(4.61)

и условиях

(4.62)

Решение

1. Целевую функцию (4.60) заменой Z₁ = -Z сведем к определению мак­симального значения, т.е.

(4.63)

2. Введем зависимые переменные согласно условиям и запишем ограничения (4.61) в виде:

(4.64)

3. Составим симплексную табл. № 1, включая в нее независимые х_к,за­висимые переменные у_i (4.64) и целевую функцию Z₁(4.64), т.е. условие исходной задачи запишем в табл. № 1:

Первоначальный план (решение) при х₁=, х₂ = х₃ = 0 имеет значение y₁ = 8, y₂ = 3, у₃ = 5, y₄ = 4 и Z₁ = -1 не является опорным, так как y₂= -3<0.

4. Определяем опорное решение задачи, выполняя шаг модифициро­ванного жорданова исключения с разрешающим элементом а₂₂ = -3. В качестве разрешающего столбца выбираем столбец с переменной х₂ (во второй строке с отрицательным свободным членом равным -3 отыскиваем отрицательный наибольший по модулю коэффициент, равный -3). Разрешающую строку определяем из условия:

В табл. № 2 все свободные члены положительны, кроме свободного члена Z₁-строки. Следовательно, решение задачи является опорным.

5. Определяем оптимальное решение задачи, т.е. находим максимальное значение функции Z₁ Так как в Z₁-строке имеется два отрицательных коэффициента -17/3 и -5/3, то в качестве разрешающего принимаем первый столбец с коэффициентом равным -17/3 (больший отрица­тельный по абсолютной величине). Разрешающую строку определяем из условия:

После шага модифицированного жорданова исключения с разрешаю­щим элементом получаем табл. № 3:

Решение задачи, представленное табл. № 3, не является оптимальным. Выполняя шаг модифицированного жорданова исключения с разрешаю­щим элементом а₄₃ = 1, получаем табл. № 4:

Табл. № 4 заполняем в такой последовательности: выписываем разре­шающие строку и столбец, а затем вычисляем значения свободных членов (столбец под 1) и коэффициентов Z₁-строки. Так как условия опорности и оптимальности выполняются для рассматриваемой задачи, то нет не­обходимости в определении остальных элементов табл. № 4.

Выписываем решение задачи из табл. № 4:

Проверка

Пример 4.12

Для заданной линейной целевой функции

(4.65)

определить минимальное значение при линейных смешанных ограниче­ниях:

(4.66)

и условиях:

(4.67)

Решение

1. Вводим зависимые переменные Запишем условие задачи, сведя ее к задаче максимизации, в виде:

(4.68)

2. Составляем симплексную табл. № 1, включая в нее зависимые, незави­симые переменные и целевую функцию. Получаем табл. № 1 в виде:

3. Исключаем свободную переменную х₂,выполняя шаг модифициро­ванного жорданова исключения с разрешающим элементом а₃₂ = -2. Получаем табл. № 2 в виде:

Выпишем значение для переменной х₂из табл. № 2:

(4.69)

Вычеркнем третью строку в этой таблице.

4. Исключаем 0-строку, выбирая в качестве разрешающего, столбец с положительным коэффициентом, равным 2, в этой строке, а разре­шающую строку определим из условия:

После шага модифицированного жорданова исключения с разрешаю­щим элементом a₄₃ = 2 получим табл. № 3:

5. В табл. № 3 вычеркиваем 0-столбец. Полученное решение не является опорным, так как в столбце свободных членов имеется отрицательное число, равное -4,5, т.е. у₁ = -4,5. Исключаем эту величину, сделав шаг модифицированного жорданова исключения с разрешающим элемен­том а₁₁ = -4,5. Получаем табл. № 4 в виде:

Из табл. № 4 выписываем решение задачи, а значение х₂ вычисляем на основании (4.69):

6. Решим задачу минимизации непосредственно (на примере 4.12), оп­ределяя значение целевой функции методом модифицированных жордановых исключений. Условием оптимальности при минимиза­ции целевой функции является отсутствие положительных коэффи­циентов в Z-строке симплексной таблицы. Условие задачи запишем в виде:

(4.70)

(4.71)

Решение

7. Составляем симплексную табл. № 5 для задачи (4.70) и (4.71) в виде:

8. Исключаем свободную переменную х₂в табл. № 5, сделав шаг моди­фицированного жорданова исключения с разрешающим элементом а₁₂ = 4. Получим табл. № 6 в виде:

(4.72)

Выпишем значение для переменной х₂

и вычеркнем первую строку в табл. № 6.

9. Исключаем 0-строку, выполнив шаг модифицированного жорданова исключения с разрешающим элементом а₄₃ = 2. Получим табл. № 7 в виде:

10. В табл. № 7 вычеркиваем 0-столбец и исключаем отрицательный сво­бодный член, т.е. определяем опорное решение, с разрешающим эле­ментом a₂₁ = -2,25, Получаем табл. № 8 в виде:

В табл. № 8 условие оптимальности выполняется: в Z-строке все ко­эффициенты отрицательные при условии минимизации целевой функ­ции Z.

Выписываем решение задачи из табл. № 8, а значение для х₂опреде­ляем из условия (4.72):

Контрольные вопросы

1. В чем заключается сущность симплексного метода решения задач линейно­го программирования?

2. Как составляются симплексные таблицы?

3. Решение задач линейного программирования способом модифицирован­ных жордановых исключений.

4. Сформулируйте признаки опорности и оптимальности решения задач ли­нейного программирования.

5. Как определяются разрешающие элементы при определении опорного и оптимального решений задачи линейного программирования?

6. Укажите последовательность решения задач линейного программирования при смешанных ограничениях и наличии свободных независимых пере­менных.

7. Какими способами решаются задачи линейного программирования при минимизации целевой функции?

8. Назовите условие несовместности системы ограничений и признак неогра­ниченности целевой функции в задачах линейного программирования.

9. По какому правилу выбираются разрешающие элементы при исключении свободных независимых переменных и 0-строк в симплексных таблицах?

Задачи 4.1-4.16

Определить оптимальные решения задач линейного программиро­вания симплексным методом