Решение задачи (24.1) — (24.7) нахождения оптимальной производственной программы симплекс-методом осуществляется на ЭВМ в два этапа на первом этапе отыскивается допустимый план на втором — происходит улучшение допустимого плана до оптимального. В целом можно сказать, что решение задачи нахождения [c.413]
Упорядоченный перебор интересующих нас допустимых планов, нахождение допустимых планов требуют огромной вычислительной работы, которая осуществляется на ЭВМ. Симплекс-метод, согласно которому ЭВМ осуществляет упорядоченный перебор и находит оптимальное решение, является наиболее распространенным экономико-математическим методом. [c.414]
Наиболее распространенным методом решения важных практических задач планирования и управления является линейное программирование. С помощью симплекс-метода решаются задачи планирования производственной программы предприятия, объединения, способствующие получению максимального эффекта при ограниченных материальных и трудовых ресурсах. Распределительный метод линейного программирования позволяет выбрать оптимальные варианты планов транспортных перевозок решать задачи по оптимизации планов загрузки оборудования и др. [c.78]
Для решения задачи (I) автор предлагает использовать метод ветвей и границ, а для нахождения решения семейства задач (II) -использовать методы линейного программирования (например. симплекс -метод). [c.120]
Рассмотрим некоторые особенности этого метода. В качестве-основы может быть выбран алгоритм симплекс-метода (например, мультипликативный), в котором на каждой итерации в явном виде вычисляется вектор симплексных множителей по формуле [c.99]
Вычислительная схема реализации расчетов по модели (2)— (9) на основе мультипликативного алгоритма симплекс. — метода показана на рисунке. [c.100]
Симплекс-метод представляет собой технику решения задач с ограничивающими факторами при помощи компьютера (соответствующие расчеты можно сделать и вручную, но это очень трудоемко, даже при относительно несложных задачах). Будучи ограниченным только аппаратными или программными возможностями (т.е. особенностями прикладной программы или объемом памяти компьютера), симплекс-метод позволяет решать задачи с огромным количеством товаров/услуг и ограни- [c.370]
Симплекс-метод — это техника решения многопродуктовых задач в условиях ограничений, чаще реализуемая с помощью компьютера. [c.378]
Для решения симплекс-методом (на компьютере) технический консультант спортклуба сформулировал задачу о размещении кресел [c.389]
Наконец, рассмотрим многокритериальные симплекс-методы,, основанные на использовании симплекс-таблицы линейного программирования. Эти методы очень близки к методам параметрического программирования и состоят в переходе из некоторой исходной точки (скажем, точки А см. рис. 6.9) в соседнюю эффективную точку. При этом, в отличие от методов взвешивания, понятие весов не используется. Многокритериальные симплекс-методы имеют те же самые достоинства и1 недостатки, что и параметрические методы. [c.311]
Стандартные программные пакеты для персональных компьютеров реализуют в этом случае симплекс-метод, который представляет собой итеративный пошаговый процесс. Он начинается с выбора одного возможного решения с последующим замещением его, если результат может быть улучшен. Этот перебор продолжается до тех пор, пока дальнейшее улучшение невозможно. Таким образом будет получено оптимальное решение. [c.280]
В этих случаях используется симплекс-метод, который представляет собой итеративную (пошаговую) процедуру для определения оптимального решения задачи линейного программирования. Расчеты по симплекс-методу начинают с определения допустимого решения, а затем отыскиваются другие допустимые решения и проверяются возможности их улучшения. Переход от одного решения к другому продолжается до тех пор, пока новые улучшения не будут невозможны. Широко распространены стандартные компьютерные программы, которые используют симплекс-метод для решения таких управленческих задач, которые можно представить как задачи линейного программирования. [c.220]
Нахождение оптимального решения. В случае, когда в целевой функции только две переменные и количество ограничений небольшое, для нахождения оптимального решения можно использовать графический метод и метод проб и ошибок. В более сложных случаях, которые возникают на практике, необходимы специальные пакеты программного обеспечения, например симплекс-метод. [c.382]
Следует отметить, что метод проб и ошибок, а также графический метод полезны в случае двух или, возможно, трех переменных. Для решения проблемы линейного программирования со многими переменными эти методы непрактичны. Стандартные программные пакеты для персональных компьютеров реализуют в этом случае симплекс-метод, который представляет собой итеративный пошаговый процесс. Он начинается выбором одного возможного решения с последующим замещением его, если результат можно улучшить. Этот перебор продолжается до тех пор, пока дальнейшее улучшение перестает быть возможным. [c.385]
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом. [c.163]
Задачи с помощью линейного программирования решаются двумя способами симплекс-методом и распределительном методом. [c.41]
Симплекс-метод см. Баканов М. И., Шеремет А. Д. Теория экономического анализа. - М. Финансы и статистика, 1998.-С. 162- 171. Приведенный в учебнике пример также может служить материалом для практических занятий. [c.42]
Известно, что в случае двух переменных решение задачи математического программирования можно провести не только аналитически (например, используя симплекс-метод), но и графически. В нашем примере интерес представляет только целочисленное решение. [c.221]
Линейное программирование — математический метод, предназначенный для выявления оптимального решения из большого числа возможных вариантов решения задачи, у которой условия позволяют запись в виде линейных соотношений. Линейное программирование применяется для решения задач типа распределение ресурсов, формирование комбинации кормов, составление портфеля инвестиций, выбор производственной программы. Для постановки задачи линейного программирования необходимо ввести переменные (определяемые) величины, выразить через эти переменные ограничивающие условия и целевую функцию. Для решения задач линейного программирования используют симплекс-метод или графический метод (при наличии двух переменных в решаемой задаче). [c.122]
Симплекс-метод (аналитическое решение задач линейного программирования) — это алгоритм формального пересчета вариантов решения задачи с последовательным движением к оптимальному решению. Каждый шаг алгоритма расчетов улучшает предыдущее решение. [c.122]
Рассмотрим алгоритм симплекс-метода на основе числового примера — оптимизационной задачи, включающей пять неизвестных и три ограничивающих условия. [c.122]
Это решение задачи представим в виде таблицы (симплекс-таблицы) (табл. 8.3). Эта таблица в условном виде повторяет систему условий задачи. [c.122]
Решение. В результате решения задачи симплекс-методом найдем оптимальное решение х = 1 х = 7, 5 1 =29,5, где верхний индекс переменных — номер задачи. [c.127]
Результаты решения симплекс-методом задачи 2 х = 1,2 j f = 7 L2 = 29,4 задачи 3 х = 0,75 xf = 8 L3 = 29,25. [c.128]
Находится начальное допустимое решение задачи. В качестве начального допустимого решения может быть рассмотрена искусственная форма стандартной симплекс-процедуры или некоторое допустимое либо оптимальное решение задачи (2.28), полученное при фиксированных номинальных значениях KJ вектора /Ту. [c.31]
Здесь я - вектор-строка симплекс-множителей, определяемая из выражения [c.31]
Найденные в результате решения подзадач (2.30) значения относительных оценок "с- анализируются совместно с относительными оценками остальных небазисных переменных. Последующие процедуры определения столбца, выводимого из базиса, ввода в базис нового столбца и преобразования базисного решения аналогичны стандартной симплекс-процедуре. [c.31]
Определяется вектор-симплекс множителей [c.32]
Исходная задача (2.28) в результате фиксации варьируемых векторов RJ на некоторых- номинальных значениях К° может быть приведена к обычной задаче линейного программирования с фиксированными параметрами. Далее стандартной симплекс-процедурой осуществляется решение задачи с фиксированными параметрами. На f-й итерации выявляется несовместность системы ограничений (2.28) при номинальных значениях Rj = Rj. В этом случае базисное решение 1- итерации [c.33]
Первый способ. 1. Определяется вектор симплекс-множителей П. На первой итерации вектор П равен вектору симплекс-множителей задачи (2.34) на последней итерации. На последующих итерациях П находится из выражения П =сВ 1. [c.34]
Основное преимущество рассмотренных модификаций общей расчетной процедуры — уменьшение числа подзадач, решаемых на каждой итерации (в ряде случаев — до одной) недостатком является то, что не исключена возможность необходимости возврата после ряда итераций к подзадаче, отброшенной" на начальной стадии расчета. В связи с этим после перебора всех подзадач необходимо осуществить контрольную проверку относительных оценок подзадач с учетом значений симплекс-множителей, определенных на последней итерации. Более того, данную процедуру следует осуществить и для небазисных столбцов RJ (/>Л1), поскольку не исключена возможность того, что после учета условий варьируемо-сти, в результате изменения соотношений технологических процессов, некоторый небазисный процесс может стать базисным. [c.35]
Оптимизация компаундирования значительно повышает рентабельность продукции при полном использовании запасов компонентов. Но для получения таких результатов необходимо обеспечить быстроту расчетов, что возможно только при применении ЭЦВМ. Решение простейшего варианта задачи о смешении симплекс-методом вручную продолжается около 15 дней, тогда как решение более сложной задачи на ЭЦВМ при наличии готовой [c.135]
Рассмотренный метод оптимизации производственной программы. НПЗ в постановке (2)—(9)-реализован на ЭВМ М-22 . Ниже приводится общая схема вычисления по данному методу. Условия (4)—(8) формируются в виде отдельного. информационного массива. Он используется только при решении вспомогательной задачи (12). Основой предлагаемой вычислительной схемы является алгоритм мультипликативного симплекс-метода, к которому стыкуются алгоритмы решения вспомогательной задачи и усреднения. Для решения вспомогательнбй задачи может использоваться основная программа. Однако в связи/с ее небольшими размерами был разработан и реализован на ЭВМ более экономный прямой алгоритм симплекс метода с верхними ограничениями на переменные. Следует отметить, что предлагаемый подход может реализован и другой вычислительной схемой, отличной от приводимой ниже. Ее отличие состоит в том, что алгоритм решения вспомогательной задачи.подключается только после получения оптимального решения, основной задачи. Практическая проверка обеих вычислительных схем не показала существенного преимущества ни одной из них. [c.100]
На /-и итерации процедуры исходной информацией шага а) является положительный вектор весов X = Х15. .., Я ]. Задача (3.9) решается с помощью симплекс-метода ее решение, обозначаемое х1, используется для построения вспомогательной информации, которая состоит в расчете значений вектора критериев в соседних с х вершинах многогранного множества (3.7). При этом рассматриваются только те вершины, которые принадлежат эффективному множеству решений. Пусть на Z-й итерации таких вершин <7гштук. Тогда строится qi векторов F(xlv , где xp(p=i,...,qi)— указанные вершины на Z-й итерации. Если какая-либо из вершин уже рассматривалась ранее, она исключается из рассмотрения. - На шаге б) процедуры ЛПР оценивает каждый из векторов F(XP), сравнивая его с F(x ). При этом ЛПР дает ответ да , нет или не знаю на вопрос о том, желателен ли переход в предлагаемую вершину. Эти ответы позволяют разбить множество [c.307]
AB D, содержащий все выпуклые комбинации этих точек (он заштрихован на рис. 6.9), содержит и неэффективные точки. Среди методов построения эффективных вершин можно выделить два основных направления. Это методы взвешивания и многокритериальные симплекс-методы. [c.310]
Чувилина А. Я. Программа решения на ЭВМ М-20 модифицированного симплекса для линейных задач с двусторонними ограничениями на переменные.— В кн. Руководство к использованию программ решения задач линейного программирования на ЭВМ М-20 и БЭСМ-4. Под ред. А. А. Тюни-на. Новосибирск. 1970, с. 140—154 (Ротапринт). [c.141]
Становление современного математического аппарата оптимальных экономических решений началось в 40-е годы, благодаря первым работам Н. Винера, Р. Беллмана, С. Джонсона, Л. Канторовича. Задача линейного программирования впервые математически сформулирована Л. В. Канторовичем в 1939 г. на примере задачи раскроя материалов для Ленинградского фанерного треста. В 1947 г. Дж. Данциг предложил универсальный алгоритм решения задач линейного программирования, названный им симплекс-методом. В 1941 г. Хичкок и независимо от него в 1947 г. Купсман формулируют транспортную задачу, в 1945 г. Стиглер — задачу о диете. В 1952 г. было проведено первое успешное решение задачи линейного программирования на ЭВМ Sea в Национальном бюро стандартов США. [c.102]