Категория
Информатика
Тип
реферат
Страницы
5 стр.
Дата
14.03.2014
Формат файла
.html — Html-документ
Архив
1005502.zip — 3.5 kb
  • zadachi-linejnogo-programmirovanija-2_1005502_1.html — 11.3 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы


--PAGE_BREAK--




Аналогично определяются координаты точки минимума С:







Индивидуальные задания.Решить графическим методом.


--PAGE_BREAK--Для этого в случае необходимости задача (1.1) поиска минимума сводится к задаче на поиск максимума (1.7) путем изменения знаков коэффициентов Сj

;


        Неравенства (1.2) преобразуются в строгие равенства путем введения дополнительных неотрицательных переменных; условия неотрицательности (1.3) распространяются на все переменные путем введения подстановок.


       
Пример . Дана задача ЛП в общем виде:





        Приведем ее к каноническому виду. Условие неотрицательности не распространяется на переменную х2. Поэтому введем подстановку: х2 = х5 – х4, где
.


Тогда





        Изменим вид экстремума на максимум:



        Изменим неравенства на строгие равенства путем введения дополнительных неотрицательных переменных. Тогда




Основные понятия и определения

.
Исходная задача (1.7), (1.8), (1.9) может быть представлена в векторной форме:


x1Р1+x2Р2+…+xnPn=P0


        С=(c1, c2 … cn); X=(x1,x2 … xn); P1,P2…Pn, P0– m-мерные вектор-столбцы.


        Вектор X=(x1,x2 … xn) называется опорным планом задачи ЛП, если он удовлетворяет ограничениям (1.8); (1.9) и содержит m отличных от нуля положительных компонент. Остальные (n-m) элементов опорного плана равны нулю. Алгоритм симплекс-метода предполагает переход от одного опорного плана к другому с увеличением при этом значения целевой функции.


        В некоторых случаях исходный опорный план можно легко определить. Это происходит тогда, когда среди векторов Pj
 имеется m единичных. В этом случае соответствующие единичным векторам переменные в опорном плане будут отличны от нуля. Они называются базисными. Остальные переменные равны нулю; они называются свободными.


        Симплекс-преобразования продолжаются до тех пор, пока среди чисел
 
 не будет отрицательных.


        Исходная симплекс-таблица в общем случае имеет вид


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


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


        В (m+1)-й строке: F0 – текущее значение целевой функции; в столбцах Pj
 записаны числа
.

        
Алгоритм решения.



Ваше мнение



CAPTCHA