1.6.5 Задания для самостоятельной работы

1. Найти максимум функции

при ограничениях:

2. Найти минимум функции

при ограничениях:

3. Найти максимум функции

при ограничениях:

4. Найти минимум функции

при ограничениях:

5. Найти максимум функции

при ограничениях:

6. Найти минимум функции

при ограничениях:

7. Найти максимум функции

при ограничениях:

8. Найти минимум функции

при ограничениях:

9. Найти максимум функции

при ограничениях:

10. Найти минимум функции

при ограничениях:

11. Найти минимум функции

при ограничениях:

12. Найти максимум функции

при ограничениях:

13. Найти минимум функции

при ограничениях:

14. Найти максимум функции

при ограничениях:

15. Найти минимум функции

при ограничениях:

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

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

1.7.1 Понятие двойственности для симметричных задач

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

(13)

при условиях

, (14)

(15)

Задача, состоящая в нахождении минимального значения функции

(16)

, (17)

, (18)

называется двойственной по отношению к задаче (13)-(15), а переменные –двойственными оценками.

Задачи (13)-(15) и (16)-(18) образуют пару задач, называемую парой взаимно двойственных задач линейного программирования.

Сравнивая пару двойственных задач (13)-(15) и (16)-(18), можно сформулировать правила, по которым составляется двойственная задача:

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

то в двойственной задаче –минимум, и наоборот;

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

бодными членами системы ограничений двойственной задачи;

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

коэффициентами целевой функции двойственной задачи;

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

чи являются транспонированными друг к другу;

5. если прямая задача решается на максимум, и ее система ограниче-

ний состоит из неравенств типа “”,то двойственная задача решается на минимум, и ее система ограничений состоит из неравенств

типа “”;

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

венной, а число ограничений двойственной–числу переменных

прямой;

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