Решение задач линейного программирования

    Дисциплина: Разное
    Тип работы: Лабораторная
    Тема: Решение задач линейного программирования

    Министерство общего и профессионального образования
    Российской Федерации
    Воронежский Государственный Архитектурно – Строительный
    Университет
    Кафедра Экономики и управления строительством
    ЛАБОРАТОРНАЯ РАБОТА
    На тему
    «Решение задач линейного программирования»
    Выполнил
    Студент 4 курса
    ФЗО ЭУС
    Сидоров В.В.
    Руководитель
    Богданов Д. А.
    Воронеж – 2002 г.
    ЛАБОРАТОРНАЯ РАБОТА № 11
    РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
    Цель работы:
    изучение принципов составления оценочных характеристик для задач линейного программирования, получение навыков использования симплекс-метода для решения задач линейного
    программирования, усвоение различий получаемых результатов, изучение табличной формы применения
    симплекс-метода.
    ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
    Стандартная задача линейного программирования состоит из трех частей:
    целевой функции (на максимум или минимум) - формула (1.1), основных oграничений
    - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3)
    (1.1)
    i = 1,… m
    (1.2)
    (1.3)
    Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция стремится к максимуму (если стремилась к минимуму, то
    функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака
    надо в правую часть каждогo такого k-го неравенства добавить искусственную переменную u
    надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной х
    , то их можно ввести путем замены всех вхождений этой
    переменной комбинацией
    = х
    , где х
    и х
    базис, т.е. набор переменных х
    в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель а
    . Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы х
    и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате
    приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из
    целевой функ
    ции вычитается их сумма, умноженная на М, т.е.
    (так называемый модифицированный симплекс-метод). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической рабо
    -ты по нахождению решения задачи линейного программирования (по варианту простого симплекс-метода) будут использоваться алгоритм итерационного (многошагового) процесса
    нахождения решения и два типа оперативных оце
    -нок, позволяющих делать переходы от одного шага к другому, а также показы
    -вающих, когда итерационный процесс остановится и результат будет найден.
    Первая оценка - это дельта-оценка, для переменной х
    она имеет вид:
    (1.4)
    Здесь выражение i
    B означает, что в качестве коэффициентов целевой функ
    -ции, представленных в сумме выражения (1.4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Пере
    -менными а
    являются множители матрицы коэффициентов А при основных ог
    -раничениях, рассчитанные на данном шаге итерационного процесса. Дельта-оценки рассчитываются по всем переменным х
    i, имеющимся в задаче. Следует отметить; что дельта-оценки базисных переменных равны нулю. После нахож
    -дения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка, переменная х
    k, ей соответствующая, будет вводиться в базис. Другой важной оценкой является тетта-оценка, имеющая вид:
    (1.5)
    Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере
    -менную х
    k и элементы столбца Х
    B делим на соответствующие (только положи
    тельные) элементы столбца матрицы А, соответствующего переменой x
    k. Из полученных результатов выбираем минимальный, он и будет тетта-оценкой, а
    -й элемент столбца
    лежащий в одной строке с тетта-оценкой, будет выво
    -диться из базиса, заменяясь элементом x
    k, полученным по дельта-оценке. Для осуществления такой замены нужно в i-ой строке k - гo столбца матрицы А сде
    -лать единицу, а в остальных элементах k-го столбца сделать нули. Такое преоб
    -разование и будет одним шагом итерационного процесса. Для осуществления такого преобразования используется метод Гаусса. В соответствии с ним i-я строка всей матрицы А, а
    также i-я координата Х
    делятся на a
    ik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата Х
    B умножаются на элемент (-а
    1k). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также Х
    1, и (-а
    1k)*Х
    i;. Аналогичные действия производятся для всех остальных строк кроме i-ой (базисной) строки. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех ос
    -тальных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма, Шаги алгоритма симплекс-метода продолжаются до тех пор, пока не будет получен
    один из следующих результатов.
    • Все небазисные дельта-оценки больше нуля — найдено решение задачи ли-
    нейного программирования, оно представляет из себя вектор компонент х;, значения которых либо равны нулю, либо равны элементам столбца Х, та
    кие компоненты стоят на базисных местах (скажем, если базис образуют пе
    -ременные х
    2, x
    4, х
    5, то ненулевые компоненты стоят в векторе решения зада
    -чи линейного программирования на 2-м, 4-м и 5-м местах).
    • Имеются небазисные дельта-оценки, равные нулю
    , тогда делается вывод о том, что задача линейного программирования имеет бесчисленное множество решений (представляемое лучом или отрезком). Подробно рассматривать случаи
    такого типа, а также отличия между решениями в виде луча и отрезка мы не будем.
    Возможен вариант получения столбца отрицательных элементов на отрица
    -тельной рассчитанной дельта-оценке, в такой ситуации нельзя вычислить тетта-оценки. В этом случае делается вывод, что система ограничений задачи линейного программирования
    несовместна; следовательно, задача линейного программирования не имеет решения.
    Решение задачи линейного программирования, если оно единственное, следует
    записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функ
    -ции в точке решения
    *(Х*).
    В других случаях (решений много или они отсут
    -ствуют) следует словесно описать полученную ситуацию. Если решение задачи линейного программирования не будет получено в течение 10-12 итераций симплекс-метода, то следует
    написать, что решение отсутствует в связи с неог
    -рачниченностью функции цели.
    Для практического решения задачи линейного программирования сим
    пл
    екс-методом удобно пользоваться таблицей вида (табл. 11.1):
    Таблица 1.1
    Базисные
    Целевые
    Правые
    компоненты
    Коэффиц.
    Части
    Базиса
    ограничен
    Задание
    Необхо...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены