Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Канонический вид задачи линейного программирования.





Не смотря на разнообразие условий (><=) их все можно свести к одной канонической форме, которая имеет вид:

а11х1 + а12х1+…а1n хn1

а21 х1 + а22х2+…а2n хn2

… … … … … … … … … … …(1)

аm1 х1 + аm2х1+…аnm хnm

F=C0 +C1x1+C2x2+…Cnxn→min

В матричном виде это выглядит так:

(А*х)=(В)

F=( C )*(x)→min

Всякое неотрицательное решение системы(1) называется допустимым. Допустимое решение системы точка которая минимизирует F называется оптимальным планом. Оптимальное решение:

-опт. решение

Допустимое решение:
Как правило оптимальное решение бывает единственным.

 

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

Если число переменных равно 2 или 3, то задачу ЛП можно решить геометр. способом, но все ограничения должны иметь вид неравенств. Геометрически задача ЛП задается в виде призмы в основании которого лежит ОДЗ. Но для упрощения призму не рисуют, оставляют только ОДЗ, но тогда для того что бы узнать в какую сторону F убывает или возрастает, находят градиент N.

1.Находим ОДЗ.

2.Находим N.

3.Перпендикулярно N проводим прямую F.

4.Прямую F перемещаем параллельно себе в направлении градиента, первая вершина, в которую входят прямая F-min, последняя вершина которую покидает F-max.

 

Алгебра-симлекс метод. Правила работы по симплекс методу.

1.Выбирается необходимое количество свободных клеток и вычисляется базисный z. Приравниваем свободные переменные к 0, если решение положительное, то оно является опорным и переходим к пункту 2, если решение получилось отрицательным, то нужно перераспределить свободные переменные, по не будет найдено положительное решение, если его не будет, то многоугольник лежит не в первой четверти.



2.если опорное решение найдено, то система записывается в исходном виде:

3.по исходному виду сост. Симплекс таблица.

4.Выбирается разрешающий элемент:

а)в строке F находим положительный элемент, если такого нет, то решение уже найдено, а если положительных элементов несколько, выбирается любое.

б)выбранный элемент определяет разрешающий элемент.

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

5.Методом Жордановых исключений переходим к новой симплекс таблице:

а)разрешающий элемент меняем на обратный

б)оставшиеся в столбце делим на «разрешающий» и меняем знак.

г)все ост. элементы меняются по правилу прямоугольника.

 

Двойственная задача.

Двойственные задачи имеют важное значения:

1.они помогают оценить среднее значение цент на рынке.

2.с их помощью определяется критерий остановки программы расчета задач ЛП.

Решение двойственной задачи равно решению прямой задача, т.е. Fпр.=Fдв.

 

 

7.Нахождение опорного плана тремя методами.

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

Второй способ. Метод наименьшей стоимости состоит в том, что на каждом шаге осуществляется максимально возможная поставка в клетку с минимальным тарифом с ij. Заполнение таблицы начинаем с клетки которой соответствует наименьший элемент с ij из всей матрицы тарифов. Затем остаток по столбцу или строке, которые соотв. по величине с ij и т.д. Другими словами, последовательность заполняемых клеток, определяется по величине с ij, а помещаем в этих клетках величины хij как при решении по правилу С-ЗУ. Может оказаться, что при построении плана, занятых клеток будет меньше, чем m+n-1. В этом случае задача называется вырожденной, тогда в свободную клетку, обычно в ту, которой соответствует наименьший тариф, и в нее помещаем 0, тогда эта клетка считается занятой.

 

Распределительный метод.

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

1.Сост-тся опорный план. Опорный план проверяется на вырожденность. Кол-во занятых клеток должно быть равно m+n-1. Если меньше, то в любую другую свободную клетку заносится 0 ед. груза и клетка считается занятой.

2. Для всех свободных клеток составляются циклы во всех клетках цикла начиная со свободной поочередно ставятся знаки «+» «-»

3.Для всех циклов подсчитывается сумма. Если хотя бы для одного цикла она отрицательна, то план можно улучшить.

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

 

Метод потенциалов.

После нахождения опорного плана перевозок каждому поставщику Ai (в каждой строке) ставится в соответствии некоторое число Ui, а каждому потребителю( каждому столбцу ) Bi ставится в соответствии некоторое число Vj. Числа Ui и Vj наз-ся потенциалами и выбираются так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетке. Ui+Vj=Cij. Т.к. всех потенциалов m+n, а число занятых клеток m+n-1, то одному из неизвестных можно придать произвольное значение. И найти все оставшиеся потенциалы. Затем для проверки оптимальности просматриваются свободные клетки ij и для каждой их них вычисляется оценка:

. План оптимален, если для каждой свобод. клетки Sij≥0. Если есть отрицательные оценки, то переходят к новому плану по правилам распределительного метода. В новом плане определяется потенциалы строк и столбцов. Вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных полученный план будет оптимальным.

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.