Реферат симплекс метод решения задач линейного программирования

Обновлено: 05.07.2024

Симплексный метод линейного программирования относится к универсальным методам, обеспечивающим эффективное решение разнообразных землеустроительных и других экономических задач. Универсальность данного метода проявляется в том, что он позволяет решать задачи различной размерности, в которых технико-экономические коэффициенты (α_ij) при переменных (Х_ij) выражены в разных единицах измерения.

Сущность симплексного метода заключается в нахождении оптимального решения задачи путем последовательного рассмотрения и анализа ее допустимых базисных решений. Геометрически каждое допустимое базисное решение соответствует одной из вершин многоугольника в n–мерном пространстве ограничивающего в соответствии с условиями задачи область допустимых решений (ОДР).

В процессе решения задачи на каждой итерации осуществляется переход из одной вершины ОДР в смежную, связанную с не худшим значением целевой функции. Для этого используется процедура метода главных элементов. Количество итераций, необходимых для получения оптимального решения, находится в пределах от m до 2m, где m-количество ограничений в задаче.

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

при условиях: /i=1,2,…m/ (3.2)

Если подробно описать все условия задачи в виде системы неравенств и уравнений, то такая экономико-математическая модель называется развернутой.

В зависимости от сложности решаемых задач экономико-математические модели могут иметь разные размеры, которые определяются произведением количества ограничений на количество переменных (m∙n).

3.1 РЕШЕНИЕ ЗАДАЧ ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

Экономико-математические модели линейного программирования структурно состоят из трех частей: целевой функции, системы ограничений и условия не отрицательности переменных. Целевая функция выражает основное условие задачи, критерий её оптимальности, ориентированный на максимум или на минимум.

Система ограничений в экономико-математических моделях задач, решаемых симплексным методом, записывается в стандартной форме, т.е. в виде неравенств и уравнений. В зависимости от типа ограничений задачи решаются по алгоритму симплексного метода, или алгоритму данного метода с искусственным базисом.

Рассмотрим алгоритм решения задач симплексным методом, который применяется и при решении задач с искусственным базисом за исключением некоторых особенностей алгоритма на начальных этапах их решения.

Методика решения задач симплексным методом предусматривает соблюдение следующих этапов их решения:

1. Постановка задачи;

2. Составление экономико-математические модели задачи;

3. Составление исходного плана (первой симплексной таблицы);

4. Анализ плана на оптимальность;

5. Улучшение плана;

6. Контроль правильности решения задачи;

7. Анализ оптимального решения задачи и формулирование ответа.

Для более наглядного представления алгоритма симплексного метода решим задачу, выраженную в условных единицах измерения.

1. Постановка задачи

При постановке задачи формулируется (словесно): оптимальные значения, каких неизвестных необходимо найти, при каких условиях (ограничениях) по видам и размерам ресурсов, какая функция цели и на что она ориентирована (на максимум или минимум). Например, необходимо определить оптимальное сочетание объемов производства трех видов продукции (Х₁, Х₂, Х₃) при имеющихся в хозяйстве трех видах ресурсов в размере в₁=100, в₂=40, в₃=50 (это могут быть трудовые ресурсы, удобрения, капиталовложения и т.п.) с целью получения максимальной денежной выручки (или валовой продукции и т.п.).

2. Составление экономико-математические модели задачи

Экономико-математическая модель в симплексном методе составляется в следующей последовательности:

- записывается уравнение функции цели, правая часть которого представляет собой сумму произведений искомых неизвестных (Х₁, Х₂, Х₃) на соответствующие им по условиям задачи коэффициенты целевой функции:

- условия задачи записываются в виде неравенств с ограничениями типа ≤. Каждое из неравенств выражает собой ограничения по одному из видов ресурсов, поэтому в левой части неравенства проставляют искомые переменные с коэффициентами, выражающими расход данного вида ресурса на единицу искомой переменной или, наоборот, выход данного вида ресурса с единицы соответствующей переменной. В правой части неравенства проставляется тип ограничения ≤ и величина соответствующего вида ресурса;

- количество неравенств в системе ограничений обусловлено условиями задачи. При записи неравенств необходимо контролировать правильность их оформления: технико-экономические коэффициенты при переменных, состав переменных (в левой части неравенства), вид и размер ресурса (в правой части неравенства) должны строго соответствовать условиям задачи и характеру её постановки.

Таким образом, система ограничений выглядит следующим образом:

- после записи основных условий задачи в виде системы ограничений обязательно формулируется условие не отрицательности переменных, так как алгоритм симплексного метода позволяет решать задачи только с положительными значениями переменных (Х_j):

Представленная выше форма записи условий задачи в виде неравенств называется стандартной. Для заполнения первой симплексной таблицы (исходного плана) необходимо перейти от стандартной формы записи условий задачи к канонической, а от неё – к симплексной.

Преобразуем приведенную выше систему неравенств в систему уравнений:

Для дальнейшего преобразования канонической формы записи в симплексную система уравнений решается относительно дополнительных переменных:

Исходя из симплексной формы записи условий задачи, становится ясен экономический смысл дополнительных переменных. На начальном этапе решения задачи принимается условие, что основные переменные равны нулю, а значения дополнительных переменных, исходя из симплексной формы записи, будут равны величинам ресурсов. В нашем примере: при Х₁=0, Х₂=0, Х₃=0 будем иметь Х₄=100, Х₅=40, Х₆=50.

В экономическом отношении это означает, что пока не реализовано ни одно из мероприятий, намечаемых по условиям задачи, ресурсы остаются неиспользованными. Исходя из данной установки, создается исходный базис (исходное условие), на основе которого начинается поиск оптимального решения задачи из числа допустимых её решений.

Если в системе уравнений отражающих условие задачи, количество переменных (n) больше количества ограничений (m), то система имеет множество решений. При этом допустимым решением системы называется любой набор переменных, удовлетворяющих условиям задачи, а допустимым базисным решением – допустимое решение, содержащее не больше, чем m не нулевых переменных. Поэтому первая симплексная таблица (исходный план) содержит допустимое базисное решение задачи. Рассмотрим порядок заполнения первой симплексной таблицы (таблица 3.1).

3. Составление исходного плана (первой симплексной таблицы)

Содержание первой симплексной таблицы и порядок её заполнения рассмотрим последовательно по столбцам и строкам.

Столбец 1 – приводится нумерация строк, соответствующая нумерации ограничений в задаче.

Столбец 2 – записывается только дополнительные переменные (Х₄, Х₅, Х₆), т.к. они составляют исходный базис для начала решения задачи.

Столбец 3 – записываются коэффициенты целевой функции при дополнительных переменных, вошедших в базис. Они равны нулю, т.к. дополнительные переменные (Х₄, Х₅, Х₆), вошедшие в базис, в целевую функцию введены с нулевыми коэффициентами (С_ij =0) для исключения влияния дополнительных переменных на величину функции цели (Z).

Столбец 4 – записывается значение ресурсов (свободных членов), стоящих в правой части соответствующего неравенства (уравнения). Исходя из симплексной формы записи условий рассматриваемой задачи дополнительные переменные, вошедшие в базис, выражают неиспользованные ресурсы, поэтому: Х₄=100, Х₅=40, Х₆=50. Следовательно, в столбец свободных членов (в_j) записываются исходные величины ресурсов.

Столбцы 5-7 – это столбцы основных переменных (соответственно, Х₁, Х₂, Х₃). В них на пересечении со строками соответствующих уравнений проставляются технико-экономические коэффициенты (а_ij), стоящие в данных уравнениях при каждой из основных переменных. Так, из первого уравнения (3.8) 3Х₁+5Х₂+8Х₃+Х₄=100 коэффициенты при основных переменных (Х₁, Х₂, Х₃), соответственно 3,5 и 8 занесены в столбцы данных переменных по первой строке таблицы (3.1).

Столбец 11 – в него записывается суммы, полученные путем сложения свободного члена (в_j) и коэффициентов (а_ij) по соответствующей строке таблицы. Так, если сложить по первой строке таблицы (3.1) свободный член и коэффициенты (100+3+5+8+1=117), то получим число 117, которое и записано в столбце 11. аналогичным образом получаем значения для столбца 11 и по остальным строкам таблицы.

