Двойственность в линейном программировании

Основная задача. Найти

(1)

на множестве решений системы

причем, должны выполняться неравенства

(3)

Эта задача называется основной задачей линейного программирования (ОЗЛП). Двойственная задача. Задачей, двойственной к основной задаче линейного про­граммирования, называют следующую задачу.

Найти

g(y) = max (4)

на множестве решений системы

(5)

причем, должны выполняться неравенств

(6)

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

Задачи (1)-(З) и (4)-(6) взаимно двойственны. Они называются симметричными двойст­венными задачами.

Следовательно, имея математическую модель одной из приведенных задач, можно построить модель двойственной к ней задачи. Когда рассматривается пара двойственных задач, то одну из них называют прямой задачей, а другую - двойственной. Сопоставляя пары двойственных задач, можно установить следующие взаимосвязи для симметричных двойственных задач;

1.Каждому i-му ограничению исходной задачи соответствует переменная у,- двой­ственной задачи и, наоборот, каждому k-му ограничению двойственной задачи соот­ветствует переменная исходной задачи.

2.Если прямая задача на минимум, то двойственная к ней - на максимум и наобо­рот.

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

4.Свободные члены Ь,- ограничений прямой задачи являются коэффициентами целе­вой функции двойственной.

5.Матрицы ограничений прямой и двойственной задач являются транспонирован­ными друг к другу.

6.Если прямая задача на минимум, то ее система ограничений представляется в виде
неравенств типа . Двойственная задача решается на максимум, и ее система ограни­чений имеет вид неравенств типа .

7.Число ограничений прямой задачи равно числу переменных двойственной, а чис­ло ограничений двойственной - числу переменных прямой.

8.Все переменные в обеих задачах неотрицательны.

Таким образом, имеют место следующие пары симметричных двойственных задач:

Прямая_задача (*) (**) (***)

Двойственная_задача (+) (++) (+++)

Несимметричные двойственные задачи

Пары двойственных задач с которых исходная задача записана в канонической форме иногда называют несимметричными двойственными задачами. Задачи (1)- (3) и (13)- (14) представляют собой пару несимметричных двойственных задач:

Таблица (max, min, несимм)

Прямая_задача (* (**) (***)

Двойственная_задача (+) (++) (+++

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

Из рассмотрений частных случаев двойственных задач можно получить двойствен­ную задачу, когда в ограничения исходной задачи входят как неравенства, так и равенст­ва. В этом случае нужно отметить, что каждому i-му ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности , а i-му равенству - переменная без ограничения на знак. Наоборот, неотрицательной переменной соответствует в двойственной задаче j-oe ограничение-неравенство, а произвольной переменной - равенство. Такую пару двойственных задач называют двойственными задачами, записанными в общей форме.

Общее правило построения двойственных задач

1.Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи и, наоборот, каждому j-му ограничению двойственной задачи соот­ветствует переменная х ; исходной задачи.

2.Если прямая задача на максимум, то двойственная к ней - на минимум и наоборот.

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

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

5.Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.

6.Если прямая задача на максимум, то ее система ограничений представляется в ви­де неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

7.Число ограничений прямой задачи равно числу переменных двойственной, а чис­ло ограничений двойственной — числу переменных прямой.

8.Каждому i-му ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности ( ), а i-му равенству - переменная

без ограничения на знак. Наоборот, неотрицательной переменной соответствует в двойственной задаче j-oe ограничение-неравенство, а произвольной переменной - равенство.

Схема анализа урока

1. Общие сведения: дата, класс, школа, фамилия, имя, отчество учителя. Тема учебной программы, тема урока.

2. Соблюдение техники безопасности и санитарно-гигиенических норм работы с компьютером.

3. Структура урока. Основные этапы урока, назначение и длительность. Сочетание самоуправления и управления учителем. Индивидуальная, парная, групповая и совместная работа класса. Этапы повторения и закрепление материата. способы

4. Цели, которые намечал учитель на урок, их достижение.

5. Сравнение содержания урока с материалом школьного учебника.

6. Оценка содержания урока с точки зрения обще дидактических принципов:

о научность - учет новейших достижений в информатике на уроке (понятие исполнителя, синтаксические диаграммы, доказательство правильности

алгоритмов и т.п.);

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

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

о связь с практикой - прикладные задачи, ориентация содержания на требования жизни в компьютерном обществе.

7. Методы деятельности учителя на уроке. Привлечение учащихся для подготовки средств к уроку. Подготовка вычислительной техники в начале урока (или до него). Свобода учителя во владении материалом. Момент ответа на актуальные вопросы (по ходу урока или в конце). 11ндивид> ализация обучения — разные уровни заданий, привлечение сильных учащихся для помощи слабым и т.д. Приемы учителя для удержания внимания, действия при обнаружении ошибки на доске, в программе, в отчете.

8. Методы формирования и закрепления интереса к материалу. Стимулирование мыслительной деятельности учащихся. Источник заданий (из учебника, другой литературы, изобретение учителем по ходу урока). Другие известные и нестандартные методы обучения, использованные на уроке.

9. Работа з'чашихся на уроке. Степень интереса к изучаемому материалу. Активность и самостоятельность обучаемых. Сознательность усвоения — усвоение смысла действий за ЭВМ. Доступность — стандартность терминологии, учет уровня подготовленности класса, выделение уровней усвоения.

10. Эффективность обучения - насыщенность учебного времени, отсутствие постороннего материала, оптимальность выбора ПС. Взаимоотношения учителя и учащихся: авторитарные, либеральные, сотрудничество. Организованность и дисциплинированность учащихся на уроке - отношение к вычислительной технике, соблюдение техники безопасности при работе с компьютером. Умение самостоятельно овладевать знаниями с помощью справочного материала, компьютера, учебника.

11. Обратная связь. Система контроля знаний у данного учителя. Использование компьютера для проверки знаний — контролирующие программы, самоконтроль запуском программы, взаимоконтроль с товарищем. Объективность оценки знаний. Критерии оценок данного учителя (известны ли они учащимся?). Возможность автоматизации такой системы контроля. Оценка трудоемкости типичного домашнего задания (выполните сами и «замерьте» время).

12. Воспитательный эффект.

13. Выводы