Если же у одной из этих задач линейная форма не ограничена, то двойственная к ней задача противоречива.

Принцип построения

Переменные и ограничения двойственной задачи формируются путем симметричных структурных преобразований прямой задачи по следующим правилам.

1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.

2. Каждой из n переменных прямой задачи соответствует ограничение двойственной задачи.

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

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

Соотношения двойственности
Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их целевых функций, но и в том, что опти­мальное решение одной из этих задач непосредственно можно получить из данных симплексной таблицы, содержащей оптимальное решение другой задачи.

Чтобы найти оптимальное решение ОЗ по известному оптимальному решению ПЗ, нужно воспользоваться следующим правилом: значение переменной ОЗ равно коэффициенту в целевой функции при соответствующей переменной ПЗ, взя­тому с противоположным знаком из последней симплексной таблицы.

Алгоритм составления
1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум — к виду «≥».

2. Составить расширенную матрицу системы А1, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

З. Найти матрицу А1′, транспонированную к матрице А1.

4. Сформулировать двойственную задачу на основании полученной матрицы А1′ и условия неотрицательности переменных.

18. Задачи целочисленного программирования и методы их решения. Метод ветвей и границ.
Целочисленное программирование – разновидность математического программирования, подразумевающая, что искомые значения должны быть целыми числами.

Целочисленные задачи математического программирования могут возникать различными путями.

Задачи линейного программирования (ЛП), если смотреть их значение, например, задача о производстве столов, шкафов и кроватей с максимальным доходом при ограниченных ресурсах, являются на самом деле целочисленными задачами линейного программирования (трудно ведь представить, что компания может произвести и продать 1/3 стола или 11/4 шкафа?).

Если речь идет о задаче с 2 переменными, проще всего применить графический метод, если же переменных >2, приходится использовать специальные методы для этого класса задач: метод Гомори или метод ветвей и границ.

Методы решения задач целочисленного программирования основаны на использовании вычислительных возможностей методов ЛП. Обычно алгоритмы включают 3 шага.

Шаг 1. "Ослабление" пространства допустимых решений задачи целочисленного ЛП путем замены любой двоичной переменной y непрерывным ограничением 0 £ у £ 1 и отбрасывания требования целочисленности для всех остальных переменных. И получается обычная задача ЛП.

Шаг 2. Решение задачи ЛП и определение ее оптимального решения.

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

Метод ветвей и границ
По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений для решения задач целочисленного программирования.

Удобно представить последовательность задач ЛП, возникающих при использовании процедуры метода ветвей и границ, в виде сети или дерева. Они состоят из множества вершин и соединяющих их дуг или ветвей. Каждая вершина представляет собой либо начальную, либо конечную точку некоторой ветви. В том случае, если в некоторой вершине возникает ситуация, когда исследуемое решение является оптимальным и целочисленным или, наоборот, решение отсутствует, то нет необходимости производить дальнейшее ветвление, поэтому рассматриваемая вершина является прозондированной.

Алгоритм:

1. Находится оптимальный план без учета целочисленности

2. Выбирается любая дробная переменная xi – переменная ветвления

3. Производится дихотомизация – пусть xi=2 1/3, тогда рассматриваются две задачи с доп условиями соответственно xi<=2 и xi>=3

4. Возможны 4 случая:

a. одна из задач неразрешима, другая имеет целочисленный оптимальный план – план другой принимается за оптимальный, конец

b. одна неразрешима, другая – нецелочисленный оптимальный план – рассматриваем вторую, к шагу 2

c. обе разрешимы: оптимальная целочисленная, оптимальная нецелочисленная – сравниваем F. Если Fцел > Fнецел, то конец, иначе анализируем нецелочисленную дальше. Если далее не найдется решения оптимальнее, чем Fцел, то берем его как оптимальный.

d. Обе разрешимы и обе оптимальные нецелочисленные – смотрим далее ту, где F лучше.

 

19. Задачи целочисленного программирования и методы их решения. Метод отсекающих плоскостей.
Описание ЦЛП – см. №18

Метод отсекающих плоскостей (метод отсечения Гомори)
В задачах с большим количеством переменных более эффективным является метод отсечения Гомори, который основан на введении дополнительных условий и анализе значений базисных и небазисных переменных, т. е. Выполняется модифицированный симплекс-метод. Кроме того, данный метод может применяться в параметрическом программировании, когда исходные данные (коэффициенты) в ЦФ и ограничениях являются не постоянными величинами, а функциями, зависящими определенным образом от некоторых параметров.

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

Методы отсечения для задачи ЦЛП делятся на:
- прямые (использующие прямой симплекс-метод) и двойственные (использующие двойственный симплекс-метод),
- целочисленные (использующие полностью целочисленные симплекс-таблицы) и нецелочисленные.

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

Алгоритм:

1. Находится оптимальный план без учета целочисленности симплекс-методом.

2. В оптимальном плане выбирается строка с наибольшей дробной частью свободного члена

3. Для базисной переменной в этой строке строится условие отсечения

где q – дробная часть элемента. Дробная часть – разность между числом и его целой частью, где целая часть – наибольшее целое, меньшее данного числа (применимо и для отрицательных чисел: целая часть -1/3 = 2/3)

4. В таблицу добавляется новый базисный вектор по переменной . Образуется недопустимое решение из-за отрицательного свободного члена.

5. Ищется новое решение симплекс-методом.

6. Продолжать, пока есть дробные части в свободных членах.

20. Оптимизация на графах и сетях. Классические задачи оптимизации на графах. Алгоритм построения сетевого графика. Задача о максимальном потоке в сети.

Классические задачи оптимизации на графах:
 задача нахождения оптимальных покрывающих деревьев;
 задача нахождения кратчайшего пути в графе;
 задача нахождения критического пути в сетевом графе;
 задача нахождения максимального потока в графе.

Оптимизация сетевого графика – процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения.

Частная оптимизация – минимизация времени выполнения комплекса работ при заданной стоимости, минимизация стоимости комплекса работ при заданном времени выполнения проекта.

Комплексная оптимизация – нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.

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

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

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

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

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

Сетевая модель – план выполнения некоторого комплекса взаимосвязанных работ, заданного в специфической форме сети, графическое изображение которого называется сетевым графиком. Событие – момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта. Порядок построения сетевого графика.

1. В сетевой модели не должно быть “тупиковых” событий, т.е. событий, из которых не выходит ни одна работа, за исключением завершающего события.

2. В сетевом графике не должно быть событий (кроме исходного), которым не предшествует хотя бы одна работа.

3. В сети не должно быть замкнутых контуров и петель, т. е путей, соединяющих некоторые события с ними же самими.

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

5. В сети рекомендуется иметь одно исходное и одно завершающее событие. Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы. Критический путь – наиболее продолжительный полный путь в сетевом графике.

Рассмотрим более подробно содержательную постановку задачи о максимальном потоке в сети.
Данная задача имеет множество возможных вариантов постановки, один из которых может быть сформулирован следующим образом.
1. Имеется система магистральных трубопроводов, связывающих источник добычи нефти или газа с предприятием по его промышленной переработке.
2. Отдельные участки трубопроводов оснащены компрессорными установками для поддержания требуемого давления, необходимого для транспортировки продукта.
3. Известны предельные значения пропускной способности каждого участка рассматриваемой системы.
4. В предположении, что источник обладает достаточным запасами продукта, требуется определить количество транспортируемого продукта по каждому из участков трубопроводной системы так, чтобы количество доставленного на предприятие переработки продукта было максимальным.

 

21. Транспортные модели. Решение транспортной модели методом потенциалов.

В общем виде транспортную задачу (ТЗ) можно представить так:
требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей.
В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.