Файл: Практикум Челябинск 2019.pdf

31
S(Y) = b
1
y
1
+ b
2
y
2
+ b
3
y
3
+ … + b
m
y
m

min
при ограничениях:
,...,
2
,
1
;
,...,
2
,
1
;
0 2
2 1
1 2
2 2
22 1
12 1
1 2
21 1
11
n
j
m
i
y
c
y
a
y
a
y
a
c
y
a
y
a
y
a
c
y
a
y
a
y
a
i
n
m
mn
n
n
m
m
m
m






















Если одна из двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, причем для любых оптимальных решений Х и Y выполняется равенство F(X)
max
= S(Y)
min
Если одна из двойственных задач неразрешима ввиду того, что F(X)
max
→ ∞
(или S(Y)
min
→

∞), то другая задача не имеет допустимых решений.
Пример 1.3. Для исходной задачи примера 1.1 составить двойственную и найти ее решение, используя надстройку Поиск решения.

32
Рис. 1.3.1. Схема формирования двойственной задачи
Ввод зависимостей для двойственной задачи показан на рисунке 1.3.2.
Рис. 1.3.2. Ввод зависимостей для двойственной задачи
Левая часть ограничений представляет собой произведение матрицы коэффициентов ограничений на вектор переменных.
Целевая функция записывается как произведение транспонированного вектора коэффициентов целевой функции на вектор переменных.
Для решения двойственной задачи воспользуемся надстройкой Поиск
решения. Заполненное диалоговое окно Поиск решения показано на рисунке 1.3.3. Параметры: Линейная модель, Неотрицательные значения.

33
Рис. 1.3.3. Окно Поиск решения с ограничениями для двойственной задачи
Результаты решения двойственной задачи приведены на рисунке 1.3.4.
Рис. 1.3.4. Решение для двойственной задачи
Минимальное значение S(Y)=9200 достигается в точке Y=(16,363;
7,272; 0; 0). Видим, что выполняется равенство F(X)
max
= S(Y)
min
, т.е. минимальное значение целевой функции двойственной задачи равно максимальному значению целевой функции исходной задачи.
Открыв отчет по устойчивости (рис. 1.3.5), можно увидеть новые двойственные оценки (в столбце Теневая цена) и убедиться, что значения переменных при решении задачи на максимизацию становятся двойственными оценками при задаче на минимизацию, и наоборот
(сравните с рисунком 1.1.13).

34
Рис. 1.3.5. Отчет по устойчивости для двойственной задачи
Варианты заданий для самостоятельной работы
Для каждого варианта задания 1.1 необходимо составить двойственную задачу и решить ее. Провести анализ чувствительности.
Контрольные вопросы
1. Что называется планом задачи линейного программирования?
2. Может ли оптимальное решение находиться вне области допустимых решений?
3. Может ли область допустимых решений иметь бесконечное множество оптимальных решений?
4. Может ли многогранник решений представлять из себя точку, отрезок?
5. Почему на переменные x накладывается условие неотрицательности?
6. Дайте определение симметричной форме записи задачи линейного программирования.
7. Когда можно применять графический метод решения задачи линейного программирования?
8. Как формулируется двойственная задача?
9. Что понимают под «теневой ценой»?
10. Если одна из взаимно двойственных задач имеет оптимальное решение, то имеет ли его другая?
11. Какие сообщения выдает Excel в случаях:

35

успешного решения задачи линейного программирования;

несовместимости системы ограничений задачи;

неограниченности целевой функции?
Практическая работа 2. ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО
ПРОГРАММИРОВАНИЯ
КРАТКАЯ СПРАВКА
Модели целочисленного (дискретного) программирования в области экономики и управления включают в себя задачи, в которых на искомые переменные накладываются условия целочисленности, а также область допустимых решений этих задач конечна. К их числу относятся, например, следующие задачи:

оптимизация раскроя;

оптимальное проектирование машин и оборудования;

оптимизация системы сервиса и технического обслуживания машинно- тракторного парка и т.п.
В том случае, когда ограничения и целевая функции задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного
программирования, если хотя бы одна зависимость нелинейна, - целочисленной
задачей нелинейного программирования.
Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами дискретного
(целочисленного) программирования:


 


.
n
p
,
p
,
i
,
целые
x
,
n
,
i
,
x
,
m
,
j
,
b
,
x
a
(max),
min
x
c
x
,
,
x
,
x
f
i
i
n
i
j
i
ij
n
i
i
i
n

















1 1
0 1
1 1
2 1

Если p = n, то задачу называют полностью целочисленной, если p < n, то
частично целочисленной.
Методы решения задач дискретного программирования:
1) метод отсекающих плоскостей (метод отсечения, метод Гомори);
2) комбинаторные методы (метод ветвей и границ);
3) метод случайного поиска и эвристические методы;
4) использование надстройки «Поиск решения» MS Office Excel.
Более эффективным считается метод ветвей и границ. Практически все коммерческие программы, предназначенные для решения задач целочисленного линейного программирования, используют это метод. Именно этот метод реализован в программе «Поиск решения» пакета MS Office Excel.

36
Метод отсекающих плоскостей более сложен и менее надежен, кроме того его реализация порождает серьезные проблемы, связанные с ошибками машинного округления.
2.1. Решение задачи целочисленного программирования с помощью
программы Microsoft Office Excel
Пример 2.1. Максимизировать z=5x
1
+4x
2
при ограничениях
.
целые
и
x
,
x
,
x
x
,
x
x
0 45 6
10 5
2 1
2 1
2 1





Решение
Дискретная оптимизация средствами MS Office Excel проводится аналогично решению соответствующих непрерывных задач линейного программирования. Основное отличие заключается во вводе при оформлении диалогового окна
Поиск
решения требования целочисленности соответствующих переменных (при этом в режиме
Параметры устанавливается тип задачи – линейная или нелинейная).
Исходя из требования целочисленности, в случае дискретной оптимизации возможен вызов только одного Отчета по результатам.
При попытке получить другие виды отчетов будет выдано сообщение, приведенное на рисунке 2.1.1.
Рис. 2.1.1. Полученное сообщение надстройки Поиск решения
Прежде чем использовать режим Поиск решения необходимо выполнить следующие действия:
1) создать форму для ввода условий задачи;
2) указать адреса ячеек, в которые будет помещен результат решения
(изменяемые ячейки);
3) ввести исходные данные;
4) ввести зависимость для целевой функции;
5) ввести зависимости для ограничений.
Экранные формы, задание переменных, целевой функции, ограничений приведены на рисунках 2.1.2, 2.1.3.

37
Рис. 2.1.2. Экранные формы
Рис. 2.1.3. Экранные формы в режиме просмотра формул
При решении задач целочисленного программирования в MS Office
Excel необходимо вводить условие целостности. Добавляя ограничения, следует выбрать опцию цел в раскрывшемся списке. В результате в поле
Ограничение: появится «целое» (рис. 2.1.4).
Рис. 2.1.4. Ввод ограничения целочисленности переменных
На рисунке 2.1.5 приведено заполненное диалоговое окно Поиск
решения.
Решение показано на рисунке 2.1.6.

38
Рис. 2.1.5. Заполненное диалоговое окно Поиск решения
Рис. 2.1.6. Решение найдено
Ответ. При целых значениях x
1
= 3, x
2
= 2 максимальное значение целевой функции будет равно 23.
2.2. Решение задачи целочисленного программирования с помощью
метода ветвей и границ
КРАТКАЯ СПРАВКА
Алгоритм метода ветвей и границ
Предположим, что рассматриваемая задача максимизации.
Зададим нижнюю границу оптимального значения целевой функции z задачи целочисленного линейного программирования равной

Положим i=0.
Шаг 1. (зондирование и определение границы). Выбираем i-ю подзадачу линейного программирования ЛПi для исследования. Решаем ЛПi и зондируем ее, при этом возможна одна из трех ситуаций:
1. Оптимальное значение целевой функции задачи ЛПi не может улучшить значение текущей нижней границы.
2. ЛПi приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница.
3. ЛПi не имеет допустимых решений.

39
Возможны два варианта:
1. Если задача ЛПi прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи целочисленного линейного программирования. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи целочисленного линейного программирования является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить i=i+1 и повторить шаг 1.
2. Если задача ЛПi не прозондирована, переходим к шагу 2 для выполнения ветвления.
Шаг 2. (Ветвление.) Выбираем одну из целочисленных переменных x
j
, оптимальное значение
*
j
x которой в оптимальном решении задачи ЛПi не является целым числом. Исключаем из пространства допустимых решений область
 
 
1



*
j
j
*
j
x
x
x
(где [u] – наибольшее целое, не превосходящее u) путем формирования двух подзадач линейного программирования, которые соответствуют ограничениям
 
*
j
j
x
x

и
 
1


*
j
j
x
x
Положим i=i+1 и переходим к шагу 1.
Описанный алгоритм применим для решения задач максимизации.
Для решения задач минимизации в алгоритме необходимо заменить нижнюю границу верхней (начальное значение которой равно +

).
Алгоритм метода ветвей и границ непосредственно распространяется на задачи частично-целочисленные линейного программирования.
Если некоторая переменная является непрерывной, то она никогда не выбирается в качестве переменной ветвления.
Допустимая подзадача определяет новую границу для значения целевой функции, если значения дискретных переменных являются целочисленными и значение целевой функции улучшено по сравнению с текущей границей.
Пример 2.2. Максимизировать z=5x
1
+4x
2
при ограничениях
.
целые
и
x
,
x
,
x
x
,
x
x
0 45 6
10 5
2 1
2 1
2 1





Решение
1. Отбросив условие целочисленности, находим оптимальное решение
(на рисунке 5.1.7 точка D):
z=23,75; x
1
=3,75; x
2
=1,25.
Т.к. оптимальное решение задачи не удовлетворяет условию целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что, в конечном счете, получается оптимальное решение задачи целочисленного линейного программирования.