Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

В качестве дополнительного ограничения вводим такое

,

где Si – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения. Такое ограничение равенство определяет отсечение Гомори для полностью целочисленной задачи. Добавив построенное ограничение в симплекс-таблицу, получим недопустимое, но оптимальное решение. В такой ситуации следует использовать двойственный симплекс-метод для получения допустимого и оптимального решения.

Метод ветвей и границ.

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

[xr]< xr<[xr]+1

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

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

Задача линейного программирования транспортного типа.

Постановка задачи. Пусть в m пунктах производят некоторый однородный продукт, причем объем производства в пункте i составляет Ai единиц. Допустим, что данный продукт потребляется в n пунктах потребления, а объем потребления в пункте j составляет единиц Bj. Предположим, что из каждого пункта производства i возможна транспортировка продукта в любой пункт потребления j с затратами cij. Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт вывезен из пунктов производства и суммарные транспортные издержки минимальны.

Математическая модель. Пусть xij – количество продукта, перевозимого из пункта i в пункт j. Найти множество переменных удовлетворяющих условиям

,

.

и таких, что целевая функция

достигает минимума.

Метод решения транспортной задачи [6, 7, 10].

Сети

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

Задача минимизации сети.

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

Задача о кратчайшем пути

Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые имеют минимальную длину от исходного пункта до пункта назначения. Для решения этой задачи можно применить следующий алгоритм. Каждому узлу сети будем приписывать временные пометки равные расстоянию от начального узла до данного узла. Если оказывается, что узел принадлежит кратчайшему маршруту, то временную пометку объявляем постоянной. На первой итерации начальному узлу приписывается постоянная пометка равная нулю, а остальным узлам – временные пометки, равные длине дуги из начального узла в рассматриваемый узел, если такая дуга существует и «», если нет такой дуги. Затем, до тех пор пока конечный узел не получит постоянную пометку выполняются следующие две процедуры: 1) среди временных пометок выбирается минимальная и объявляется постоянной; 2) для всех временно помеченных узлов вычисляются новые временные пометки, меньшей из двух величин – старой временной пометки рассматриваемого узла и суммы постоянной пометки последнего постоянно помеченного узла и длины дуги, соединяющей последний постоянно помеченный узел с рассматриваемым узлом. Если при этом постоянную пометку получает конечный узел, то кратчайший маршрут найден. Дуги входящие в этот маршрут определяются следующим образом: если разность между постоянными пометками начального и конечного узлов данной дуги равна длине дуги, то эта дуга принадлежит кратчайшему маршрут.

Задача о максимальном потоке

Рассмотрим задачу о максимальном потоке между двумя выделенными узлами связной сети. Каждая дуга сети обладает пропускными способностями в обоих направлениях, которые определяют максимальное количество потока, проходящего поданной дуге. Ориентированная (односторонняя) дуга соответствует нулевой пропускной способности в запрещенном направлении.

Пропускные способности cij сети можно представить в матричной форме. Для определения максимального потока из источника s в сток t используется следующий алгоритм.

Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении st. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.

Шаг 2. Пусть cij- (cij+) – пропускные способности дуг цепи (s, t) в направлении st (ts) и = min{cij-}>0. Матрицу пропускных способностей (cij) изменить следующим образом:

(а) вычесть из всех cij- ;

(б) прибавить ко всем cij+ .

Заменить текущую cij-матрицу на вновь полученную и перейти к шагу 1.

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

Шаг 3. Найти максимальный поток в сети. Пусть C = cij - исходная матрица пропускных способностей, и пусть C* = cij - последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток X = xij в дугах задается как

Максимальный поток из s в t равен

При этом z есть сумма всех положительных , определенных на шаге 2. Таким образом, можно объяснить, почему используются положительные элементы матрицы C – C* для определения результирующего потока в направлении s t.

Литература

1. Протосеня А.Г., Кулиш С.А., Азбель Е.И. и др. Математические методы планировании и управлении горным производством. Учебное пособие для вузов. - М.: Наука, 1985.

2. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир,1984.

3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.

4. Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.

5. Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.

6. Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979

7. Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.

8. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.

9. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

10. Данко. Высшая математика в примерах и задачах.

Контрольная работа.

Контрольная работа выполняется в отдельной тетради или на листах. Контрольная работа состоит из 7 заданий, представленных в общем виде. Числовые данные к каждой задаче выдаются преподавателем и должны следовать в выполненной контрольной работе после титульного листа. Решения задач должны сопровождаться достаточными пояснениями. При решении допускается использование ПЭВМ. Контрольная работа считается выполненной, если решены все задания. Контрольная работа защищается на консультации либо в течение семестра, либо перед зачетом. К зачету допускаются только студенты, защитившие свою работу.

Задание 1

Для изготовления трех видов продукции Р1, Р2 и Р3 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, количество каждого ресурса, затрачиваемое на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице.

Вид ресурса	Запас ресурса	Число единиц ресурса, затрачиваемых на изготовление единицы продукции
		Р1	Р2	Р3
S1	B1	A11	A12	A13
S2	B2	A21	A22	A23
S3	B3	A31	A32	A33
S4	B4	A41	A42	A43
Прибыль, получаемая от единицы продукции		C1	C2	C3

Требуется:

1. составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной;

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

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

2. Привести задачу к стандартному виду.

3. Определить начальный допустимый план.

4. Заполнить начальную симплекс-таблицу.

5. Найти оптимальный план производства симплекс-методом. (Допускается использование ПЭВМ). Решение оформить в виде симплекс-таблиц.

6. По оптимальной симплекс-таблице определить: ограничено ли пространство допустимых решений; единственно ли оптимальное решение задачи; есть ли у задачи вырожденные решения. Все ответы объяснить и обосновать.

7. Определить, какие из ресурсов являются дефицитными. Почему?

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

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

10. Определить увеличение запаса какого из ресурсов наиболее выгодно.

11. Определить, в каких пределах допустимо изменение коэффициентов целевой функции.

Задание 2.

Для задачи, полученной в первом задании построить двойственную. Дать экономическую интерпретацию двойственной задачи. Решить двойственную задачу. Используя соотношения двойственности, получить оптимальное решение прямой задачи.

Задание 3.

К математической модели, полученной в задании 1 добавить условие целочисленности для всех переменных. Решить новую задачу методом отсечений.

Задание 4.

Решить транспортную задачу.

Задание 5.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Построить минимальное дерево-остов.

Задание 6.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Найти кратчайший маршрут из узла 1 в узел 13.

Задание 7.

Для каждой дуги (i, j) сети указана ее пропускная способность. Найти максимальный поток из источника s в сток t.

Характеристики

Список файлов книги