- •6.030509, 6.030504, 6.030601Дневной и заочной форм обучения
- •1.Решение систем линейных уравнений методом гаусса – жордана
- •1.1. Основные понятия
- •1.2. Приведение системы линейных уравнений к жордановой форме
- •1.3. Понятие общего, частного и базисного решений.
- •2. Общие свойства задачи линейного программирования
- •2.І. Пример задачи линейного программирования - задача об использовании оборудования.
- •2.2. Задача об использовании сырья.
- •2.3. Задача составления рациона (задача о диете).
- •2.4. Общая постановка задачи линейного программирования
- •2.5. Геометрический метод решения злп.
- •Пример 1
- •2.6. Канонический вид злп.
- •2.7. Понятие опорного плана злп.
- •3. Симплексный метод решения злп
- •3.1. Общая характеристика и основные этапы симплекс – метода
- •3.2. Табличный вид злп. Симплекс - таблицы.
- •3.3. Условие оптимальности опорного плана.
- •3.4. Условие неразрешимости злп из-за неограниченности снизу на одр целевой функции.
- •3.5. Переход к новому опорному плану.
- •3.6. Табличный симплекс-алгоритм.
- •После выбора генерального элемента переходим к таблице 3.11
- •Снова выбираем генеральный элемент и переходим к таблице 3.14
- •3.7. Отыскание исходного опорного плана злп методом искусственного базиса
- •3.8. Вырожденность опорного плана. Зацикливание.
- •Двойственность в линейном программировании
- •Экономическая интерпретация двойственных задач
- •Понятие двойственной задачи
- •Теоремы двойственности
- •Транспортная задача.
- •Задача о перевозках.
- •Общая постановка транспортной задачи.
- •Отыскание исходного опорного плана перевозок.
- •5.4. Циклы пересчета
- •5.4.1. Понятие цикла пересчета
- •5.4.2. Максимально допустимый сдвиг по циклу пересчета.
- •5.4.3. Цена цикла пересчета
- •5.5. Потенциалы.
- •5.6. Алгоритм решения транспортной задачи методом потенциалов.
- •5.7. Открытые транспортные задачи.
- •6. Целочисленное линейное программирование
- •6.1. Общая постановка задачи целочисленного линейного программирования (зцлп).
- •6.2. Целочисленная задача об использовании сырья.
- •6.3. Задача о рюкзаке.
- •6.4. Решение зцлп методом округления.
- •6.5. Метод ветвей и границ.
- •Оптимальный план оптимальный план
- •7. Общая постановка и разновидности задач математического программирования
- •Литература
- •Содержание
Понятие двойственной задачи
Пусть имеется следующая задача линейного программирования, которую будем называть прямой:
Задача 1.
Легко видеть, что к такому виду можно привести любую ЗЛП. Двойственная задача для задачи 1 записывается так:
Задача 2.
Можно показать, что имеет место принцип взаимной двойственности: двойственной к задаче 2 является задача 1. Таким образом, несущественно, какую из задач 1 или 2 называть прямой, а какую двойственной.
Пример 1. Дана ЗЛП
Построить двойственную задачу.
Задачу нужно привести к виду, в котором записана задача 1. Все ограничения, кроме требований неотрицательности переменных, должны быть неравенствами вида ≤. Первое неравенство умножим на (-1). Затем заменим равенство – x1+x2=2 двумя неравенствами –x1+x2≤2 и –x1+x2≥2; второе из этих неравенств умножим на (-1). В результате ЗЛП примет вид:
Теперь запишем двойственную задачу. Каждому линейному ограничению (кроме требований неотрицательности переменных) сопоставим переменную двойственной задачи. Затем, двигаясь вдоль столбцов, запишем целевую функцию и ограничения двойственной задачи. Получим:
Теоремы двойственности
Приведем без доказательства следующие две теоремы.
Первая теорема двойственности.Прямая задача разрешима тогда и только тогда, когда разрешима двойственная. При этомfmax=φmin.
Вторая теорема двойственности.Для того чтобы два допустимых решенияx1',x2',...,xn' и у1', у2',…,ym' пары двойственных задач были оптимальными, необходимо и достаточно, чтобы эти решения удовлетворяли условиям
Вторая теорема двойственности дает возможность находить оптимальное решение одной из пары двойственных задач, имея оптимальное решение другой задачи.
Пример 2. Дана задача
Построить двойственную задачу, решить ее геометрически, а затем с помощью второй теоремы двойственности найти оптимальное решение прямой задачи.
Обратим внимание, что, данная задача записана в форме (4.4) - (4.6). Так как имеет место принцип взаимной двойственности, то будем записывать двойственную задачу в форме (4.1) - (4.3). Получим:
Решим геометрически двойственную задачу. Построим на координатной плоскости граничные прямые (1) 8у1–5у2=11; (2) –у1+3у2=1; (3) –2у1–7у2=–7; находим полуплоскости, определяем ОДР, а затем находим на ОДР оптимальную точку А (см. рисунок). Для отыскания координат точки А решаем систему уравнений
Получаем у1=2, у2=1. Подставив эти значения переменных в целевую функцию, получим φmax=7.
|
|
|
|
|
Y2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
(3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
1 |
|
|
|
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
• |
|
|
|
|
|
|
|
|
(4) |
|
|
|
|
Y1 |
|
|
|
|
|
|
|
|
0,3 |
|
|
ОДР |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
-1 |
|
0 |
|
|
1,4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3,5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
(2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-2,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
(1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 4.1.
Для отыскания оптимального решения исходной задачи воспользуемся второй теоремой двойственности. Для этого запишем систему равенств (4.7) и (4.8)
Подставив у1=2, у2=1, после очевидных преобразований получим систему
Решив полученную систему, найдем х1= 9/19; х2=34/19; х3=0; fmin= 7.