С учетом возможностей современных ППП, использующих модифицированный симплекс-метод с мультипликативным представлением матрицы, отнесение очередного вектора к классу векторов, обеспечивающих совместность или несовместность, требует проведения всего нескольких итераций после модификации обобщенной матрицы
МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
Вычислительная схема, основанная на преобразовании обратных матриц. Анализируя вычислительную процедуру симплекс-метода с позиций оценки трудоемкости, нетрудно заметить, что наиболее критичным в этом плане является э ап пересчета значений А и b при переходе от одного базисного плана к другому (п. 3 алгоритма). Однако в том случае, когда число ограничений задачи m явно меньше количества переменных я, можно добиться существенной экономии, выполняя на очередной итерации q преобразование Жордана-Гаусса не над матрицей Л(р() по Д Чр(ведущий столбец аЧр О. Данные соображения положены в основу вычислительной схемы симплекс-метода , основанной на преобразовании обратных матриц, которую также называют модифицированным симплекс-методом. Впервые данный алгоритм был предложен в 1951 г. в работах Л. В. Канторовича.
Вычислительной схеме модифицированного симплекс-метода соответствует система таблиц 7] и T q). Таблица 7J (рис. 1.7) является общей для всех итераций и служит для получения
По аналогии с п. 1.4.1 опишем формальную схему алгоритма модифицированного симплекс-метода.
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный симплекс-метод реально применяется в программном обеспечении , предназначенном для решения канонических задач линейного программирования.
Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3
Еще раз вернемся к таблице Т (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс--метода. Более подробно рассмотрим нулевую строку матрицы A 4p(
Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи.
В заключение отметим, что в настоящем параграфе был рассмотрен вариант двойственного алгоритма, соответствующий стандартному симплекс-методу . Нетрудно догадаться, что существует и вариант, построенный на базе модифицированного симплекса (схемы, связанной с преобразованием обратных матриц), но, поскольку этот вопрос представляет интерес в основном с точки зрения техники организации вычислений, мы на нем останавливаться не будем. При желании с глубоким и детальным описанием данной версии алгоритма можно ознакомиться в . Отметим лишь, что она обладает теми же принципиальными преимуществами, что и модифицированный симплекс-метод.
Модифицированный симплекс-метод - вычислительная схема, связанная с преобразованием обратных матриц.
Сформулируйте основные отличия модифицированного симплекс-метода по отношению к стандартному.
Перечислите преимущества модифицированного симплекс-метода.
Будет ли отличаться количество итераций при решении одной и той же задачи при решении ее стандартным и модифицированным симплекс-методом
Метод разложения (декомпозиции) был разработан для решения задач линейного программирования большой размерности, имеющих блочную структуру. Его вычислительная процедура главным образом основана на идеях модифицированного симплекс-метода. Однако значение метода Данцига-Вулфа состоит не только и (не столько) в его вычислительных преимуществах, сколько в возможности дать содержательную экономическую интерпретацию . Метод предусматривает разложение исходной задачи (5.6)-(5.9) на локальные задачи, соответствующие обособленным частям объединения (в данном случае предприятиям), и главную задачу (соответствует объединению в целом и связывает эти локальные задачи).
Р. Б. Д у б и н а, К. Е. Ч е р н и н. Программа образования и записи на М. Б. матрицы для модифицированного симплекс-метода.- Сборник программ для ЭВМ Урал. Л., Аркт. и антаркт. ин-т, 1966.
Среди методов нахождения оптимального решения наибольшее распространение приобрёл метод последо -ват. улучшения допустимого решения (МНУ), к-рый имеет большое число вычислит, реализаций (
3. Модифицированный симплекс-метод
В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.
В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.
В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс – разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана – Гаусса. Особенности заключаются в наличии двух таблиц – основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.
Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи.
Таким образом, процесс нахождения решения задачи нелинейного программирования включает следующие этапы:
1. Первоначальную задачу сводят к задаче линейного программирования.
2. Находят решение линейной задачи
Используя соотношения, определяют оптимальный план исходной задачи и находят максимальное значение целевой функции нелинейной задачи.
Первый этап: Получение задания к курсовой работе
1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра:
Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:
из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а – том столбце в строке 9, b – том столбце в строке 5, c – том столбце в строке 5, d – том столбце в строке 8, e – том столбце в строке 7и f – том столбце в строке 2.
По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания. В моем случае для цифры 9 соответствует вариант 9.
На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами:
где С i и - постоянные величины, i = 1, 2, 3;
X 1 – трудовые ресурсы в человеко-днях;
Х 2 – денежно-материальные средства, в тенге;
У i – получаемый продукт
Х 1 = а 1 х 1 + b 1 x 2 + c 1 x 3
Х 2 = а 2 х 1 + b 2 x 2 + c 2 x 3
Найти все неотрицательные базисные решения и определить оптимальный план F = y 1 + y 2 + y 3 .
Известно, что продукт для производства j – того вида затрачивается a ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10
Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.
2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица:
| Продукты ресурсы | |||
| I | 8 | 4 | 6 |
| II | 160 | 240 | 200 |
3. По столбцу c – на 3 строке находим с 1 =6, α 1 =0,6
4. По столбцу d – на 5 строке определяем с 2 =5, α 2 =0,5
5. По столбцу e – по 4 строке установим, что с 3 =8, α 3 =0,4.
6. И наконец по столбцу f – в 1 строке найдем Т чел.дней =1000, П тенге = 280000
Для производства имеются трудовые ресурсы Т чел.дней и денежно-материальные средства П тенге.
Требуется найти оптимальный план выпуска продукции, при котором выпускаемый продукт будет наибольшим.
Второй этап – составление математической модели задачи
1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:
| Продукты ресурсы | ||||
| I | 8 | 4 | 6 | 1000 |
| II | 160 | 240 | 200 | 280000 |
Через Х 1 обозначим ресурсы I вида.
Через Х 2 обозначим ресурсы II вида.
2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.
8Х 1 + 4Х 2 + 6Х 3 ≤ 1000
240Х 1 + 200Х 2 + 160Х 3 ≤ 280000
Таким образом, получили задачу нелинейного программирования. Такие задачи называются задачами нелинейного программирования.
Решение задач нелинейного программирования осуществляется приведением их к задачам линейного программирования.
Для решения задачи линейного программирования применяется симплекс – метод.
Третий этап – выбор метода решения полученной математической задачи
1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:
8Х 1 + 4Х 2 + 6Х 3 + Х 4 = 1000
240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000
Разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах...
Нахождение точки Куна-Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать при ограничениях С помощью теоремы 2 докажем, что решение является оптимальным. Имеем Так...
Лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...
Положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой...
В модифицированном методе матрица
не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный.
1. Вычисляем двойственные переменные
2. Проверка оптимальности. преобразуется в.
Проверка заключается в вычислении для всех столбцов. Столбец со значением < 0 можно вводить в базис.
Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.
Чаще выбирают значение, меньшее некоторого заданного значения
Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис.
3. Определение выводимого.
Пусть - вводимый столбец, соответствующий переменной Базиный план - это решение системы Увеличиваем.
Умножим слева на, т.е.
Здесь - базисный план, - разложение вводимого столбца по базису.
Находим максимальное значение, при котором все значения не отрицательны. Если может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.
4. Пересчет опорного(базисного) плана.
Вычисляем новый опорный план по уже приведенной формуле с найденным значением.
5. Пересчитываем обратную к базисной.
Пусть - выводимый столбец.
Матрица B представима в виде
где - базисная матрица без выводимого столбца.
После замены столбца базисная матрица будет иметь вид
Нам нужно найти матрицу, такую что
Замечание.
При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».
Мультипликативный вариант симплекс-метода
В мультипликативном варианте матрица не хранится, хранятся лишь множители
При решении экономических задач часто матрица ограничений разреженная, в таком случае мультипликативный вариант получает дополнительные преимущества - можно хранить мультипликаторы в сжатом виде (не хранить нули).
Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.
При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса .
Метод основан на том, что базисная матрица может быть представлена в виде
Обратная к ней имеет вид
При относительно небольших размерах матрицы остальная часть матрицы может не храниться.
Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).
Двойственный симплекс-метод
Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:
при ограничениях
Теорема двойственности . Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем экстремальные значения линейных функций этих задач равны.
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Геометрический способ решения стандартных задач линейного программирования с двумя переменными. Универсальный метод решения канонической задачи. Основная идея симплекс-метода, реализация на примере. Табличная реализация простого симплекс-метода.
реферат , добавлен 15.06.2010
Виды задач линейного программирования и формулировка задачи. Сущность оптимизации как раздела математики и характеристика основных методов решения задач. Понятие симплекс-метода, реальные прикладные задачи. Алгоритм и этапы решения транспортной задачи.
курсовая работа , добавлен 17.02.2010
Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа , добавлен 15.08.2012
Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа , добавлен 18.02.2014
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа , добавлен 11.05.2014
Основы математического моделирования экономических процессов. Общая характеристика графического и симплексного методов решения прямой и двойственной задач линейного программирования. Особенности формулирования и методика решения транспортной задачи.
курсовая работа , добавлен 12.11.2010
Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа , добавлен 01.06.2014
Для решения задач линейного программирования существует множество методов. Рассмотрим один из них улучшенный (модифицированный) симплекс-метод
Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.
Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.
Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.
В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.
Одним из модификаций симплекс-метода является улучшенный симплекс-метод. В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.
В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A -1 , обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису A x .
Рассмотрим поэтапно шаги решения задачи линейного программирования улучшенным симплекс-методом:
j = c j -- = c j -- P j , (2)
где - двойственные переменные, которые можно найти следующим образом:
где c x - вектор коэффициентов целевой функции при базисных переменных.
3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим:
= (, ...,) . (2.4)
Если все 0 - процедура останавливается: оптимум неограничен.
7. В противном случае находим выводимую из базиса переменную:
8. Строим увеличенную матрицу:
и трансформируем ее с ведущим элементом. Первые m столбцов дают матрицу, обратную новому базису.
9. Преобразуем базисное решение:
x b i x b i -- * , i r, (2.7)
и переходим к этапу 2.
Этот вариант называют также модифицированным симплекс-методом, поскольку он уменьшает объем вычислений на каждом шаге. Идея заключается в том, что на каждом шаге каноническую форму задачи для текущего базиса можно получить независимо от других таких форм непосредственно из исходной записи стандартной задачи ЛП.
Для этого нужно:
Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабо заполненными, содержат малый процент ненулевых элементов.
Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабо заполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.
В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабо заполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом, время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль.
