Читать учебное пособие по информатике, вычислительной технике, телекоммуникациям: "Задачи линейного программирования" Страница 2


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

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

    Выбор или написание программы для решения задачи на ЭВМ. Подавляющая часть задач, возникающих на практике, из-за большого числа переменных и зависимости между ними могут быть решены в разумные строки только с помощью ЭВМ. Для решения задачи на ЭВМ прежде всего следует составить (или использовать уже готовую, если аналогичная задача уже решалась на ЭВМ) программу, реализующую выбранный метод решения.

    Решение задачи на ЭВМ. Вся необходимая информация для решения задачи на ЭВМ вводится в память машины вместе с программой. В соответствии с программой решения ЭВМ производит необходимую обработку в веденной числовой информации, получает соответствующие результаты, которые выдает человеку в удобной для него форме.

    Анализ полученного решения. Анализ решения бывает двух видов: формальный (математический), когда проверяется соответствие полученного решения построенной математической модели (в случае несоответствия проверяются программа, исходные данные, работа ЭВМ и т.д.), и содержательный (экономический, технологический и т.п.), когда проверяется соответствие полученного решения тому объекту, который моделировался. В результате такого анализа в модель могут быть внесены изменения или уточнения, после чего весь разобранный процесс повторяется. Модель считается построенной и завершенной, если она с достаточной точностью характеризует деятельность объекта по выбранному критерию. Только после этого модель может быть использована для расчета.

Метод решения задачи

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

    При решении задачи симплекс методом необходимо систему уравнений привести к виду, когда какие-либо r переменные (базисные) выражены через остальные (небазисные), причем свободные члены этих выражений должны быть неотрицательными.

Пусть для определенности X1, X2, X3... Xr выражены через остальные переменные Xr+1, Xr+2, Xr+3,... Xn.

Система ограничений принимает вид: ( 1 ) где

Базис (X1, X2, X3... Xr) обозначим через Б. Пусть все небазисные переменные равны нулю: . Найдем из системы ( 1 ) значение базисных переменных : В результате получаем базисное решение соответствующее базису Б .

Целевая функция F ( X1 , ...., Xn) также выражается через небазисные переменные : Замечаем , что значение целевой функции , соответствующее базисному решению , равно : C0 : FБ = C0.

    Следующим шагом алгоритма является проверка достижения оптимума . Если оптимум не достигнут , то из базиса Б удаляется одна из переменных в небазисные , а вместо нее из числа прежних



Интересная статья: Быстрое написание курсовой работы