Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задание 2. Симплекс-метод решения задачи линейного программирования

Сайт: www.melashchuk.com

 

Решить задачу 1 симплекс-методом.

Решение

Приводим задачу к каноническому виду:

 

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

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

, где – коэффициенты при базисных переменных в целевой функции; – коэффициенты при переменной в системе ограничений; – коэффициент при переменной в целевой функции.

 

 

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

1 2 ↓ 0 0 0

Б Сб А0 Х1 Х2 Х3 Х4 Х5 ql2
  Х3
Х4
Х5 1,5 1,5
  f Dk –1 –2  

 

Начальное опорное решение не является оптимальным, так как в рассматриваемой задаче на максимум векторам Х1, Х2 соответствуют отрицательные оценки.

Найдем новое опорное решение, на котором значение целевой функции будет больше.

Так как из всех оценок Di наименьшая оценка , то будем вводить в базис вектор Х2. Для этого вектора находим оценки .

Наименьшая из этих оценок соответствует вектору Х5. Поэтому выводим из базиса вектор Х5. За разрешающий элемент принимаем элемент . Получаем опорное решение с базисом :

 

 

1↓ 2 0 0 0

Б Сб А1 Х1 Х2 Х3 Х4 Х5 ql1
Х3 1,5 -3 0,75
Х4 -2 1,4
  Х2 1,5
  f Dk -1  

 

 

Опорное решение А1 не является оптимальным, так как в рассматриваемой задаче на максимум вектору Х1 соответствует отрицательная оценка.

Найдем новое опорное решение.

Вводим в базис вектор Х1. Исключаем из базиса вектор Х4. За разрешающий элемент принимаем элемент . Получаем второе опорное решение с базисом :

 

 

1 2 0 0 0

Б Сб А2 Х1 Х2 Х3 Х4 Х5
  Х1 0,75 0,5 -1,5
Х4 3,25 -2,5 5,5
  Х2 1,5
  f 3,75 Dk 0,5 0,5

 

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

Таким образом, при .

Симплекс-метод решения задач линейного программирования (ЗЛП)

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

Данный метод состоит в целенаправленном переборе опорных решений ЗЛП. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие.

Алгоритм симплексного метода решения ЗЛП

1. Привести задачу к каноническому виду.

Каноническая ЗЛП имеет вид:

Если система ограничений задана в виде неравенств, то для перехода к равенствам достаточно ввести дополнительные переменные. В целевую функцию эти же переменные вводятся с нулевыми коэффициентами.

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решения).

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

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

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

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

Для проверки опорного решения на оптимальность необходимо найти оценки разложения вектора условий по базису опорного решения:

,

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

Опорное решение является оптимальным, если:

1) в задаче на максимум все ;

2) в задаче на минимум все .

Оптимальное решение ЗЛП является единственным, если для любого вектора условий, не входящего в базис, оценка отлична от нуля, то есть для всех .

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

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

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

Вектор, вводимый в базис, из условия:

1) в задаче на максимум ;

2) в задаче на минимум .

Вектор, выводимый из базиса, находим из условия: при .

 

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

 




<== предыдущая лекция | следующая лекция ==>
Технические условия - роль в переходный период | Типы личности

Дата добавления: 2015-03-11; просмотров: 1739. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2019 год . (0.016 сек.) русская версия | украинская версия