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

17

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

Содержание

1. Сформулируйте задачу составления рациона

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

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

1. Сформулируйте задачу составления рациона

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

Пусть в хозяйстве имеется два вида корма I и II, содержащие питательные вещества (витамины) S1, S2 и S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице (цифры условные).

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

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

Решение. Составим экономико-математическую модель задачи.

Обозначим x1, x2 -- количество кормов I и II, входящих в дневной рацион. Тогда этот рацион (см. табл) будет включать (3x1+1* x2) единиц питательного вещества S1, (1 * x1+2x2) единиц вещества S2 и (1 * x1 + 6x2) единиц питательного вещества S3.

Так как содержание питательных веществ S1, S2 и S3 в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств:

(1)

Кроме того, переменные

(2)

Общая стоимость рациона составит (в руб.)

(3)

Итак, экономико-математическая модель задачи:

составить дневной рацион , удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает минимальное значение.

Для формулировки задачи в общей постановке обозначим:

-- число единиц корма n-го вида;

-- необходимый минимум содержания в рационе питательного вещества Si;

aij -- числоединиц питательного вещества Si в единице корма j-го вида;

cj -- стоимость единицы корма j-го вида.

Тогда экономико-математическая модель задачи примет вид:

найти такой рацион , удовлетворяющий системе

и условию

при котором функция

принимает максимальное значение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

Получаем:

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

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

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

Дk = CбXk -- ck

Где 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).

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

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

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

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

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

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

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

7. Хэмди, А. Таха. Введение в исследование операций. пер. с англ. / А. Таха Хэмди. - М.: Издательский дом «Вильямс», 2007. - 912 с.