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

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

    Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим

    программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под

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

    отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание

    изучаемого явления и исследование с помощью математического аппарата.

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

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

    улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.

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

    линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной —

    происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно

    описывается линейными моделями.

    Основные формы задачи ЛП.

    Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.

    Стандартная задача ЛП.

    или, в матричной записи,

    где

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

    Каноническая задача ЛП.

    или, в матричной записи,

    Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

    Общая задача ЛП.

    В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:

    Здесь

    . Ясно, что стандартная задача получается как частный случай общей при

    ; каноническая — при

    Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.

    При изучении задач ЛП сложилась определенная терминалогия. Линейная форма

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

    Рассмотрим задачу ЛП

    или, в матричной записи,

    Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от

    переменных

    вида

    или, в матричной записи,

    где

    Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных

    столько же, сколько строк в матрице

    задачи (1). Матрица ограничений в (3) — транспортированная матрица

    накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется

    прямой.

    Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.

    Теорема равновесия. Пусть

    то

    Язык: Русский

    Скачиваний: 142

    Формат: Microsoft Word

    Размер файла: 60 Кб

    Автор: Виктор

    Скачать работу...

    Забрать файл

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


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


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