Столбец 12 – в него записываются значения, полученные в результате построчного деления значений свободных членов (в_j) на положительные коэффициенты ключевого (k-го) столбца.

Для выполнения таких расчетов необходимо предварительно выбрать ключевой столбец (k–й столбец). В качестве ключевого (k-го) выбирается столбец (из числа столбцов основных переменных Х₁, Х₂, Х₃, т.е. столбцов 5-7), по которому в индексной (m+n) строке таблицы стоит максимальное по абсолютной величине: отрицательное число при решении задачи на максимум и, наоборот, положительное число, при решении задачи на минимум.

Теперь можно выполнить расчеты для заполнения столбца 12. По первой строке указанное отношение получаем, разделив свободный член 100 (в₁=100) на положительный коэффициент 8 (в₁=8), стоящий по данной строке в ключевом столбце. Оно равно 12,5 ( ). Запишем его в таблицу 3.1.

Аналогично определяем остальные значения для столбца 12.

Значения, записываемые в столбце 12 служат, в последующем основанием для выбора ключевой строки (l-строки), используемой вместе с ключевым (k-столбцом) столбцом для получения следующей симплексной таблицы (улучшенного плана).

Столбец m+1 – это индексная строка симплексной таблицы. На пересечении m+1 строки и столбца основных членов в_i (столбец 4), записывается численное значение функции цели (Z). В первой симплексной таблице (3.1) оно равно нулю (Z=0).

Все остальные элементы индексной (m+1) строки рассчитываются по формуле:

где С_i – коэффициенты целевой функции при переменных, вошедших в базис;

C_j - коэффициенты целевой функции при переменных (Х_ij), по столбцам которых выполняется расчет;

а_ij – технико-экономические коэффициенты при переменных Х_j, стоящих в i-м ограничении.

Так, для столбца переменной Х₁ (столбец 3) элемент индексной строки будет рассчитан следующим образом:

Так же рассчитываются остальные элементы индексной строки (для столбцов 5-10). В столбец 11 проставляется сумма элементов по индексной строке (-60).

Заполненная первая симплексная таблица (3.1) представляет собой исходный план, который анализируется на оптимальность.

4. Анализ плана на оптимальность

Признаком оптимальности опорного (как исходного, так и последующих) плана является отсутствие в индексной (m+1) строке при решении задачи на минимум – положительных коэффициентов или нулей. Если это условие не выполняется, то план не оптимален и необходимо его улучшать.

В рассматриваемой задаче, решаемой на максимум, исходный план (таблица 3.1) не оптимален, т.к. в индексной строке имеются отрицательные коэффициенты (-20, -10, -30). В связи с этим его необходимо улучшать.

5. Улучшение плана

Новый, улучшенный план, получают на основе преобразования неоптимального плана. Вычислительная процедура улучшения плана заключается в выведении из базиса неоптимального плана одной из базисных переменных и введение в него новой, небазисной переменной. Для осуществления этой процедуры в неоптимальном (улучшаемом плане, т.е. в первой симплексной таблице) выбирают ключевой К-столбец и ключевую l-строку (таблица 3.1).

Ключевой столбец (К-столбец) выбирают, как было отмечено выше, по наибольшему по абсолютной величине: отрицательному коэффициенту индексной строки при решении задачи на максимум, и положительному коэффициенту при решении задачи на минимум.

В первой симплексной таблице (неоптимальном плане) в качестве ключевого нами выбран столбец переменной Х₃ (столбец 7), в котором по индексной строке стоит наибольший по абсолютной величине отрицательный коэффициент -30 (Z_max).

Ключевая строка (l-строка) выбирается по минимальному положительному коэффициенту, стоящему в столбце 12. В первой симплексной таблице рассматриваемой задачи в качестве ключевой l-строки выбрана вторая строка, по которой в столбце 12 стоит наименьший положительный коэффициент (6,67).

Коэффициент, стоящий на пересечении ключевой строки и ключевого столбца называется главным или генеральным элементом (a_lk).

