В этом случае мы имеем дело с неотрицательными решениями системы уравнений. Любая задача линейного программирования с помощью элементарных преобразований может быть приведена к каноническому виду. F (x)=c1x1+c2x2+…+cnxn ->max (min)a11×1+a12×2+…+a1nxn +х n +1 = b1a21×1+a22×2+…+a2nxn+х n +2 = b2 (3)…am1x1+am2x2+…+amnxn+х n +т = bmxi≥0 (i=1.n), где F (x) — целевая функция; х1, х2,…, хn- базисные переменные; другие переменные именуются свободными. Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как вернымравенствам. Базисные переменные
Свободные членыX 1X 2… X nX n+1X n+2…Xn+mX n+1b1a 11a 12… a 1n10…0X n+2b2a 21a 22… a 2n01…0…X n+mb ma m1a m2… amn00…1F (x)0-c1-c2…-cn00…0Разберем алгоритм перехода к следующим симплекс-таблицам:
1. Находим ключевой столбец. Это столбец соответственный минимально отрицательному (максимально положительному) элементу последней (индексной) строке:
Если отрицательных элементов в индексной строке нет, то план оптимальный.
2. В ключевом столбце находятся положительные коэффициенты, если таких нет, то задача не имеет решений;
3. Выбираем ключевую строку:
Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответственного свободного члена к этому элементу минимальна. Ключевой элемент — это элемент, расположенный на пересечении ключевого столбца и ключевой строки;
4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;
5. В новой таблице:
5.1 Все элементы ключевой строки делятся на ключевой элемент.
5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.
5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.
5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.
5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.
6. Переход к шагу 1. Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.
3.2 Постановка задачи и ее решение
Для производства изделий двух обличий склад может выпустить металла не более 150 кг, причем на изделие первого вида тратится пять килограмм, а на изделие другого вида три килограмма. Требуется планировать производство так, чтобы была обеспечена максимальная прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб. Решение поставленной задачиx1 — количество изделий первого вида. x2 — количество изделий второго вида. F (x) — целевая функция.
5x1 + 3×2 =150×120×225×1, x2≥0F (x) = 7×1 +8×2 maxПриведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, обращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:
5x1 + 3×2+x3 =150×1+x4=20×2+x5 =25×1, x2, x3, x4, x5≥0F (x)= 7×1 +8×2 +x3 +x4 +x5x3,x4,x5 — базисные переменные; x1, x2 — свободные переменные. Соберем симплекс — таблицу, отвечающую каноническому виду:
Таблица2 — Итерация 1Базис
Свободные чл. X1X2X3X4X 5X 31 505 3100X 4 201 0010X 5 250 1001F (x)0−7-8000
Выстроив первую таблицу, обследуем ее на оптимальность, то есть в последней строке таблицы разыскиваемнаибольший по модулю отрицательный элемент, в нашем случае — это -8. Из данного следует, что столбец х2делается ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из обретенных делений находим минимальное, у нас это будет 25. То есть строка, в которой вышло минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1. Строим новую таблицу, следуя алгоритму, приведенному выше. Таблица 3 — Итерация 2Базис
СвободныеX1X2X3X4X5X3755010−3X42010010X22501001F (x)200−70 008
Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу. Таблица 4 — Итерация 3Базис
СвободныеX1X2X3X4X5X115100,20−0,6X4500−0,210,6X22501001F (x)305001,403,8 В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный план-решение поставленной задачи. X1=15; X2=25; Fmax=305.Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день. Вычислительная процедура симплекс-метода проявляется итерационным процессом. Если задача хранит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи умещаются десятки переменных и ограничений (иногда намного больше), и ясно, что глупо решать эти задачи вручную. Симплекс-метод — это метод для электронно-вычислительных машин. Закономерноформирование теории линейного программирования сошлось по времени с развитием ЭВМ. Без них применениеданной теории имело бы оченьограниченную область приложений. Заключение
Нынешняя теория математического обоснования принятия решений во многом строится на теории оптимизации, и не может быть изложена довольно стройно без запаса знаний начал математического программирования и изучения операций. В последние годы в прикладной математике немалое внимание уделяется последнему классу задач оптимизации, содержащихся в отыскивании в заданной области точек максимального или минимального значения некоторой функции, зависящей от значительного числа переменных. Это, так именуемые задачи математического программирования, появляющиеся в самых различных сферах человеческой деятельности и прежде всего в экономических изучениях, в практике планирования и организации потребления. В предоставленной курсовой работе было разобраны некоторые виды решение задач оптимизации. Разобраны этапы построения решения данных задач, предложен алгоритм для решения этих задач, а также представлено решение задач. Список использованных источников
Т. М. Попова. Методы многомерной оптимизации: методические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации» для студентов направления «Прикладная математика"/ сост. — Хабаровск: Изд-во Тихоокеан. гос. ун-та,
2012. — 44 с. Вержбицкий В. М. Основы численных методов: Учебник для вузов. М.: Высшая школа, 2002. — 840 с.
ISBN 5−06−4 020−8Вентцель Е. С. Исследование операций. М.: Высшая школа, 2002. — 255 с. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб.
пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985
Коршунов Ю.М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972
Максимов Ю.А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982
Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575−576.Хемди А. Таха
Глава 3. Симплекс-метод // Введение в исследование операций = OperationsResearch: AnIntroduction. — 7-е изд. — М.: «Вильямс», 2007. —
С. 95−141. — ISBN 0−13−32 374−8.Акулич И. Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
— 319 с. — ISBN 5−06−2 663−9.
