Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
тор
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Ижевский государственный технический университет»
к проведению практических занятий и
лабораторных работ
по дисциплине "Теория принятия решений"
на тему "Симплексный метод решения задачи
линейного программирования"
для студентов специальностей 230102,230104,
направления 230100
Форма обучения очная и заочная
Ижевск 2009
Рецензент: И.Н. Габдрахманов, к.т.н., доцент кафедры АСОИУ
ИжГТУ.
Исенбаева Е.Н. Методические указания к выполнению лабораторной работы по дисциплине «Теория принятия решений» на тему «Симплексный метод решения задачи линейного программирования». – Ижевск: Издательство ИжГТУ, 2009 г.-20 с.
В методических указаниях описан симплексный метод решения задачи линейного программирования. Сформулирована постановка задачи линейного программирования, рассмотрен алгоритм симплексного метода, проиллюстрированный на примере. Приведены варианты заданий на лабораторную работу.
Рекомендовано к изданию на заседании кафедры «Автоматизированные системы обработки информации и управления» ИжГТУ (протокол №4 от 02.07.2009).
Учебное пособие предназначено для студентов очной и заочной формы обучения специальностей 230102, 230104, направления 230100.
.
Исенбаева Е.Н., составление, 2009
Издательство ИжГТУ, 2009
ВВЕДЕНИЕ
Данные методические указания предназначены для использования студентами при выполнении лабораторной работы на тему «Симплексный метод решения задачи линейного программирования».
В пособии дается описание распространенного метода решения задачи линейного программирования– симплексного метода. Симплексный метод является классическим и наиболее проработанным методом в линейном программировании. В работе сформулирован алгоритм решения задачи, который проиллюстрирован на примере.
В пособии предложены варианты заданий на лабораторную работу.
Выполняя данную лабораторную работу, студент должен научиться решать задачи линейного программирования и применять полученные навыки при выполнении курсовых работ и дипломной работы.
1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задача линейного программирования (ЛП) возникает из необходимости оптимально использовать имеющиеся ресурсы. Это задачи, связанные с анализом целей и функций; задачи разработки или совершенствования структур ( производственных структур предприятий, организованных структур объединений); задачи проектирования( проектирование сложных – робототехнических комплексов, гибких производственных систем).
В качестве конкретных примеров задач, которые относятся к области линейного программирования, можно назвать задачу об использовании сырья, задачу об использовании мощностей, задачу на составление оптимальной производственной программы.
Рассмотрим задачу из экономической области на составление оптимальной производственной программы [5]. Для изготовления двух видов продукции Р1, Р2 используется три вида сырья S1, S2, S3. Запасы сырья, количество единиц сырья, затраченных на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1.
Вид сырья |
Запас сырья, Т |
Затраты сырья на единицу продукции |
|
Р1 |
Р2 |
||
|
S1 |
9 |
1 |
1 |
|
S2 |
3 |
0,5 |
1 |
|
S3 |
3 |
1 |
0,5 |
|
Прибыль от единицы продукции, денежных единиц |
1 |
2 |
Составить оптимальную производственную программу, т.е. такой план выпуска продукции, чтобы при ее реализации можно было получить максимальную прибыль.
Математически эта задача формулируется следующим образом.
Переменные.
Так как нужно определить объем производства каждого вида продукции, переменными в модели являются:
x1 – объем производства продукции Р1
х2 – объем производства продукции Р2
Целевая функция. Конечную цель задачи- получение максимальной прибыли при реализации продукции – выразим как функцию 2-х переменных х1 и х2.
Суммарная прибыль Z = x1 + 2 x2
Ограничения.
При решении рассматриваемой задачи должны быть учтены ограничения на расход сырья.
х1 + х2 9 (для вида S1),
0,5 х1 + х2 3 (для вида S2),
х1 + 0,5 х2 3 (для вида S3).
Добавим ограничения на не отрицательность значений объемов производства продукции
х1 0, х2 0.
Итак, математическая модель формулируется следующим образом.
Определить объемы производства х1, х2 продукции вида Р1 и Р2 в тоннах, при которых достигается максимум целевой функции
Z = х1 + 2 х2
при ограничениях
х1 + х2 9
0,5 х1 + х2 3
х1 + 0,5 х2 3
Таким образом, задача ЛП заключается в отыскании вектора (х1, х2,…,хJ,…,хn), который максимизирует линейную целевую функцию
Z= с1х1+с2х2+…+сjхj+…+сnхn, (1)
при следующих линейных ограничениях
11х1 + 12 х2 + …+1n xn b1
21х1 + 22 х2 + …+2n xn b2
. . . (2)
m1х1 + m2 х2 + …+mn xn bm
x1 0, x2 0,. . .,xn 0. (3)
Запись задачи ЛП в виде (1)-(3) называется симметричной формой представления задачи линейного программирования.
Эту же задачу ЛП можно представить в векторно-матричной записи:
AX B, Х 0, где C = (c1, c2,…,cn), , ,
A=(ij), , – матрица коэффициентов ограничений,
С - вектор коэффициентов целевой функции
Х- вектор решения.
Область называется областью допустимых значений (ОДЗ) задачи линейного программирования.
Соотношения (2), (3) называются системами ограничений задачи ЛП.
Так как , то можно ограничиться изучением задачи одного типа.
Решением задачи ЛП называется вектор, удовлетворяющий системе ограничений задачи и оптимизирующий целевую функцию.
Другая форма представления задачи ЛП – каноническая. Она имеет вид:
CX max
AX = B, X 0.
Наряду с задачей ЛП в симметричной форме (1)-(3) рассмотрим задачу
BU min (4)
ATU C, U 0, (5)
где - переменные двойственной задачи.
Задача (4), (5) называется двойственной по отношению к задаче (1)-(3).
2. АЛГОРИТМ СИМПЛЕКС-МЕТОДА
Симплекс метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.
Этот метод позволяет переходить от одного допустимого решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить является ли задача ЛП разрешимой.
1. Рассмотрим задачу ЛП в симметричной форме (1)-(3). Сделаем допущения: В 0.
Введем вектор Y такой, что Y = B AX, YRm, Y 0,
Y = (xn+1, xn+2, . . .,xn+m)T. Вектор Y называют балансовым, а xn+1, xn+2, . . .,xn+m – балансовыми переменными.
В целевую функцию балансовые переменные входят с нулевыми коэффициентами, т.е.
=c1x1 + c2x2 +…+ cnxn + 0xn+1 +…+ 0xn+m
или
, где , Rn+m. (6)
Систему ограничений (2) задачи ЛП можно записать:
11х1 + 12 х2 + …+1n xn +хn+1 = b1
21х1 + 22 х2 + …+2n xn +хn+2 = b2
. . . (7)
m1х1 + m2 х2 + …+mn xn +хn+m = bm
причем xj 0, (8)
Таким образом, задачу ЛП (1)-(3) преобразовали из симметричной формы в каноническую.
Итак, вместо задачи (1)-(3) будем искать решение задачи (6)- (8).
2. Положим j = 1. Взяв переменные х1,…,хn за свободные и положив их равными нулю, а хn+1,…,хn+m – за базисные, находим первую крайнюю точку.
= (0,…,0,b1,b2,...,bm).
n
3. Обозначим через Аk - вектор, составленный из коэффициентов ограничений при переменной хk, СБ вектор, составленный из коэффициентов целевой функции, соответствующих базисным переменным, через Сk – коэффициент целевой функции при переменной xk.
Вычислим симплексные разности k в j-той крайней точке по формуле
k = Ak∙ CБ k, . (9)
Заполняется симплекс-таблица (таблица 2) по указанным выше правилам.
Таблица 2
|
Базис |
СБ |
1 |
2 |
… |
n |
n+1 |
… |
n+m |
|
|
B |
A1 |
A2 |
… |
An |
An+1 |
… |
An+m |
||
|
xn+1 xn+2 . . . xn+m |
n+1 n+2 . . . n+m |
b1 b2 . . . bm |
11 21 . . . m1 |
12 22 . . . m2 |
… … . . . … |
1n 2n . . . mn |
1 0 . . . 0 |
… … . . . … |
0 0 . . . 1 |
|
1 |
2 |
… |
n |
n+1 |
… |
n+m |
4. Если для j-той крайней точки все симплексные разности k 0, , то эта точка оптимальная. Конец решения.
Если есть столбец, в котором симплексная разность k0 0 и все элементы столбца ik0 0, , то задача ЛП решения не имеет, т.к. целевая функция не ограничена сверху.
В остальных случаях переход к пункту 5.
5. Находим k0 направляющий столбец. Выбираем столбец, в котором самая минимальная симплекс разность среди отрицательных симплекс-разностей (напомним, что решаем задачу максимизации) т.е.
k0= min k (10)
k < 0.
Направляющая строка i0 выбирает из условия
, , αik0 › 0 . (11)
Итак, направляющий элемент i0k0.
Заполняем таблицу, соответствующую новому решению.
6. Выполняем один шаг метода Гаусса, введя в базис вектор Аk0 вместо вектора Аn0, имеющего i0 – координату, равную 1. Для это используются следующие соотношения:
- новые элементы направляющей строки :
, ; (12)
- новые элементы направляющего столбца:
, , причем i i0; (13)
т.е. в направляющем столбце все элементы равны 0, а направляющий элемент равен 1.
- новые значения остальных элементов матрицы:
, ; (14)
- новые значения симплексных разностей:
,; (15)
Правильность вычислений контролируется по формулам непосредственного счета:
, (16)
Получаем (j + 1) крайнюю точку. Полагая j = j + 1, переходим к пункту 4.
Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.
Замечание 1. Если одна из базисных переменных равна нулю, то крайняя точка, соответствующая такому базисному решению- вырожденная. Вырожденность возникает, когда имеется неоднозначность в выборе направляющей строки. Можно вообще не заметить вырожденности задачи, если выбрать другую строку в качестве направляющей. В случае неоднозначности нужно выбирать строку с наименьшим индексом, чтобы избежать зацикливания.
Замечание 2. Пусть в некоторой крайней точке все симплексные разности неотрицательные k 0 (),т.е. получено оптимальное решение и существует такой Аk – небазисный вектор, у которого k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную xk, значение целевой функции не изменится.
Замечание 3. Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей( в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.
Замечание 4. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации[3].
ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ
Найти максимальное значение линейной функции
Z = x1 + 2x2
при ограничениях
x1 + x2 9
-x1 + x2 3 (17)
x1 - x2 3, x1,x2 0.
Перейдем от исходной задачи к задаче с ограничениями типа равенств. Введем вектор балансовых переменных y, размерность которого равна числу неравенств в системе ограничений: y = (x3, x4, x5). Все балансовые переменные неотрицательные, в целевой функции им соответствуют коэффициенты, равные нулю. Исходную задачу преобразовали к виду:
= x1 + 2x2 + 0x3 + 0x4 + 0x5 max
x1 + x2 + x3 = 9
x1 + x2 + x4 = 3 (18)
x1 x2 + x5 =3
x1, x2, x3, x4, x5 0.
, , ,
, , , , .
Заполняем первую симплексную таблицу.
Таблица 3
|
Базис |
CБ |
1 |
2 |
0 |
0 |
0 |
|
|
B |
A1 |
A2 |
A3 |
A4 |
A5 |
||
|
x3 x4 x5 |
0 0 0 |
9 3 3 |
1 -1 1 |
1 1 -1 |
1 0 0 |
0 1 0 |
0 0 1 |
|
Z=0 |
-1 |
-2 |
0 |
0 |
0 |
Переменные x3, x4, x5 образуют базис. Свободные переменные х1, х2 выбираем равными нулю. Тогда системе ограничений задачи (18) удовлетворяет вектор
= (0,0,9,3,3)T (сравните значение базисных переменных с вектором В в симплексной таблице).
- первая крайняя точка.
Так как x3, x4, x5 – базисные переменные, то
CБ = () = (0,0,0).
Умножая скалярно вектор CБ и А1 и вычитая из произведения , находим симплексную разность 1. Аналогично, вычисляем остальные симплексные разности k () в первой крайней точке. Полученные значения записываем в последнюю строку таблицы.
Вычислим значение целевой функции в первой крайней точке:
= СБ В = 0
Так как для первой крайней точки имеются отрицательные симплексные разности, то она не является оптимальной. Ищем вторую крайнюю точку. По формуле находим переменную, вводимую в базис.
, т.е. в базис надо ввести х2. Т.о. направляющий столбец с номером 2.
Определим переменную, выводимую из базиса
,
, т.е. i0 = 2.
Значит, направляющая строка имеет номер 2.
Обратите внимание, что отношение не принималось во внимание при нахождении значения индекса i0, так как значение коэффициента 32 < 0. Переменная, выводимая из базиса х4. Т.о. направляющий элемент 22 = 1.
Используя один шаг метода Гаусса, введем в базис переменную х2 вместо переменной х4, применяя соотношение (12)-(16). Тем самым найдем координаты второй крайней точки.
Заполняем вторую симплексную таблицу.
Таблица 4
|
Базис |
CБ |
1 |
2 |
0 |
0 |
0 |
|
|
B |
A1 |
A2 |
A3 |
A4 |
A5 |
||
|
x3 x2 x5 |
0 2 0 |
6 3 6 |
2 -1 0 |
0 1 0 |
1 0 0 |
-1 1 1 |
0 0 1 |
|
=6 |
-3 |
0 |
0 |
2 |
0 |
Сейчас в базисе переменные x3, x2, x5 (порядок именно такой). Свободные переменные х1=0 и х4=0. Тогда базисные переменные принимают значения x3=6, x2=3, x5=6. Вторая крайняя точка =(0,3,6,0,6)Т. Вектор СБ для этой точки имеет вид:
CБ = () = (0,2,0).
Строку симплексных разностей вычисляем по формуле:
k = CБAk ,
1 = 3, 2 = 0, 3 = 0, 4 = 2, 5 = 0.
Значение целевой функции во второй крайней точке
= СБ В =06 + 23 + 06 = 6.
Для второй крайней точки одна из симплексных разностей отрицательна, поэтому эта точка еще не является оптимальной.
Находим очередную крайнюю точку. Переменную х1 вводим в базис, так как , т.е. направляющий столбец имеет номер 1.
, т.е. i0=1, т.е. направляющая строка имеет номер 1.
Тогда переменная х3 - выводится из базиса. Направляющий элемент 11 = 2.
Осуществляем один шаг метода Гаусса, пользуясь соотношениями (12)-(16), получаем третью симплексную таблицу.
Таблица 5
|
Базис |
CБ |
1 |
2 |
0 |
0 |
0 |
|
|
B |
A1 |
A2 |
A3 |
A4 |
A5 |
||
|
x1 x2 x5 |
1 2 0 |
3 6 6 |
1 0 0 |
0 1 0 |
0,5 0,5 0 |
-0,5 0,5 1 |
0 0 1 |
|
Z=15 |
0 |
0 |
1,5 |
0,5 |
0 |
Найдена третья крайняя точка
=(3,6,0,0,6)Т,
CБ = ()T = (1,2,0)T,
1 = 2 = 5 = 0, 3 = , 4 = .
Так как все симплексные разности неотрицательны, то третья крайняя точка является оптимальной. Значение целевой функции в оптимальной точке равно = CБ В = 13 + 26 + 06 = 15.
Таким образом, найдено оптимальное решение задачи (18). Отбросив в векторе балансовые переменные, получим оптимальное решение исходной задачи Xопт = (3,6), Zmax = 15.
Рассмотрим геометрическую интерпретацию решения. Построим область допустимых решений задачи (17). Это многоугольник ОАВСD.
Отметим найденные крайние точки. Первая точка совпадает с вершиной О; вторая – с вершиной А; третья оптимальная точка – вершина В.
Найдем решение двойственной задачи.
W = 9U1 + 3U2 + 3U3 min,
U1 U2 + U3 1
U1 + U2 U3 2
U1, U2, U3 0.
Решение находим по последней симплексной таблице – последние три симплексные разности Uопт = (1,5; 0,5; 0)
Wmin = 15 [3].
Написать программу, реализующую симплексный метод решения задачи линейного программирования.
В программе требуется предусмотреть:
Варианты заданий на лабораторную работу
1. Z = x1 + x2 + x3 + x4 + x6 max
x1 + x2 + x3 + x4 x5 x6 = 1 xj 0,
x2 + x3 x4 x5 x6 = 1
x2 x6 = 2.
2. Z = x1 + x3 + x5 + x6 max
x1 + 4x2 + x3 + 3x4 2x5 + x6 = 15 xj 0,
x1 + 4x2 x3 x4 + x6 = 5
2x1 + 6x2 + x3 + 4x4 2x5 + x6 = 22.
3. Z = x1 2x2 + x3 8x4 + x5 + x6 max
x1 + 4x2 + x3 + 3x4 2x5 + x6 = 15 xj 0,
x1 + 4x2 x3 x4 + x6 = 5
2x1 + 6x2 + x3 + 4x4 2x5 + x6 = 22.
4. Z = x1 + x3 + x6 max
x1 + x2 + x3 + x4 x5 x6 = 1 xj 0,
x2 + x3 x4 x5 x6 = 1
x2 x6 = 2.
5. Z = x1 + 2x2 + x3 2x4 + x5 2x6 min
x1 x2 + x3 x4 + x5 x6 = 7
2x1 + 3x2 2x3 3x4 + 2x5 + 3x6 = 3 xj 0,
3x1 + 2x2 x3 4x4 + 3x5 + 2x6 = 10.
6. Z = x1 4x2 + x3 + x4 + x5 +x6 min
2x1 + x2 + x3 + x5 = 20
x1 2x2 + x4 + 3x5 = 24 xj 0,
3x1 x2 12x5 + x6 = 18.
7. Z = 2x1 6x2 + 3x5 max
2x1 + x2 + x3 + x5 = 20 xj 0,
x1 2x2 + x4 + 3x5 = 24
3x1 x2 12x5 + x6 = 18.
8. Z = x1 + x2 + x3 + 2x4 + 3x5 + 2x6 max
2x1 + x2 + x3 + x5 = 20
x1 2x2 + x4 + 3x5 = 24 xj 0,
3x1 x2 12x5 + x6 = 18.
9. Z = x1 4x2 + x3 +x4 + x5 + x6 min
x1 + x2 + x3 + x4 x5 x6 = 1
x2 + x3 x4 x5 x6 = 1 xj 0,
x2 x6 = 2.
10. Z = x1 x2 + 2x3 x4 + x5 max
x1 + x2 + 2x3 + 3x4 2x5 = 3
x2 x3 x4 x5 = 0 xj 0,
x1 + x4 x5 = 0.
11. Z = x1 + x2 + x3 + x4 max
xj 0,
12. Z = x1 + x2 x3 + 5x4 max
xj 0,
13. Z = 3x1 + 2x2 + x3 + x4 5x5 10x6 max
xj 0,
14. Z = x1 + x2 + x3 x5 max
xj 0,
15. Z = x1 + 2x6 max
xj 0,
16. Z = x1 + x2 + x3 x5 min
xj 0,
17. Z = x1 x2 + x3 x4 + x5 x6 max
xj 0,
18. Z = x1 + 2x2 + x3 2x4 + x5 2x6 max
xj 0,
19. Z = x1 2x2 + 2x3 + 3x4 x5 min
xj 0,
20. Z = x1 x2 + 2x3 x4 + x5 min
xj 0,
5. СОДЕРЖАНИЕ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ
В отчете по лабораторной работе должны быть представлены следующие разделы:
1. Постановка задачи.
2. Математическая модель.
3. Текст программы.
4. Результаты работы.
5. Выводы.
Лабораторная работа выполняется на любом языке высокого уровня.
6. ВОПРОСЫ ДЛЯ ПРОВЕРКИ ОСТАТОЧНЫХ ЗНАНИЙ
7.СУЩЕСТВУЮЩИЕ МАТЕМАТИЧЕСКИЕ
ПРОГРАММНЫЕ СИСТЕМЫ
Решение задач линейного программирования – это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ. Табличный симплекс-метод хорошо приспособлен для программирования и машинного счета.
Существуют программные реализации симплекс-метода. В настоящее время появились интегрированные математические программные системы для научно-технических расчетов: Eureka, PC MatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.
Широкую известность и заслуженную популярность приобрели математические системы класса MathCAD, разработанные фирмой MathSoft (США). Это единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков [6].
СПИСОК ЛИТЕРАТУРЫ
1. Андрейчиков А.В., Андрейчикова О.Н. Компьютерная поддержка изобретательства. – М.: Машиностроение, 1998.
2. Варфоломеев В.И., Воробьев С.Н. Принятие управленческих решений.-М.: Кудиц- образ, 2001.
3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: Учебное пособие для вузов. -М.: Дрофа, 2004.
4. Зайченко Ю.П. Исследование операций. Сборник задач. – Киев: Выща школа, 1988.
5. Зайченко Ю.П., Шумилова С.А. Исследование операций. Сборник задач. – Киев: Выща школа, 1990.
6. Дьяконов В.П. Справочник по MathCAD PLUS 7.0 PRO. – М: СК Пресс, 1998.
7. Ларичев О.И. Теория и методы принятия решений. – М.: Логос, 2000.
8. Ларичев О.И., Мошкович Е.Н. Качественные методы принятия решений. – М.: Физматлит, 1996.
9. Ларичев О.И. Наука и искусство принятия решений. – М.: Наука, 1979.
4
6
2
6
4
2
EMBED Equation.3
x2
EMBED Equation.3
EMBED Equation.3
D
B
C
x1
0
A