Новую симплексную таблицу (улучшенный план) с новым базисным решением составляют в следующей последовательности:

- вычерчивают новую симплексную таблицу (3.2) по форме первой таблицы, добавляя столбец 13 (для контроля правильности вычислений). Вместо базисной переменной, стоявшей в базисе (столбец 2) по ключевой l-строке предыдущей таблицы в новую таблицу записывают переменную Х_j, столбец которой выбран в качестве ключевого. Этим самым в базис новой симплексной таблицы вводится новая базисная переменная, а прежняя – выводится из базиса;

- в столбец 3, рядом с новой переменной, введенной в базис, записывают её коэффициент целевой функции. Остальные базисные переменные и их коэффициенты целевой функции (столбцы 2 и 3) переписываются в новую таблицу из предыдущей без изменения;

- элементы ( ) для заполнения в новой таблице строки, стоящей на месте ключевой l-строки предыдущей таблицы, вычисляются как отношение соответствующего элемента (a_lj) ключевой l-строки на главный элемент (a_lk) предыдущей таблицы, т.е. по формуле:

, (3.15)

- элементы остальных строк новой симплексной таблицы, за исключением строки, стоящей на месте бывшей ключевой l-строки, пересчитываются по одной из следующих формул:

где , а_ij – однотипные коэффициенты, соответственно новой и предыдущей симплексной таблиц;

, а_lj – коэффициенты строки, стоящей в новой таблице на месте бывшей ключевой l-строки и, соответственно, коэффициенты ключевой l-строки в предыдущей таблице;

a_ik – коэффициенты ключевого К-столбца предыдущей симплексной таблицы;

a_lk – главный (генеральный) элемент предыдущей симплексной таблицы, стоящий на пересечении ключевых l-строки и К-столбца.

Расчеты по указанным выше формулам выполняются для заполнения всех строк новой симплексной таблицы, включая индексную (m+1) строку, но исключая ключевую l-строку.

В соответствии с вышеизложенным выполнены расчеты по улучшению первого и второго планов (таблицы 3.1 и 3.2) и получен оптимальный план (таблица 3.3).

Работа посвящена наиболее распространенному методу решения задачи линейного программирования (симплекс-методу). Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.

Сформулирован алгоритм решения задачи, который проиллюстрирован на примере.

Основное содержание симплексного метода заключается в следующем:

1. Указать способ нахождения оптимального опорного решения

2. Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения

3. Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.

2. Симплексный метод решения задач линейного программировани я

Симплексный метод решения задач линейного программирования (симплекс-метод) - вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице).

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, . Xr. Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, . Xr, то решение будет опорным при условии, что b1, b2. br ≥ 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям.

Реализация решения задачи симплекс-методом наглядно показана на блок-схеме (рис.1).

Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения. При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.

Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, . Xr и что при этом b1, b2. br ≥ 0 (соответствующее базисное решение является опорным).

Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенств:

Далее эта система оформляется в виде симплекс-таблиц:

Примечание. Названия базисных переменных здесь взяты лишь для определенности записи и в реальной таблице могут оказаться другими.

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

Алгоритм перехода к следующей таблице такой:

просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;

в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:

разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы;

строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место;

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1;

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же;

строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же;

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

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

3.Алгоритм симплексного метода решения задач линейного программирования

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду.

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости Привести системы ограничений).

3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода.

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

4.Пример решения задачи симплексным методом

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффицентом ноль (т.е. не входит).

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

Где Cб = (с1, с2, . , сm ) — вектор коэффициентов целевой функции при базисных переменных;

