История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2018-01-04 | 310 |
5.00
из
|
Заказать работу |
|
|
проверка допустимости решения ЗЛП на основе заполненной симплекс-таблицы. В качестве признака допустимости решения ЗЛП выступает требование неотрицательности всех элементов второго столбца (коэффициентов ) симплекс-таблицы (коэффициент в расчёт не принимается).
Если данное требование не выполняется (т.е. среди коэффициентов имеется хотя бы один отрицательный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 4 лабораторной работы №5. При этом если в ходе поиска допустимого решения возникнет ситуация, когда в симплекс-таблице один или несколько элементов второго столбца отрицательны, и хотя бы в одной строке, соответствующей одному из этих элементов, остальные элементы положительны, то это свидетельствует об отсутствии у ЗЛП допустимого решения.
Алгоритм поиска оптимального решения ЗЛП на основе симплекс-таблиц.
проверка данного допустимого решения на оптимальность. Признаком оптимальности решения ЗЛП является требование отрицательности всех элементов второй строки (коэффициентов rj) симплекс-таблицы (коэффициент в расчёт не принимается). Если данное требование не выполняется (т.е. среди коэффициентов rj имеется хотя бы один положительный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 3 лабораторной работы №5, до тех пор, пока не будет получено единственное оптимальное решение. При этом искомыми оптимальными значениями переменных будут значения базисных переменных второго столбца конечной симплекс-таблицы, а минимальным значением целевой функции – значение . В принципе, можно решать задачу получения оптимального решения и добиваясь положительности всех элементов второй строки, но в таком случае минимальным значением целевой функции будет значение , взятое с отрицательным знаком.
|
При этом если в ходе поиска оптимального решения возникнет ситуация, когда во второй строке симплекс-таблицы один или несколько элементов равны нулю (коэффициенты rj), а все остальные отрицательны, то это свидетельствует о том, что данная ЗЛП имеет бесчисленное множество оптимальных решений.
Например, если коэффициент r2 = 0, то имеет место выражение для целевой функции , где переменная x2, а, следовательно, и сама целевая функция могут принимать произвольное значение.
Если же в ходе поиска оптимального решения окажется, что во второй строке симплекс-таблицы один или несколько элементов положительны, а в столбце, соответствующем положительному элементу, остальные элементы (коэффициенты ) отрицательны, то это свидетельствует о том, что данная ЗЛП не имеетоптимального решения.
20. Алгоритм поиска оптимального решения ЗЛП на основе симплекс-таблиц.
Табличный симплекс-метод
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn + xn+1=b1
a2,1x1+a2,2x2+...a2,nxn +xn+2 =b2
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
Исходная таблица для задачи имеет следующий вид:
x1 | x2 | ... | xn-1 | xn | b | |
F | -a0,1 | -a0,2 | ... | -a0,n-1 | -a0,n | -b0 |
xn+1 | a1,1 | a1,2 | ... | a1,n-1 | a1,n | b1 |
xn+2 | a2,1 | a2,2 | ... | a2,n-1 | a2,n | b2 |
... | ... | ... | ... | ... | ... | ... |
xn+m | am,1 | am,2 | ... | am,n-1 | am,n | bm |
x1, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определеннымправилам.
|
Алгоритм симплекс-метода.
Подготовительный этап
Приводим задачу ЛП к каноническому виду
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn+xn+1=b1
a2,1x1+a2,2x2+...a2,nxn+xn+2=b2
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!