Симплексный метод решения задачи линейного — КиберПедия 

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

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

2017-10-11 296
Симплексный метод решения задачи линейного 0.00 из 5.00 0 оценок
Заказать работу

Программирования

 

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

Предположим, составляется план производства для предприятия, выпускающего два вида продукции А и В. На изготовление единицы изделия А требуется затратить а 1 = 2 кг сырья первого типа, а 2 = 3 кг сырья второго типа и а 3 = 1 кг сырья третьего типа. Для единицы изделия B: b 1 = 1 кг сырья первого типа, b 2 = 4 кг сырья второго типа и b 3 = 3 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количествах 400 кг, 900 кг, 600 кг, соответственно. Стоимость реализации единицы изделия А составляет 60 (д. ед), а единицы изделия В – 40 (д. ед). следует составить план производства изделий А и В, обеспечивающий максимум прибыли от реализации.

Сформулируем задачу математически. Пусть х 1 и х 2 – неизвестные количества изготавливаемых изделий А и В, соответственно. Необходимо найти такие х 1 и х 2, чтобы выполнялись условия:

2x1+x2 400

3x1+4x2 900

X1+3x2 600

X1 0,x2 0

и при этом функция f = 60 х 1 + 40 х 2 была максимальна. Система ограничений описывает условия производства. Функция f – целевая функция, а х 1 и х 2 - аргументы целевой функции.

Задача имеет стандартную форму. Представим эту задачу в канонической форме, введя дополнительные переменные х 3, х 4, х 5, экономический смысл которых - неиспользованное сырье, соответственно, первого, второго и третьего типов.

2x1+x2+x3=400

3x1+4x2+x4=900 (1.23)

X1+3x2+ x5=600

X1 0,x2 0, x3 0,x4 0,x5 0 (1.24)

 

 

Функцию f представим в неявном виде:

f - 60 x 1 – 40 x 2= 0

Заметим, что если бы в задаче требовалось найти не max f, a min Z, то следовало бы перейти к функции f = - Z.

Пусть переменные х 1, х 2, входящие в функцию f, будут свободными, а переменные х 3, х 4, х 5 – базисными. Базисные переменные выразятся через свободные следующим образом:

(1.25)

Полагая свободные переменные равными нулю, получим первое опорное решение:

x 1 = x 2 = 0; x 3 = 400; x 4 = 900; x 5 = 600

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

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

 

 

Таблица 5

№ 1 x 1 x 2 x 3 x 4 x 5 b i b i / a ij
x 3             400/2=200 Z
x 4             900/3=300
x 5             600/1=600
f -60 -40          

ñ

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

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

В последней строке таблицы среди отрицательных значений находим наибольший по абсолютной величине элемент (это (-60)). Столбец, в котором находится этот элемент, называется ведущим, он соответствует новой базисной переменной x 1. Делим свободные члены (b i) на соответствующие элементы ведущего столбца (отрицательные элементы ведущего столбца и нули во внимание не принимаются) и среди частных от деления находим минимальное значение,

т.е. min

Строка, которой соответствует минимальное значение, называется ведущей строкой. Смысл этой операции – сократить перебор вершин многоугольника за счет выбора строки с наименьшим допустимым значением новой базисной переменной x 1. Ведущая строка соответствует старой базисной переменной x 3, которая переводится в свободные. На пересечении ведущей строки и ведущего столбца расположен разрешающий элемент. В нашем случае это число а* = 2.

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

w Ведущую строку переписываем во вторую таблицу, поделив предварительно все элементы строки на разрешающий элемент;

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

w Столбцы соответствующие оставшимся базисным переменным переписываем в новую таблицу без изменения;

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

 

a ij A

 

В а *

 

Рис. 1.4. Схема правила прямоугольника

 

 

На рис. 1.4. элемент исходной таблицы a ij и разрешающий элемент а * располагаются на одной из диагоналей прямоугольника; А – элемент ведущего столбца, стоящий в одной строке с a ij; В – элемент ведущей строки, стоящий в одном столбце с a ij. Тогда элемент a ij ´ новой таблицы определяется по формуле:

a ij ´ = a ij-(A*B)/ а *

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

Таблица 6

№ 2 x 1 x 2 x 3 x 4 x 5 b i b i / a ij
x1   ½ ½        
x 4   2,5 -1,5       120 Z
x 5   2,5 -0,5        
f   -10          

ñ

 

Из полученной симплексной таблицы можно записать второе опорное решение. Переменные х 2, х 3 являются свободными и равны нулю: х 2 = х 3 = 0. Базисные переменные: x1 = 200; х 4 = 300; х 5 = 400. Прибыль составляет: f = 12000 (д.ед.).

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

Преобразуя таблицу 6, как и ранее, методом Гаусса, получим таблицу 7.

 

 

aТаблица 7

№ 3 x 1 x 2 x 3 x 4 x 5 b i
x 1     4/5 -1/5    
x 2     -3,5 2/5    
x 5       -1    
f            

 

В последней строке таблицы 7 все элементы положительны, что означает, что полученное опорное решение является оптимальным. Предприятие получит максимальную прибыль от реализации выпускаемых изделий при выпуске х1 = 140 ед. изделия А, х 2 = 120 ед. изделия В. При этом ресурсы первого и второго вида будут использоваться полностью, х 3 = х 4 = 0. По ресурсу третьего вида будет остаток х 5 = 100 кг. Прибыль, которую получит предприятие от реализации изделий, составит f = 13200 (д.ед.).

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

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

 


Поделиться с друзьями:

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

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

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.018 с.