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

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

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

задача минимизации целевой функции - student2.ru

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

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

Пример 4.11

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

задача минимизации целевой функции - student2.ru (4.60)

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

задача минимизации целевой функции - student2.ru (4.61)

и условиях

 
  задача минимизации целевой функции - student2.ru

(4.62)

Решение

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

задача минимизации целевой функции - student2.ru

(4.63)

задача минимизации целевой функции - student2.ru 2. Введем зависимые переменные согласно условиям и запишем ограничения (4.61) в виде:

задача минимизации целевой функции - student2.ru (4.64)

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

 
  задача минимизации целевой функции - student2.ru

Первоначальный план (решение) при х1=, х2 = х3 = 0 имеет значение y1 = 8, y2 = 3, у3 = 5, y4 = 4 и Z1 = -1 не является опорным, так как y2= -3<0.

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

задача минимизации целевой функции - student2.ru

 
  задача минимизации целевой функции - student2.ru

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

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

задача минимизации целевой функции - student2.ru задача минимизации целевой функции - student2.ru

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

 
  задача минимизации целевой функции - student2.ru

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

 
  задача минимизации целевой функции - student2.ru

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

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

 
  задача минимизации целевой функции - student2.ru

Проверка

задача минимизации целевой функции - student2.ru

Пример 4.12

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

(4.65)

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru (4.66)

и условиях:

задача минимизации целевой функции - student2.ru (4.67)

Решение

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

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru (4.68)

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

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

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

 
  задача минимизации целевой функции - student2.ru

(4.69)

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

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

 
  задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

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

(4.70)

задача минимизации целевой функции - student2.ru

(4.71)

Решение

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

задача минимизации целевой функции - student2.ru

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

 
  задача минимизации целевой функции - student2.ru

(4.72)

 
  задача минимизации целевой функции - student2.ru

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

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

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

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

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

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

задача минимизации целевой функции - student2.ru

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

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

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

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

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

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

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

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

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

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

Задачи 4.1-4.16

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

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

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

задача минимизации целевой функции - student2.ru

Наши рекомендации