Курсовая работа по ЭММ

х1 0, х2 0,..., хn 0 или части переменных, но это, впрочем, не обязательно. В зависимости от характера функции f, g1, ...,gm различают разные виды математического программирования. Наиболее простой и часто встречающийся случай, когда эти функции являются линейными, т.е. каждая из них имеет вид а1х1+а2х2+ ...+аnхn +b.

Дадим теперь общую формулировку задачи линейного программирования. Пусть S - система линейных ограничений ( т.е. линейных уравнений или нестрогих линейных неравенств) с n переменными х1, х2,..., хn , а f(х) - целевая функция вида f(х) = с1х1 + с2х2 + ...+ сnxn + c.

Требуется решить задачу f(х) max (min) при условиях S.

Обычно система S включает в себя условия неотрицательности всех переменных: х1 0, х2 0,..., хn 0, (1.3)

что вытекает из реального смысла чисел х1, х2,..., хn. Будем называть эти условия тривиальными ограничениями.

1.1 Каноническая задача. В этом случае система S, помимо тривиальных ограничений (1.3), включает в себя только уравнения. Определение: Если ищется max значение функции цели, а все ограничения являются равенством, все переменные не отрицательны, то такая система - называется системой в каноническом виде, а задача - является задачей в канонической форме. В этом случае модель задач можно записать в векторной форме: f(х) = с1х1 + с2х2 + ...+ сnxn max А1х1 + А2х2 + ... + Аnхn = B xj = 0 (j =1,n)

A1 = A2 = B =

Записать задачу в каноническом виде: f = -х1+2х2-х3+х4 min xj=0 (j=1; 4)

Вместо того, чтобы исследовать функцию f на min, будем исследовать на f1= - f на max. В ограничениях содержащих к левой части прибавим дополнительную не отрицательную переменную. В ограничениях содержащих - в левой части вычтем не отрицательную дополнительную переменную. Условие не отрицательности в равенство не переводится.

f1 = -f =х1 - 2х2 + х3 - х4 max

хj 0 (j =1; 7) Вводимые дополнительные переменные имеют экономический смысл. В ограничении исходной задачи, отражается расход и наличие ресурсов, то числовое значение дополнительной переменной, показывает количество не израсходованного ресурса определенного вида. Замечание: Если переменная хк не подчинена условию не отрицательности, ее нужно заменить на разность двух не отрицательных величин xk = uk + vk . Определение: Совокупность не отрицательных чисел х1, х2,..., хn , удовлетворяющих ограничениям задачи, называются допустимым решением или просто планом задачи. План Х* = (х1*, х2*, ..., хn*) при котором целевая функция достигает своего экстремального значения, называется оптимальной. Не нулевые допустимые решения задачи, называются базисными решениями, если соответствуют им векторы Аj образуют линейно не зависимую систему.

1.2 Симплекс - метод .

С самого начала укажем, что симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования. Для работы по симплекс-методу требуется: 1. привести задачу к канонической форме; 2. представить ее в векторной форме; 3. заполнить первую симплексную таблицу; 4. проверить план на оптимальность; 5. если план не оптимален, то выбрать разрешающий элемент, произвести пересчет всех элементов симплексной таблицы и перейти к п.4

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

СбХбпланС1

х1С2

х2.....

....Сn

хn j

0 1 2 ... n В верхней строке записывают коэффициенты при переменных целевых функций. В столбцы х1, х2, ..., хn - заносят элементы векторов А1, А2,Аn. В столбец план - заносят компоненты вектора В. Столбец Хб - отображает переменные входящие в базис. Их индексы совпадают с индексами базисных векторов. Столбец Сб - коэффициенты при базисных переменных в целевой функции. Проверка плана на оптимальность. Нижняя строка симплекс-таблицы j - называется индексной. 0 = Сб *В; j = Сб*хj - Сj или j = Cб *Аj - Cj Она служит для проверки опорного плана на оптимальность. Если все j 0, то все планы являются оптимальными.

Переход от одного базисного решения к другому, осуществляется исключением из базиса какого-нибудь из векторов и введением в него нового вектора. 1. В качестве разрешающего столбца выбирают столбец для которого элемент индексной строки р является самым маленьким отрицательным числом. 2. Находим отношения компонент столбца план к неотрицательным элементам разрешающего столбца. 3. Выбираем наименьшее из данных отношений. Строка с ним называется разрешающей. 4. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент аqp. Индексы q и p обозначают, что из базиса выводится Аq, а вместо него вводится Аp. Разрешающий элемент обычно обводят в таблице. 5. На месте разрешающего элемента в новой симплекс-таблице ставят 1, остальные элементы разрешающего столбца 0. 6. Все элементы разрешающей строки делят на разрешающий элемент. 7. Остальные элементы симплекс-таблицы пересчитывают по формулам Жордана-Гаусса.

Замечание: Если по индексной строке определили разрешающий столбец, но в нем все элементы не положительные, то задача не имеет решений.

Следующий этап - это определение оптимального плана из симплекс-таблицы Х* = (х1*, х2*, ..., хn*). Оптимальное решение выписывают из столбцов Хб и план. Столбец Хб - показывает, какие неизвестные отличны от 0. Столбец план - показывает, чему они равны. 0 - в последней симплекс-таблицы равно max значению целевой функции. Алгоритм работы по симплекс-методу: 1. Выделяем исходный допустимый базис и заполняем первую таблицу. 2. Если в последней строке полученной таблицы, кроме, быть может, первого числа, нет положительных чисел, то базисное решение является оптимальным - задача решена. 3. Пусть среди указанных в пункте 2 чисел имеется положительное число( скажем, в столбце хj). Отмечаем столбец Хj вертикальной стрелкой. Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min f = - - задача решений не имеет. 4. Пусть среди просмотренных в п.3 чисел имеются положительные числа. Для каждого из таких чисел a составляем отношение, где b - первое число в той же строке (свободный член). Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке базисного неизвестного хi . Отмечаем эту строку горизонтальной стрелкой. Число , стоящее в отмеченной строке и отмеченном столбце, называется разрешающим элементом таблицы. 5. Переходим к новой таблице. Для этого отмеченную строку умножаем