Линейное программирование
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
ми подготовки исходных данных, средствами их анализа и представления полученных результатов. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
рационального использования сырья и материалов;
задачи оптимального раскроя;
оптимизации производственной программы предприятий;
оптимального размещения и концентрации производства;
составления оптимального плана перевозок, работы транспорта;
управления производственными запасами;
и многие другие, принадлежащие сфере оптимального планирования.
Наиболее разработанным и широко применяемым разделом математического программирования является линейное программирование, целью которого служит отыскивание оптимума (max, min) заданной линейной функции при наличии ограничений в виде линейных уравнений или неравенств в этом и заключается актуальность данной работы.
Целью данного РГЗ является выполнение расчетно-графической работы, закрепление знаний и навыков, необходимых для математического моделирования социально-экономических процессов. А также, приобретение навыков работы с программными пакетами Линейное программирование и Дискретное программирование.
Теоретическая часть
Табличный симплекс-метод
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
F=a01x1+a02x2+...a0nxn +b0 > max
Исходная таблица для задачи имеет следующий вид:
x1x2...xn-1xnbF- a0,1-a0,2...-a0,n-1- a0,n-b0xn+1a1,1a1,2...a1,n-1a1,nb1xn+2a2,1a2,2...a2,n-1a2,nb2.....................xn+mam,1am,2...am,n-1am,nbm, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.
Алгоритм симплекс-метода.
Подготовительный этап
Приводим задачу ЛП к каноническому виду
F=a01x1+a02x2+...a0nxn +b0 > max
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "?" так же меняются на противоположные. В случае если условие содержит знак "?" - коэффициенты запишутся без изменений.
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче :
x1x2...xn-1xnbF- a0,1-a0,2...-a0,n-1- a0,n-b0xn+1a1,1a1,2...a1,n-1a1,nb1xn+2a2,1a2,2...a2,n-1a2,nb2.....................xn+mam,1am,2...am,n-1am,nbm
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены):
1.Если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2.
2.Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Затем снова пересчитываем симплекс-таблицу согласно правилам.
.Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
.Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность:
1.Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
2.Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0) a0,l=min{a0,i }. Первый столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
/ak,l =min {bi/ai,l } при ai,l>0, bi>0
- cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
:">Пересчитываем симплекс-таблицу по формулам :
1.Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
2.Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
.Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимал