Новый ДБР. - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Среди Всех Клеточек (І,j), Для Присоединяется К Совокупности Базисных ...
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим такую клеточку через (i0,j0).
Пусть клеточка (i0,j0), для которой
Находится цикл, что образуется этими клеточками. Цикл разбивается на положительный (C+) и отрицательный (C–) полуциклы, клеточки которых чергуються одна из одною, причем клеточка (i0,j0) относится к положительному полцикла. Вычисляются величины
q1 = min{xij} по C–,
q2= min{rij – xij} по C+
q = min{q1q2}.
Увеличивают на значение q перевозка xij в клеточках полцикла C+ и уменьшают их на то же значение в клеточках C–.
Для клеточки (i0,j0) такой, что отмена заключается в том, что она относится к отрицательному полцикла.
В результате выполнения указанных процедур клеточка (i0,j0) вводится к множеству базисных, а клеточка, связанная с q, становится небазисной. Если q достигается на клеточке (i0,j0), то множество базисных клеточек не изменяется после перераспределения перевозок вдоль цикла на постоянную q и новый ДБР будет иметь ту же самую систему потенциалов и те же самые оценки, что и предыдущий. Поэтому в этом случае после вычисления нового ДБР непосредственно переходят к проверке его на оптимум.
Все темы данного раздела:
Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п
Постановка задачи.
Решить систему линейных алгебраических уравнений
a11x1 + . . . + a1n xn = a10
. . . . . . . . . . . . . . . . . .
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД
Постановка задачи линейного программирования
в стандартной форме (СЗЛП).
Найти вектор x=
МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода.
Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра
ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода.
Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм
Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b
Основные определения.
Поскольку транспортная задача является случаем части задачи линейного программирования, для нее имеют силу все общие определения последней. В частности, замеченное относится также и к допустимому б
Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение.
2. Ранг матрицы А ограничений транспортной
Основные теоремы.
1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл).
2. ДБР
Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,
Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов.
2. В дальнейшем метод потенциалов с
Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО
СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными
пропускными способностями (ТЗО).
В пункте Pi (i=1
Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт
Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами
Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим
xi,n+1 = ai – (
Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij
Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые).
Те
Алгоритм метода потенциалов.
1. Строится выходной ДБР.
2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых:
i) Вычисляются потенциалы u
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети.
На сети, что задается графом (I,U), где И — множество вершин,
МЕТОД ФОРДА-ФАЛКЕРСОНА
Постановка задачи о максимальном потоке на сети.
На сети, что задается графом (I,U), где I — множество вершин,
Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию
L(x)= c1x1 + ... + cnxn (9.1)
Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем.
Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9
Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также
ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП).
Найти вектор x=(x1...,xn
МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП).
Найти вектор x=(x1...,xn), что
ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП).
Найти вектор x=(x1...,xn
МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП).
Найти вектор x=(x1...,xn), что
Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1
Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления
ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении.
Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию
ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
Алгоритм метода Мака.
МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН
Постановка матричной игры двух лиц с нулевой суммой.
Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданн
Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето
Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.
Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B].
Алгоритм метода реа
КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования.
Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию
Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу
x[s+1]=
Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу
F(x[s]–r
Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979.
2. Ю.Д.Попов. Линейное и нел
Новости и инфо для студентов