Решить симплекс методом и выполнить графическую интерпретацию. Линейное программирование. Симплекс-метод

Понравилось? Добавьте в закладки

Решение задач симплекс-методом: примеры онлайн

Задача 1. Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Задача 2. Решить задачу линейного программирования симплекс-методом.

Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.

1. Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
2. Определить статус каждого вида сырья и его удельную ценность.
3. Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
4. Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
5. Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.

Задача 4. Решить задачу линейного программирования симплексным методом:

Задача 5. Решить задачу линейного программирования симплекс-методом:

Задача 6. Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:

Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.

Задача 8. Найти оптимальное решение двойственным симплекс-методом

Основным алгоритмом решения ЗЛП является симплекс-метод. Его можно применять в случае, если задача оптимизации записана в специальном каноническом виде. При этом все ограничения имеют вид равенств и каждая базисная переменная встречается с коэффициентом 1 только в одном уравнении, а в других коэффициент при базисной переменной равен 0. Аналитическое выражение для целевой функции не должно содержать базисных переменных, а выражаться только через свободные переменные. Если при этом b i ≥ 0, то говорят о допустимом каноническом виде.

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

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

Вырожденное опорное решение опорное решение, в котором одна или несколько базисных переменных равны нулю.

Допустимое опорное решение опорное решение, в котором все базисные переменные ≥ 0.

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

Для удобства формулировки правил метода запишем допустимую каноническую форму ЗЛП в ином виде, называемом стандартной формой. Например:

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

В симплекс-методе требуется иметь исходное допустимое опорное решение. Иногда такое решение получить легко. Например, если существует ограничение вида с положительной правой частью, то дополнительные переменные, используемые при записи ограничений в виде равенств, образуют допустимое опорное решение, в котором все переменные проектирования равны нулю, а дополнительные переменные являются базисными. Однако во многих задачах существуют ограничения вида0 и = 0, для которых начальное опорное решение может быть недопустимым. Поэтому применению симплекс-метода в общем случае должен предшествовать этап поиска допустимого решения. Рассмотрим один из вариантов алгоритма симплекс-метода с учетом этапа поиска допустимого решения.

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

1-й этап: нахождение допустимого опорного решения.

Шаг 1. Ограничения неравенства приводятся к виду ограничений ра-венств. Задача записывается в стандартной форме.

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

Шаг 3. Для ограничения, имеющего отрицательный свободный член, выбирается свободная переменная с отрицательным коэффициентом. Эта переменная будет новой базисной переменной. Если отрицательных коэффициентов более одного, то в качестве новой базисной переменной можно выбрать любую, имеющую отрицательный коэффициент (выбор переменной в этом случае скажется на числе замен базиса, но не на конечном результате). Пусть это будет переменнаяx l . Если ограничений с отрицательным свободным членом более одного, то можно для анализа коэффициентов выбрать любое.

Шаг 4. Для выбора новой свободной переменной рассматривается отношениеb j /a jl для всех ограничений, причемb j иa jl должны иметь одинаковый знак. Находится минимальное отношение. Новой свободной переменной будет та базисная переменная, для ограничения которой отношениеb j /a jl оказалось минимальным. В этом случае разрешающий элемент таблицы будет находиться на пересечении столбца, соответствующего переменнойx l и строки, соответствующей ограничению, для которого получено минимальное отношение.

Шаг 5. Делается замена базиса. Для пересчета значений элементов симплекс-таблицы после смены базиса введем в таблицу следующие обозначения:

при q=r; s=p, номер итерации(смены базиса);

при q=r ;sp , s=
;

при q r;s=p ;q=
;

для остальных элементов.

Шаг 6. Возвращаемся на шаг 2.

2-й этап: нахождение оптимального решения.

Шаг 1. Проверяется признак оптимальности решения.

Признаки оптимального решения:

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

б) целевая функция будет иметь минимальное значение в том случае, если в строке целевой функции в стандартной форме все коэффициенты при свободных переменных отрицательны;

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

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

Шаг 2. В соответствии с правилом выбора новой базисной переменной одну из свободных переменных переводим в базисные.

Правило выбора свободной переменной, переводимой в базис

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

Шаг 3. В соответствии с правилом выбора переменной, переводимой из базисной в свободные, определяем новую свободную переменную.

Сформулируем правило выбора переменной, переводимой из базисных в свободные.

Для выбора новой свободной переменной x i необходимо рассмотреть отношениеb j /a ij для всех ограничений (
), (
), из этих отношений выбрать минимальное, а в качестве новой свободной переменной выбирать базисную переменную, для ограничения которой получено минимальное отношениеb j /a ij . Отношениеb j /a ij необходимо рассматривать только для положительныхa ij . Если минимум достигается более чем для одного индексаj , то из базиса исключается любая из переменных, соответствующих j -м ограничениям.

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

Шаг 4. Осуществляется замена базиса аналогично шагу 5 первого этапа.

Шаг 5. Переходим к шагу 1.

Пример 2. Найтипри ограничениях

Запишем задачу в стандартной форме и представим ее в виде симплекс-таблицы:

Признак несовместности ограничений не выполняется. Допустимое решение не найдено, так как свободный член для ограничения x 5 равен5. Для получения допустимого решения произведем смену базиса. В качестве разрешающего столбца выберемx 1 ; разрешающей строки –x 6 (так как 2/1 <5/2). Разрешающий элемент подчеркнут. Строим новую симплекс-таблицу.

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

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

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

Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.

Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Цель производственной задачи

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

Решение задачи табличным симплекс-методом

(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )

(2) Запишем ограничения плана в виде системы уравнений:

(3) Тогда целевая прибыль:

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

(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).

(5) Примем следующий опорный план :

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесем данные в симплекс-таблицу :

В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;

(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.

Вычислим b = Н / Элементы_выбранного_столбца

Среди вычисленных значений b выбираем наименьшее .

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

• Сам разрешающий элемент обращается в 1.
• Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
• Для элементов разрешающего столбца – они просто обнуляются.
• Остальные элементы таблицы пересчитываем по правилу прямоугольника.

a ij (*) = a ij – (A * B / РЭ)

Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .

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

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.

(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.

ОТВЕТ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2 196 руб.

Галяутдинов Р.Р.

© Копирование материала допустимо только при указании прямой гиперссылки на

Рассмотрим симплекс -метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.

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

1. Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0 , т.к. целевая функция не должна при этом менять свой экономический смысл.
2. Выписываются вектора P i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
3. После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение . Коэффициенты целевой функции записывают с противоположным знаком.
4. Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р 0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
5. Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0 . Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
6. Так поступают до тех пор, пока в f – строке все элементы не станут положительными.

Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:

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

Составляем вектора:

Заполняем симплекс – таблицу:

:
Пересчитаем первый элемент вектора Р 0 , для чего составляем прямоугольник из чисел: и получаем: .

Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:

В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:

Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план :
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).

• Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
• Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
• Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.

Решение линейного программирования на заказ

Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на