Xk = (x1k, x2k, . , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения;

Ск — коэффициент целевой функции при переменной хк.

Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу

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

В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные.

По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле:

Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (табл.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (табл.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (табл.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

5. Заключение

Решение задач линейного программирования – это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ. Табличный симплекс-метод хорошо приспособлен для программирования и машинного счета.

Существуют программные реализации симплекс-метода. В настоящее время появились интегрированные математические программные системы для научно-технических расчетов: Eureka, PCMatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.

Широкую известность и заслуженную популярность приобрели математические системы класса MathCAD, разработанные фирмой MathSoft (США). Это единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков

6.Список используемой литературы

1. Ашманов, С.А. Линейное программирование / С.А.Ашманов. – М.: Наука, 1981. – 304 с.

2. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология / Е.С.Вентцель. – М.: Высшая школа, 2001. – 208 с.

3. Гольдштейн, Е.Г. Линейное программирование: Теория, методы и приложения / Е.Г.Гольдштейн, Д.Б.Юдин. – М.: Наука, 1969. – 736 с.

4. Кофман, А. Методы и модели исследования операций / А.Кофман. – М.: Мир, 1966. – 523 с.

5. Силич, В.А. Системный анализ и исследование операций: учебное пособие / В.А. Силич, М.П. Силич. – Томск: Изд-во ТПУ, 2000. – 96 с.

6. Силич, В.А. Системный анализ экономической деятельности: учебное пособие / В.А.Силич. – Томск: Изд. ТПУ, 2001. – 97 с.

Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение

Содержание

Введение
Цель
1. Теоретические основы линейного программирования
1.1 Что такое линейное программирование
1.2 Симплекс-метод
1.3 Пример решения линейного уравнения симплекс-методом
1.4 Пример составления симплекс-таблицы
2. Алгоритм симплекс-метода
2.1 Усиленная постановка задачи
2.2 Алгоритм
3. Двухфазный симплекс-метод
3.1 Причины использования
3.2 Модификация ограничений
3.3 Различия между дополнительными и вспомогательными переменными
3.4 Фазы решения
4. Модифицированный симплекс-метод
4.1 Мультипликативный вариант симплекс-метода
5. Другие варианты симплекс-метода
5.1 Двойственный симплекс-метод
5.2 Теорема двойственности.
Заключение
Список используемой литературы

Прикрепленные файлы: 1 файл

Курсовая Симплекс.doc

1. Теоретические основы линейного программирования

1.1 Что такое линейное программирование

1.3 Пример решения линейного уравнения симплекс-методом

1.4 Пример составления симплекс-таблицы

2. Алгоритм симплекс-метода

2.1 Усиленная постановка задачи

2.2 Алгоритм

3. Двухфазный симплекс-метод

3.1 Причины использования

3.2 Модификация ограничений

3.3 Различия между дополнительными и вспомогательными переменными

3.4 Фазы решения

4. Модифицированный симплекс-метод

4.1 Мультипликативный вариант симплекс-метода

5. Другие варианты симплекс-метода

5.1 Двойственный симплекс-метод

5.2 Теорема двойственности.

Список используемой литературы

Введение

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение

W(x) = c, где W(x) - максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Целью данной курсовой работы является нахождения решения задач симплексным методом.

Задачи курсовой работы:

- Изучить что такое симплексный метод

- Рассмотреть методы решения

- Рассмотреть решение задачи

1. Теоретические основы линейного программирования.

1.1 Что такое линейное программирование

Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

· математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

· для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;

· многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;

· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.

Итак, Линейное программирование - это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х₁, х₂, … х_n) и функция этих переменных f(x) = f (х₁, х₂, … х_n), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G.

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X₁, X₂,…, X_r. Тогда наша система уравнений может быть записана как

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X₁, X₂,…, X_r, то решение 1, b₂,…, b_r, 0,…, 0> будет опорным при условии, что b₁, b₂,…, b_r ≥ 0.

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

1.3 Пример решения линейного уравнения симплекс-методом

линейный симплекс уравнение

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям. Его идея состоит в следующем.

Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m ограничений или установление факта ее несовместности; нахождение оптимального решения.

При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X₁, X₂,…, X_r и что при этом b₁, b₂,…, b_r ≥ 0 (соответствующее базисное решение является опорным).

1.4 Пример составления симплекс-таблицы

Цель данной курсовой работы: изучить и научиться применять на практике симплекс - метод для решения задач линейного программирования в случаи произвольных свободных членов. Задачи курсовой работы:
изучить теоретический материал;
на примерах рассмотреть симплекс метод.

Содержание работы

Введение 3
1 Симплекс-метод 5
1.1 Общая характеристика симплекс-метода 5
1.2 Общая идея симплексного метода 12
1.3 Симплекс-метод решения задачи линейного программирования 14
2 Решение задачи при помощи симплекс – метода 20
2.1 Постановка задачи 20
2.2 Решение поставленной задачи 21
2.3 Решение задачи при помощи табличного процессора Microsoft Excel 25
Список используемых источников 32
Приложение А – Решение элементов 33
Приложение Б – Решение элементов 34

Файлы: 1 файл

Курсовая.docx

1 Симплекс-метод 5

1.1 Общая характеристика симплекс-метода 5

1.2 Общая идея симплексного метода 12

1.3 Симплекс-метод решения задачи линейного программирования 14

2 Решение задачи при помощи симплекс – метода 20

2.1 Постановка задачи 20

2.2 Решение поставленной задачи 21

2.3 Решение задачи при помощи табличного процессора Microsoft Excel 25

Список используемых источников 32

Приложение А – Решение элементов 33

Приложение Б – Решение элементов 34

Приложение В - Презентация 35

Приложение Г - Диск 44

Введение

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных.

Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения.

Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.

Для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их использования можно просто проиллюстрировать.

Для решения задач линейного программирования потребовалось создание специальных методов.

Особенно широкое распространение линейное программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные.

Задачи курсовой работы:

изучить теоретический материал;
на примерах рассмотреть симплекс метод.

В первой главе курсовой работы рассматриваются:

общая характеристика симплекс-метода;
алгоритм симплексного метода решения;
понятие базисного решения – основа симплекс-метода;
симплексный метод решения задач линейного программирования.

Во второй главе курсовой работы описывается решение задачи симплекс-методом линейного программирования.

В заключении получено решение заданного варианта задачи линейного программирования.

1 Симплекс-метод

1.1 Общая характеристика симплекс-метода

Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Симплекс-метод известен с 1947 года, когда появилась первая публикация Джона Данцига, посвященная этому методу. В советской литературе 60-80-х гг. прошлого столетия этот метод был известен также как метод последовательного улучшения плана.

В 1939 году в Советском Союзе появилась работа, которая, как выяснилось позднее, могла быть оценена, как фундаментальная для развития теории линейного программирования.

Решая чисто практическую задачу, поставленную перед ним руководителями лаборатории фанерного треста, которые стремились создать модель оптимального распределения материала между станками, профессор Л.В.Канторович практически дал метод решения задачи линейного программирования как рассматриваемой модели.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ.

Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования.

В 1939 год. Говорят, что истина рождается ересью и, увы, так случилось и с идеями Л.В.Канторовича в области экономики. Они не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.

Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т. Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем.

В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию.

Маленькая книга, изданная малым тиражом, обращенная даже не экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем - стоит ли принимать такую книжку во внимание. Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем.

Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс- методом.

Как только в 50-е годы образуется маленький просвет и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования.

Начиная с 1960 года Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (ему присуждена совместно с В.С.Немчиновым и В.В.Новожиловым) и Нобелевской премией в 1975 году.

За прошедшие с тех пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности различных подклассов задачи ЛП (блочные задачи, задачи со слабо заполненной матрицей условий A =), но и несколько принципиально иных методов решения задачи ЛП.

Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят симплекс-метод (известно, что симплекс-метод обладает экспоненциальной сложностью, т.е. имеет экспоненциальную оценку трудоемкости на всем классе задач ЛП, тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя) характеризуются полиномиальной сложностью).

В теории линейного программирования симплекс-метод и после десятилетий всесторонней апробации с точки зрения алгоритмической реализации и универсальности применимости на классе задач ЛП остается наиболее предпочтительным, а потому наиболее распространенным методом решения задач ЛП.

Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации.

Основная идея симплекс-метода достаточно просто иллюстрируется геометрически.

Каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей.

Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань.

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

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

нахождение исходной вершины множества допустимых решений;
последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

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

Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация.

Все ограничения задачи модифицируются согласно следующим правилам:

Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:

Читайте также: