55. Теорема двоїстості. Двоїстий критерій оптимальності. Двоїстий симплекс-метод.
Теорема
1. (Первая основная теорема двойственности.)
Если одна из двойственных задач имеет
оптимальное решение, то двойственная
ей задача также имеет оптимальное
решение, причем экстремумы целевых
функций равны, т.е. .
Если одна из двойственных задач не имеет оптимального решения, то другая задача также не имеет оптимального решения, причем если одна из задач не имеет оптимального решения из-за неограниченности целевой функции, то другая из-за несовместности системы ограничений.
Вторая теорема двойственности для несимметричных двойственных задач сформулируется так:
Теорема
2. (Вторая основная теорема двойственности.)
Для того чтобы допустимые решения
и
несимметричной пары двойственных задач
были соответственно оптимальными
решениями, необходимо и достаточно,
чтобы для любого j выполнялось равенство
Доказательство.
Необходимость. Дана несимметричная пара двойственных задач: найти наибольшее значение функции
при ограничениях:
Двойственная задача: найти наименьшее значение функции
при ограничениях:
где
yi свободны по знаку,
.
Пусть
и
- оптимальные решения соответствующих
задач, тогда по первой теореме
двойственности
,
или
Подставим
вместо
получим
В правой части поменяем местами знаки суммирования, получим:
Перенесем
все в левую часть и вынесем за скобки
общий множитель
:
По
условию
и
,
т.е. сумма неположительных слагаемых
равна 0, а это возможно только тогда,
когда каждое слагаемое равно нулю, т.е.
Достаточность. Предположим, что для допустимых решений и несимметричной пары двойственных задач выполняются равенства
Просуммируем это равенство по всем j и проведем преобразования, противоположные предыдущим:
Следовательно, и оптимальные решения соответствующих двойственных задач.
Первый критерий оптимальности
Решение
оптимально тогда и только тогда, когда
существует решение
такое, что
Доказательство. Необходимость следует из первой теоремы двойственности.
Достаточность следует из достаточного условия оптимальности.
Второй критерий оптимальности
Чтобы допустимые решения х, у пары двойственных задач (I), (II) были оптимальны, необходимо и достаточно, чтобы выполнялись УДН.
Критерий разрешимости задачи ЛП
Точной верхней гранью (супремумом) функции L(х) на множестве D называется такое число М*, что
56. Керування подіями. Програмування обробки подій.
Поскольку сущность объектно-ориентированного программирования в конечном счете сводится к обмену сообщениями между взаимодействующими объектами, события должны занимать определенное место в этой схеме. В каком-то отношении они нормально вписываются в нее: объект-источник отправляет сообщение, которое указывает на возникновение события.
Но при этом возникает очевидная проблема: каким объектам следует отправлять сообщения? Оповещать о каждом событии все объекты, в настоящий момент существующие в программе? Это было бы слишком неэффективно. Для большийства объектов событие не представляет ни малейшего интереса, а быстродействие станет неприемлемо низким.
Вместо этого VB .NET пытается ограничить число получателей события, для чего используется модель «подписка/публикация». В этой модели объекты-приемники событий регистрируют объекты-источники тех событий, которые представляют для них интерес. На события от одного источника могут подписаться сразу несколько объектов-приемников. О том, что источник инициировал событие, оповещаются только зарегистрированные получатели.
Впрочем, реализовать подобную схему не так просто. Какие сообщения должны передаваться приемнику от источника? Как организовать их отправку? Что должно происходить при получении сообщения? Как говорилось выше, взаимодействие между объектами на базе обмена сообщениями строится на вызове методов класса-приемника. В конечном счете обработка событий строится по тому же принципу, но при этом приходится учитывать ряд дополнительных тонкостей.
Общий смысл происходящего заключается в том, что при возникновении события объект-источник вызывает заранее определенные функции объектов-приемников. Вызываемая функция приемника регистрируется источником события одновременно с регистрацией объекта-приемника. Такая схема называется оповещением посредством обратного вызова (callback notification), потому что источник события вызывает метод приемника по заранее известному ему адресу. На рис. 6.1 показан объект-«начальник» с событием HighRating, при возникновении вызываются разные методы объектов-приемников. Во второй половине этой главы будет рассказано, как это происходит в VB .NET.