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

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

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

Допустимое решение:

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

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

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

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

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

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

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

а)в строке 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. Если есть отрицательные оценки, то переходят к новому плану по правилам распределительного метода. В новом плане определяется потенциалы строк и столбцов. Вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных полученный план будет оптимальным.

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

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