Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c).
Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Целью данной курсовой работы является нахождения решения задач симплекс методом.
Задачи курсовой работы:
Изучить что такое симплекс-метод, Рассмотреть методы решения, Рассмотреть решение задачи
1. Теоретические основы линейного программирования, .1 Что такое линейное программирование
Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.
Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:
- математические модели очень большого числа экономических задач линейны относительно искомых переменных;
эти типы задач в настоящее время наиболее изучены;
- для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
- многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
— некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Разработка модели и решение задачи линейного программирования ...
... линейны. Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций ...
Линейное программирование
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
систему ограничений
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования ( ЗЛП ) является выбор из множества допустимых планов наиболее выгодного (оптимального).
В общей постановке задача линейного программирования выглядит следующим образом:
х = (х1, х2, … хn)
1.2 Симплекс-0метод, Симплекс-метод
канонической форме
любую совместную систему
базисными
Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.
1.3Пример решения линейного уравнения симплекс-методом
линейный симплекс уравнение
любую совместную систему
базисными
Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.
Задача: Решение задач по Макроэкономике
... на бизнес 58 Прочие выплаты 0,5 Решение: Все данные, приведенные в условии задачи, относятся либо к числу статей доходов ... платежи). Импорт – это приобретение у иностранного контрагента товара с ввозом его в страну из за границы. Чистые инвестиции ... 390 Индивидуальные налоги 590 Решение: Данные, представленные в задании, позволяют рассчитать ВНП по расходам или по доходам. Используя первый ...
Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.
систему ограничений
допустимым
Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
недопустимым
Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.
При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.
Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Вычисления по симплекс-методу
X1, X2,…, Xr
1.4 Пример составления симплекс-таблицы
Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенств:
Далее эта система оформляется в виде симплекс-таблиц:
Примечание., Порядок работы с симплекс таблицей
Первая симплекс-таблица подвергается преобразованию, суть которого заключается в переходе к новому опорному решению.
Алгоритм перехода к следующей таблице такой:
последняя строка
столбец таблицы
коэффициент
базисная переменная
каждый элемент ключевой строки
строка разрешающего элемента делится
- в новой таблице все элементы ключевого столбца = 0 , кроме разрезающего , он всегда равен 1 .
- столбец , у которого в ключевой строке имеется 0 , в новой таблице будет таким же .
- строка , у которой в ключевом столбце имеется 0 , в новой таблице будет такой же .
- в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы :
В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.
Применение линейного программирования для решения экономических ...
... в экономике. Основной целью написания курсовой работы является всесторонний анализ применения линейного программирования для решения экономических задач. Задачами курсовой работы являются: 1. Теоретико-методическое описание метода линейного программирования; 2. Выявление области применения и ограничения использования линейного программирования для решения экономических задач; 3. ...
строку целевой функции
Рассмотрим порядок решения задачи с помощью симплекс-таблиц на примере.
Если в только что рассмотренной задаче первое же полученное без всякого труда базисное решение оказалось допустимым, то в ряде задач исходное базисное решение может иметь одну, две и т.д. отрицательных компонент, т.е. быть недопустимым. В таких задачах надо сначала применить первый этап симплексного метода, т.е. с его помощью найти какое-либо допустимое решение (или установить несовместность системы ограничений), а затем уже искать оптимальное решение (сделать вывод о противоречии условий задачи).
При этом надо помнить, что на первом этапе применения симплексного метода, т.е. пока мы ищем допустимое базисное решение, линейная форма не рассматривается, а все преобразования относятся только к системе ограничений.
Пусть задача линейного программирования задана в канонической форме, состоящей из m независимых уравнений с n переменными (или же она приведена к такому виду после введения добавочных неотрицательных переменных).
Выберем группу m основных переменных, которые позволяют найти исходное базисное решение (не нарушая общности, можем считать, что основными переменными являются первые m переменных).
Выразив эти основные переменные через неосновные, получим следующую систему ограничений:
k1, k2,…, km, 0, 0,…, 0
По предположению исходное базисное решение недопустимо. Следовательно, среди свободных членов системы ограничений (2.16) имеется хотя бы один отрицательный (число отрицательных свободных членов этой системы совпадает с числом отрицательных компонент исходного базисного решения).
Пусть им является свободный член i -го уравнения ki, т.е. основная переменная xi в соответствующем базисном решении отрицательна.
Для перехода к новому базисному решению необходимо: выбрать переменную, которую следует перевести из неосновных в основные; установить, какая основная переменная при этом перейдет в число неосновных переменных. При переводе неосновной переменной в основные ее значение, как правило, возрастает: вместо нуля в исходном базисном решении оно будет положительно в новом базисном решении (исключая случай вырождения).
Вернемся к i -му уравнению системы (2.16), содержащему отрицательный свободный член k1 . Оно показывает, что значение переменной xi растет при возрастании значений тех неосновных переменных, которые в этом уравнении имеют положительные коэффициенты. Отсюда следует, что в основные можно переводить те неосновные переменные, которые в уравнении системы (2.16) с отрицательным свободным членом имеют положительные коэффициенты.
Здесь может быть три исхода:
1. в i -м уравнении системы (2.16) нет основных переменных с положительными коэффициентами, т.е. все коэффициенты bi, m+j (как и свободный член ki ) отрицательны. В этом случае система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального;
Задачи на издержки производства с решением по экономике
... Задачи на издержки производства с решением по экономике В помощь студентам и аспирантам 1 задача. Прибыль рассчитывается как разница выручки и издержек. Издержки предприятия Общие издержки ... переменные издержки, средние издержки, средние постоянные и средние переменные издержки. Общие издержки (ТС) = 50000000 р. Объем производства (Q) = 20 шт. Постоянные издержки (FC) = 20000 р. Переменные издержки ...
2. в i -м уравнения имеется одна переменная xm+j, коэффициент b при которой положителен. В этом случае именно эта переменная переводится в основные;
- в i -м уравнении имеется несколько переменных с положительными коэффициентами bi, m+j. В этом случае в основные можно перевести любую из них.
Далее необходимо установить, какая основная переменная должна быть переведена в число неосновных на место переводимой в основные. В неосновные переводится та основная переменная, которая первой обратится в нуль при возрастании от нуля неосновной переменной, переводимой в основные. Иными словами, пользуемся тем же правилом, которое было установлено ранее. Находятся отношения свободных членов к коэффициентам при переменной, переводимой в основные, из всех уравнений, где знаки свободных членов и указанных коэффициентов противоположны, берется абсолютная величина этих отношений и из них выбирается наименьшая (если в некоторых уравнениях знаки свободных членов и указанных коэффициентов совпадают или в каких-то уравнениях переменная, переводимая в основные, отсутствует, то указанное отношение считается равным).
Уравнение, из которого получено наименьшее отношение, выделяется. Выделенное уравнение и покажет, какая из основных переменных должна быть переведена в неосновные. Выразив новые основные переменные через неосновные, перейдем к следующему базисному решению.
Если выделенным окажется уравнение с отрицательным свободным членом, то в новом базисном решении число отрицательных компонент будет на единицу меньше, чем в исходном. Если же выделенным окажется уравнение с положительным (или равным нулю) свободным членом, то в новом базисном решении число отрицательных компонент сохранится таким же, каким оно было в исходном базисном решении.
Таким образом, при переходе к новому базисному решению выгодно, чтобы выделенным оказалось уравнение с отрицательным свободным членом, и если есть возможность выбора, то предпочтение следует отдать такому обмену переменных, при котором выделенным оказывается уравнение с отрицательным свободным членом.
Итак, мы получим новое, улучшенное базисное решение, которое ближе к области допустимых решений системы ограничений. Если оно недопустимое, то к нему следует применить ту же схему еще раз. В результате через конечное число шагов мы получим допустимое базисное решение. Как только будет найдено допустимое базисное решение, переходят ко второму этапу симплексного метода, сущность которого рассмотрена при решении задачи
После овладения способом нахождения первого допустимого базисного решения любая задача линейного программирования может иметь трудности лишь вычислительного характера.
2. Алгоритм симплекс-метода, Усиленная постановка задачи
Рассмотрим следующую задачу линейного программирования:
Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:
Здесь x — переменные из исходного линейного функционала, x s — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства и в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «непростыми». Остальные переменные при этом будут вычисляться однозначно и называться «простыми». Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать непростыми, а все новые будем считать простыми. При этом начальное допустимое решение вычисляется однозначно:.
Метод решения многомерной задачи оптимального управления динамикой ...
... оптимальной траектории. Значение научных результатов для практики На основе построенного алгоритма разработан программный комплекс в среде Borland Delphi 7.0, который может быть использован для решения задач оптимального управления экономической системой ... значений управляющих переменных. 2. Новый аналитический метод решения задачи оптимального управления макроэкономической системой, ... теории функций ...
Алгоритм
Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:
где c B — коэффициенты вектора c соответствующие простым переменным (переменным xs соответствуют 0), B — столбцы, соответствующие простым переменным. Матрицу, образованную оставшимися столбцами обозначим D. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.
Первый шаг
s . cB — нулевой вектор по тем же причинам.
Второй шаг
Покажем, что в выражении только непростые переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b простые переменные однозначно выражаются через непростые, так как число простых переменных равно числу уравнений. Пусть x ‘ — простые, а x ‘ ‘ — непростые переменные на данной итерации. Уравнение Ax+xs=b можно переписать, как Bx ‘+Dx ‘ ‘=b. Умножим его на слева: Таким образом мы выразили простые переменные через непростые, и в выражении, эквивалентному левой части равенства, все простые переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству равенство, то в полученном равенстве все простые переменные будут иметь нулевой коэффициент — все простые переменные вида x сократятся, а простые переменные вида xs не войдут в выражение.
Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение
Для этого выберем переменную, которая имеет наибольший по модулю отрицательный коэффициент. Если таких переменных нет, то есть все коэффициенты этого выражения неотрицательны, то мы пришли в искомую вершину и нашли оптимальное решение. В противном случае начнём увеличивать эту непростую переменную, то есть перемещаться по соответствующему ей ребру. Эту переменную назовём входящей.
Использование информатики для решения экономических задач
... со значениями и формулами. />; />Задание № 4 Решить задачу линейного программирования. Отчет долженсодержать следующие разделы: Условие задачи Формализация задачи Графическое решение задачи Распечатку решения задачи с помощью пакета Microsoft Excel Экономический вывод ... D E F G H 1 Переменные 2 x1 x2 3 Значения 2000 3000 4 Нижняя граница 1000 5 Решение 6 Коэффициенты целевой функции 23 12 ...
Третий шаг
Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:
При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в простую, а выходящая из них «выйдет» в непростые. Теперь перепишем матрицу B и вектор c B в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. x»
Поскольку число вершин, конечно, то алгоритм однажды закончится. Найденная вершина будет являться оптимальным решением.
3. Двухфазный симплекс-метод, Причины использования
Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «?», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат.
Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация.
Модификация ограничений
Все ограничения задачи модифицируются согласно следующим правилам:
— ограничения типа «?» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.
— ограничения типа «?» дополняются одной переменной с коэффициентом «?1 ». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную , переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».
ограничения типа «=» дополняются одной вспомогательной переменной.
Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым.
Различия между дополнительными и вспомогательными переменными
Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:
- дополнительные переменные сообщают, насколько соответствующее им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству значений правых и левых частей ограничения.
— вспомогательные переменные сообщают, насколько данное условие далеко от допустимого (относительно конкретного ограничения).
Если значение вспомогательной переменной больше нуля, то данное решение не выполняет определённое ограничение, а значит не является допустимым.
Взаимосвязи экономических переменных
... модель регрессия гиперболическая параболическая Для определения значений теоретических коэффициентов регрессии необходимо знать и использовать все значения переменных х и у генеральной совокупности, что ... брака литья Х (т), т.к. автокорреляция остатков отсутствует, коэффициенты значимы, связь сильная, но модель неприемлема для прогнозирования. 2. Гиперболическая модель регрессии Гиперболическая ...
То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.
Фазы решения
вспомогательная целевая функция
После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Поскольку все вспомогательные переменные увеличивают значение, в ходе алгоритма они будут поочерёдно выводится из базиса, при этом после каждого перехода новое решение будет всё ближе к множеству допустимых решений.
Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:
— оптимальное значение больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует.
- оптимальное значение равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым.
Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные. Это и является второй фазой решения.
4. Модифицированный симплекс-метод
В модифицированном методе матрица
не пересчитывается, хранится и пересчитывается только матрица. В остальном алгоритм похож на вышеописанный.
- Вычисляем двойственные переменные
преобразуется в.
для всех столбцов. Столбец со значением < 0 можно вводить в базис.
Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.
Чаще выбирают значение, меньшее некоторого заданного значения
Если такого столбца не обнаружится, за принимается максимальное найденное абсолютное значение и соответствующий столбец вводится в базис.
- Определение выводимого.
Пусть — вводимый столбец, соответствующий переменной Базиный план — это решение системы Увеличиваем.
Умножим слева на, т.е.
- базисный план, — разложение вводимого столбца по базису.
Находим максимальное значение, при котором все значения не отрицательны. Если может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.
- Пересчет опорного(базисного) плана.
с найденным значением.
- Пересчитываем обратную к базисной.
- выводимый столбец.
Матрица B представима в виде
Методы оптимальных решений краткий
... типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание. Сейчас лишь сформулируем их в терминах ЗЛП, а методы решения подобных задач рассмотрим ниже. 1. Задача об оптимальном использовании ресурсов при ...
- базисная матрица без выводимого столбца.
После замены столбца базисная матрица будет иметь вид
Нам нужно найти матрицу, такую что
=> => =>
Откуда
Замечание.
При пересчете матрицы накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».
Мультипликативный вариант симплекс-метода
не хранится, хранятся лишь множители
При решении экономических задач часто матрица ограничений разреженная, в таком случае мультипликативный вариант получает дополнительные преимущества — можно хранить мультипликаторы в сжатом виде (не хранить нули).
5. Другие варианты симплекс-метода
Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.
метод переменного базиса
Метод основан на том, что базисная матрица может быть представлена в виде
Обратная к ней имеет вид
остальная часть матрицы может не храниться.
Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).
Двойственный симплекс-метод
Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путем транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:
при ограничениях
Теорема двойственности
Если линейная функция одной из задач не ограничена, то другая не имеет решения.
