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

Основные понятия и принципы исследования операций

Исследование операций (ИО) (Operations Research) — дисциплина, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе матем. И статистического моделирования. Иногда используется название математические методы исследования операций. Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

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

Параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А-i, А₂, ..., А_т в пункты назначения В_1г В₂, ..., В_п, то элементами решения будут числа Xj, показывающие, какое количество груза будет отправлено из пункта отправления i в пункт назначения j. Набор чисел Xj образует решение.

Кроме элементов решения, которыми мы можем распоряжаться, в любой задаче ИО имеются еще и заданные условия, которые фиксированы с самого начала и нарушены быть не могут (например, грузоподъемность машины; размер планового задания; весовые характеристики оборудования и т. п.). В частности, к таким условиям относятся средства (материальные, технические, людские), которыми мы вправе распоряжаться, и иные ограничения, налагаемые на решение. В своей совокупности они формируют так называемое «множество возможных решений». Обозначим это множество одной буквой X. Речь идет о том, чтобы в множестве возможных решений X выделить те решения, которые с той или другой точки зрения эффективнее (удачнее, предпочтительнее) других.

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (его часто называют «целевой функцией»). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. «Лучшим» будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели.

Чтобы выбрать показатель эффективности W нужно спросить себя: чего мы хотим, к чему стремимся, предпринимая операцию? Выбирая решение, мы, естественно, предпочтем такое, которое обращает показатель эффективности W в максимум (или же в минимум). Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум. Если показатель эффективности желательно максимизировать, мы это будем записывать в виде W —max, а если минимизировать — W —min. План снабжения предприятий. Задача операции — обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R - min).

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

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

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

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

2. Типичные задачи исследования операций

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

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

План снабжения предприятий. Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями какими-то путями сообщения (железнодорожными, водными, автомобильными, воздушными) со своими тарифами. Требуется разработать такой план снабжения предприятий сырьем , чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки. Задача операции — обеспечить снабжение сырьем при минимальных расходах на перевозки. Показатель эффективности R — суммарные расходы на перевозки сырья за единицу времени, например, месяц (R ^ min).

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

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

Противолодочный рейд. Известно, что в некотором районе морского театра военных действий находится подводная лодка противника. Группа самолетов противолодочной обороны получила задание: разыскать, обнаружить и уничтожить лодку. Требуется рационально организовать операцию (рейд): выбрать маршруты самолетов, высоту полета, способ атаки так, чтобы с максимальной уверенностью обеспечить выполнение боевого задания.

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

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

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

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

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

3. Понятие модели и моделирования

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

или времени. Создавая что-то новое, мы первоначально формируем некоторый образ. Управляя чем-либо, мы пытаемся анализировать, к каким последствиям приведет управление. Перечисленные задачи требуют представления информации об объекте в виде некоторого образа. В связи с этим в познавательной и практической деятельности большую роль играют модели и моделирование. Особенно незаменимо моделирование при работе со сложными объектами (в частности, экономическими).

Модель — это упрощенное подобие объекта, которое воспроизводит интересующие нас свойства и характеристики объекта-оригинала или объекта проектирования.

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

Моделирование связано с выяснением или воспроизведением свойств какого-либо реального или создаваемого объекта, процесса или явления с помощью другого объекта, процесса или явления. Моделирование — это построение, изучение и применение моделей реально существующих или проектируемых объектов. Причины, по которым мы прибегаем к использованию моделей вместо прямого взаимодействия с реальным миром:

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

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

3) необходимость прогнозирования.

Среди других причин можно назвать следующие:

• исследуемый объект либо очень велик (модель Солнечной системы), либо очень мал (модель атома);

• процесс протекает очень быстро (модель двигателя внутреннего сгорания) или очень медленно (геологические модели);

• исследование объекта может привести к его разрушению (модель самолета, автомобиля). Цели моделирования

Решаются 2 задачи — экспертная и конструктивная.

В экспертной задаче на основании имеющейся информации описывается прошлое, настоящее и предсказывается будущее. Суть конструктивной задачи заключается в том, чтобы создать нечто с заданными свойствами. Для решения экспертных задач применяют так называемые описательные модели, а для решения конструктивных — нормативные.

Описательные модели предназначены для описания свойств или поведения реальных объектов. Примеры. План города, отчет о деятельности фирмы, психологическая характеристика личности. Можно назвать цели описательного моделирования в зависимости от решаемых задач: изучение объекта — наиболее полно и точно отразить свойства объекта; управление — наиболее точно отразить свойства объекта в рабочем диапазоне изменения его параметров; прогнозирование — построить модель, способную наиболее точно прогнозировать поведение объекта в будущем; обучение - отразить в модели изучаемые свойства объекта. Построение описательной модели

-►^Модель ^

Нормативные модели (прагматические) предназначены для указания целей деятельности и определенного порядка (алгоритма) действий для их достижения. Цель — образ желаемого будущего, т. е. модель состояния, на реализацию которого и направлена деятельность. Алгоритм — образ (модель) будущей деятельности. При нормативном моделировании обычно не используют слово «модель» — чаще говорят «проект», «план».Примеры. Проекты машин, зданий; планы застройки; законы; уставы организаций и должностные инструкции, бизнес-планы, программы действий, управленческие решения.

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

Линейное программирование - целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. Нелинейное программирование - целевая функция и ограничения нелинейны. Нелинейное программирование принято подразделять следующим образом: выпуклое программирование - целевая функция выпукла (рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача; квадратичное программирование - целевая функция квадратична, а ограничениями являются линейные равенства и неравенства.

Среди задач математического программирования самыми простыми являются задачи линейного программирования. Для этих задач характерно: 1) целевая функция (показатель

эффективности) линейно зависит от элементов решения Х₁₉Х₂2) ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно

JC^ 9 * * * '

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

Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Допустим, что имеется всего четыре вида продуктов: П₁, П₂, П₃ и П₄. Стоимость единицы каждого продукта с₁, с₂, с_з и с₄. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков - не менее в1 единиц, углеводов - не менее в₂ единиц, жиров - не менее в_зединиц. Для продуктов П₁, П₂, П₃ и П₄ содержание белков, углеводов и жиров известно и задано в таблице, а ,- j - определенные числа, первый индекс указывает на номер продукта, а второй - на номер элемента (белки, углеводы, жиры).

Требуется составить такой пищевой рацион (то есть назначить количества продуктов П1, П2, П3 и П4, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Составим математическую модель.

Обозначим через ^х1, ^х2, ^х3' ^х4 -

количества продуктов П₁, П₂, П₃ и П₄, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона L;

х..

продукт	белки	углеводы	жиры
П1	ац	а12	а1з
П2	а21	а22	а2з
Пз	аз1	аз2	азз
П4	а41	а42	а4з

^X1, ^X2 ' ^X3 , ^Х4 ;

решения

L = C₁X₁ + C₂X₂ + C₃X₃ + C₄X₄ . Запишем в виде формул ограничительные условия по белкам,

углеводам и жирам. Учитывая, что в одной единице продукта П₁ содержится а₁₁ единиц белка, а в х₁ единицах - ац х₁ единиц белка, в х₂ единицах продукта П₂ содержится а₂₁ х₂ единиц белка и так

линейно

стоимость

зависит

от

элементов

то

есть

> b1 ^a12 ^X1 + ^a22 ^X2 + ^a32 ^X3 + ^a42 ^X4 > ^b2+ a23X2 + a₃₃X₃ + ^^x^ > b^+ ^21X2 + + ^41X4<(*). Эт идалее, получим три неравенства:линейные неравенства представляют собой ограничения, накладываемые на элементы решения ^X₁ ?^X₂ ?^X₃?^X₄. Таким образом, поставленная задача сводится к следующей: найти такиенеотрицательные значения переменных ^X₁? ^х₂? ^х₃? ^X₄, чтобы они удовлетворяли ограничениям- неравенствам (*) и одновременно обращали в минимум линейную функцию этих переменных

L = c_tx_t + c₂x₂ + C3X3 + c₄x₄ ^ min.

6. Целочисленное линейное программирование

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

Пример. Вернемся к оптимизационной задаче о столах и шкафах.

z = 60x + 240y ® max,

(9.2)

x ≥ 0, y ≥ 0; x, y — целые.

Сначала из соотношений (9.2) определим диапазон возможных значений х. Пусть у = 0. Тогда из первого неравенства следует, что х £ 37,5, из второго — что х £ 92. Отсюда 0 £ х £37. Аналогично заключаем, что 0 £ у £13.

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

В результате получаем такой ответ:

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

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

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

Предположим, что задача линейного программирования задана в следующем виде:

Составим другую задачу линейного программирования, число переменных которой равно числу ограничений данной задачи, т. е. m.

Обозначим их буквами у₁, y₂, ..., у_m (они записаны справа от системы ограничений приведенной задачи). Эта задача имеет вид:

Вторая задача называется двойственной, или сопряженной для первой, а первая — прямой, или основной.

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

Отметим особенности пары взаимно двойственных задач:

1) Если основная задача — задача на максимум (минимум), то система ограничений должна состоять из неравенств вида ≤ ( ≥ ), и в таком случае двойственная задача должна быть задачей на минимум (максимум), а ее система ограничений должна состоять из неравенств вида ≥ ( ≤ ).

2) В основной задаче все переменные должны быть неотрицательными.

3) Коэффициентами целевой функции F(Y) двойственной задачи являются свободные члены системы ограничений основной задачи, и их число равно m.

4) Основная матрица системы ограничений двойственной задачи получается транспонированием матрицы системы ограничений основной задачи.

5) Свободными членами системы ограничений двойственной задачи являются коэффициенты целевой функции основной задачи.

6) Все переменные двойственной задачи неотрицательные.

Теорема 5.1. Если одна из пары двойственных задач линейного программирования имеет решение, то и другая задача имеет решение, и при этом значения целевых функций этих задач равны: L(X_опт) = F(Y_опт).

Теорема 5.2. Произвольное допустимое базисное решение одной задачи из пары двойственных оптимально тогда и только тогда, когда система ограничений двойственной задачи совместна.

Теорема 5.3. Если целевая функция одной из пары двойственных задач не ограничена снизу (сверху), то система ограничений другой задачи этой пары несовместна.

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

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

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

или

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

У. 1. Неравенство равносильно равенству   и простейшему неравенству .

У. 2. Неравенство равносильно равенству   и простейшему неравенству .

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

У. З. Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных:

9. Симплексный метод решения ЗЛП

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

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

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

Таким образом, последовательность шагов симплекс-метода — это переход от вершины к вершине многоугольника допустимых планов с целью отыскания той вершины, в которой Z принимает наибольшее значение.

Дата добавления: 2018-04-15; просмотров: 485; Мы поможем в написании вашей работы!
Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!