Методичка - Симплекс-метод решения задачи линейного программирования - файл n1.doc

приобрести
Методичка - Симплекс-метод решения задачи линейного программирования
скачать (14.5 kb.)
Доступные файлы (1):
n1.doc69kb.15.12.2002 09:36скачать

n1.doc

  1   2   3   4   5
Практические занятия №4,5,6 (6 час.)
Тема: Симплекс-метод решения задачи линейного программирования.

Рассматриваемые вопросы:




  1. Симплекс-алгоритм.

Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования (ЛП), перестает быть пригодной для этой цели при числе свободных переменных n – m >= 3. Для нахождения решения задачи ЛП в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.

Идея симплекс-метода относительно проста. Пусть в задаче ЛП имеется n переменных и m независимых линейных ограничений, заданных в форме уравнений, т.е. задача ЛП формулирована в канонической форме. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из угловых точек (вершин ОДР), где по крайне мере k = n – m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n – m переменных x1 , x2 , … xk , а остальные m выражены через них:

xk+1 = ak+1,1x1 + ak+1,2x2 + … + ak+1,kxk + bk+1

xk+2 = ak+2,1x1 + ak+2,2x2 + … + ak+2,kxk + bk+2

… (1)

xn = an,1x1 + an,2x2 + … + an,kxk + bn
  1   2   3   4   5


Практические занятия №4,5,6
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации