Линейное программирование. Симплекс-метод

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД 417  [c.417]

Линейное программирование. Симплекс-метод  [c.417]


ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД 419  [c.419]

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД 421  [c.421]

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ СИМПЛЕКС-МЕТОД 423  [c.423]

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД  [c.427]

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. СИМПЛЕКС-МЕТОД 431  [c.431]

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, СИМПЛЕКС-МЕТОД 433  [c.433]

Описанная выше математическая модель соответствует использованию универсального метода линейного программирования — симплекс-метода, получившего наибольшее применение в настоящее время для решения задач развития и размещения отраслей химической промышленности при статической постановке задачи.  [c.177]

Пример 7.13. Решение задачи линейного программирования симплекс-методом. Для нахождения опорного плана использовать метод искусственных переменных.  [c.222]


Представляется полезным обратить внимание читателя и на то, что применяемый для решения задач линейного программирования симплекс-метод может быть рассмотрен как частный случай метода допустимых направлений. В частности, этап выбора столбца, вводимого в очередной базис, соответствует определению допустимого прогрессивного направления. Более подробно о такой концепции симплекс-метода можно прочесть в [1].  [c.98]

Решение задачи линейного программирования симплекс-методом  [c.197]

Наконец, рассмотрим многокритериальные симплекс-методы,, основанные на использовании симплекс-таблицы линейного программирования. Эти методы очень близки к методам параметрического программирования и состоят в переходе из некоторой исходной точки (скажем, точки А см. рис. 6.9) в соседнюю эффективную точку. При этом, в отличие от методов взвешивания, понятие весов не используется. Многокритериальные симплекс-методы имеют те же самые достоинства и1 недостатки, что и параметрические методы.  [c.311]

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


Итак, для нахождения оптимальной производственной программы необходимо такое решение системы многих уравнений с многими неизвестными, при котором критерий (целевая функция) достигает оптимума. Система уравнений и неравенств (24.1) — (24.5), (24.7) обладает следующим свойством она линейна относительно неизвестных. Это означает, что неизвестные входят в уравнения, неравенства и критерий лишь в первой степени и что отсутствуют произведения неизвестных. Методом решения подобных задач, которые носят название задач линейного программирования, служит так называемый симплекс-метод. Симплекс-метод изложен в целом ряде книг. Ограничимся лишь его технико-экономической интерпретацией.  [c.413]

Наиболее распространенным методом решения важных практических задач планирования и управления является линейное программирование. С помощью симплекс-метода решаются задачи планирования производственной программы предприятия, объединения, способствующие получению максимального эффекта при ограниченных материальных и трудовых ресурсах. Распределительный метод линейного программирования позволяет выбрать оптимальные варианты планов транспортных перевозок решать задачи по оптимизации планов загрузки оборудования и др.  [c.78]

Для решения задачи (I) автор предлагает использовать метод ветвей и границ, а для нахождения решения семейства задач (II) -использовать методы линейного программирования (например. симплекс -метод).  [c.120]

В этих случаях используется симплекс-метод, который представляет собой итеративную (пошаговую) процедуру для определения оптимального решения задачи линейного программирования. Расчеты по симплекс-методу начинают с определения допустимого решения, а затем отыскиваются другие допустимые решения и проверяются возможности их улучшения. Переход от одного решения к другому продолжается до тех пор, пока новые улучшения не будут невозможны. Широко распространены стандартные компьютерные программы, которые используют симплекс-метод для решения таких управленческих задач, которые можно представить как задачи линейного программирования.  [c.220]

Следует отметить, что метод проб и ошибок, а также графический метод полезны в случае двух или, возможно, трех переменных. Для решения проблемы линейного программирования со многими переменными эти методы непрактичны. Стандартные программные пакеты для персональных компьютеров реализуют в этом случае симплекс-метод, который представляет собой итеративный пошаговый процесс. Он начинается выбором одного возможного решения с последующим замещением его, если результат можно улучшить. Этот перебор продолжается до тех пор, пока дальнейшее улучшение перестает быть возможным.  [c.385]

Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.  [c.163]

Задачи с помощью линейного программирования решаются двумя способами симплекс-методом и распределительном методом.  [c.41]

Симплекс-метод (аналитическое решение задач линейного программирования) — это алгоритм формального пересчета вариантов решения задачи с последовательным движением к оптимальному решению. Каждый шаг алгоритма расчетов улучшает предыдущее решение.  [c.122]

Для отыскания максимумов или минимумов в таких случаях существует масса методов. Любой из них, как правило, накладывает на переменные некие ограничения, которые должны удовлетворяться применительно к экстремуму. К примеру, в нашем случае эти ограничения заключаются в том, чтобы все независимые переменные (значения J) были бы большими или равными нулю. Нередко требуется выполнение ограничивающих функций (т. е. чтобы значения других функций от используемых переменных были бы больше/меньше или равны некоторым величинам). Линейное программирование с его симплекс-методом — эта весьма хорошо разработанная область такой оптимизации в условиях ограничений — применима лишь, когда и оптимизируемая, и ограничивающие функции являются линейными (многочленами первой степени).  [c.186]

На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования-так называемый симплекс-метод.  [c.65]

Симплекс-метод является алгебраической формой решения задачи линейного программирования, вытекающей из только что рассмотренного геометрического представления. При обосновании симплекс-метода будем прибегать к уже рассмотренному выше двухмерному случаю, что позволит достаточно просто перейти от геометрического представления к его алгебраической аналогии.  [c.65]

В четвертой главе выясняется, каким образом производить учет не одного сообщения об относительной важности критериев, а целого набора такого рода сообщений. Сначала подробно разбирается случай двух сообщений. В частности, выясняется, что при определенных значениях числовых коэффициентов относительной важности вполне возможен случай, когда один критерий важнее другого, а тот, в свою очередь, важнее первого. В этой же главе изучается вопрос непротиворечивости произвольного набора информации об относительной важности критериев. Приведены три утверждения, с помощью которых всегда можно проверить является ли определенный набор информации противоречивым или нет. Далее исследуется вопрос учета произвольного набора количественной информации об относительной важности критериев и предлагается отличный от упомянутого ранее так называемый алгоритмический подход. Для случая конечного множества возможных решений формулируется алгоритм этого подхода, использующий симплекс-метод решения канонической задачи линейного программирования.  [c.13]

В соответствии с теоремой 4.12 проверка справедливости соотношения у >м У" сводится к решению канонической задачи линейного программирования (4.27). Это решение может быть осуществлено с помощью известного алгоритма симплекс-метода. Такой способ проверки соотношения у1 >м у" удобен при создании общего алгоритма построения оценки сверху в случае конечного множества возможных векторов Y. Если же требуется решить задачу невысокой размерности вручную , то более удобным оказывается использование следующего результата, который представляет собой частный случай теоремы 4.12, установленный в ходе доказательства этой теоремы.  [c.127]

Для любой задачи линейного программирования можно сформулировать задачу-двойник, или, иначе, двойственную задачу. Эта задача-двойник является своеобразным "зеркальным отражением" исходной задачи, поскольку ее формулировка использует те же параметры, что и исходная задача, а ее решение может быть получено одновременно с решением исходной задачи. Фактически при решении исходной задачи симплекс-методом одновременно решается и двойственная задача, и наоборот. Следует также заметить, что исходная и двойственная задачи совершенно симметричны. Если двойственную задачу рассматривать как исходную, то исходная будет для нее двойственной.  [c.65]

Одним из основных условий применимости симплекс-метода и других методов решения задач линейного программирования является то, что переменные решения могут принимать непрерывный ряд значений, т.е., иными словами, быть не только целыми, но и дробными.  [c.98]

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

Симплекс-метод. Это один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г.Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.  [c.170]

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (симплекс-метод) [simplex method] — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т.н. вырожденной задачи, при которой возможно явление "зацикливания", т.е. многократного возврата к одному и тому же положению). Название метод получил от термина " -мерный симплекс". Геометрическая интерпретация метода состоит в последовательном движении по верши) шм симплекса.  [c.322]

Становление современного математического аппарата оптимальных экономических решений началось в 40-е годы, благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. Канторовича. Задача линейного программирования впервые математически сформулирована Л. В. Канторовичем в 1939 г. на примере задачи раскроя материалов для Ленинградского фанерного треста. В 1947 г. Дж. Данциг предложил универсальный алгоритм решения задач линейного программирования, названный им симплекс-методом. В 1941 г. Хичкок и независимо от него в 1947 г. Купсман формулируют транспортную задачу, в 1945 г. Стиглер — задачу о диете. В 1952 г. было проведено первое успешное решение задачи линейного программирования на ЭВМ Sea в Национальном бюро стандартов США.  [c.102]

М301. Мультипликативный симплекс-метод решения общей задачи линейного программирования  [c.35]

Почему так получилось Дело в том, что введенное дополнительное ограничение превратило нашу задачу о назначениях (по существу транспортную задачу) в обычную задачу линейного программирования. Для такой задачи специализированные "транспортные" методы решения неприменимы. А как указывалось раньше, только они обеспечивают целочисленные решения без введения явных требований целочисленности. Получившуюся общую ЛП-задачу MS-Ex el решают с помощью обычного симплекс-метода, а он отнюдь не гарантирует целочисленности переменных решения.  [c.141]

СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции.  [c.322]