Программное обеспечение. - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Обучающий Модуль, С Помощью Которого Транспортная Задача Решается В Диалоге С...
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО.
Задание.
Решить методом потенциалов транспортные задачи, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи:
1)
| a
| 25
| 40
| 50
| 35
| 45
| 2)
| a
| 35
| 30
| 50
| 25
| 65
|
| 20
| 7
| 3
| 4
| 8
| 6
|
| 50
| 8
| 6
| 7
| 3
| 4
|
| 60
| 5
| 7
| 2
| 3
| 5
|
| 50
| 7
| 4
| 9
| 3
| 4
|
| 45
| 1
| 4
| 5
| 2
| 6
|
| 55
| 6
| 1
| 4
| 5
| 2
|
| 70
| 3
| 4
| 2
| 7
| 8
|
| 50
| 7
| 8
| 3
| 4
| 2
|
3)
| a
| 10
| 40
| 20
| 60
| 20
| 4)
| a
| 70
| 40
| 30
| 60
| 50
|
| 30
| 5
| 1
| 5
| 2
| 4
|
| 20
| 6
| 1
| 7
| 3
| 3
|
| 70
| 5
| 7
| 6
| 3
| 2
|
| 90
| 7
| 4
| 4
| 8
| 4
|
| 25
| 1
| 5
| 4
| 2
| 6
|
| 80
| 8
| 2
| 3
| 5
| 7
|
| 25
| 1
| 6
| 3
| 3
| 5
|
| 60
| 3
| 4
| 2
| 8
| 5
|
5)
| a
| 30
| 90
| 80
| 20
| 30
| 6)
| a
| 10
| 30
| 25
| 15
| 20
|
| 95
| 2
| 8
| 4
| 6
| 3
|
| 20
| 9
| 1
| 5
| 7
| 1
|
| 55
| 3
| 2
| 5
| 2
| 6
|
| 15
| 2
| 8
| 4
| 8
| 1
|
| 40
| 6
| 5
| 8
| 7
| 4
|
| 45
| 2
| 3
| 2
| 8
| 5
|
| 60
| 3
| 4
| 4
| 2
| 1
|
| 20
| 6
| 1
| 3
| 4
| 7
|
7)
| a
| 13
| 13
| 13
| 13
| 28
| 8)
| a
| 11
| 13
| 26
| 10
| 10
|
| 28
| 8
| 4
| 6
| 3
| 1
|
| 24
| 9
| 1
| 3
| 2
| 7
|
| 13
| 9
| 3
| 8
| 5
| 7
|
| 12
| 6
| 9
| 4
| 1
| 5
|
| 19
| 7
| 3
| 5
| 9
| 8
|
| 18
| 9
| 1
| 2
| 8
| 5
|
| 20
| 2
| 1
| 4
| 5
| 7
|
| 16
| 3
| 3
| 9
| 6
| 8
|
9)
| a
| 10
| 35
| 15
| 25
| 35
| 10)
| a
| 30
| 80
| 65
| 35
| 40
|
| 30
| 7
| 3
| 1
| 5
| 4
|
| 60
| 8
| 2
| 4
| 9
| 1
|
| 25
| 7
| 5
| 8
| 3
| 2
|
| 55
| 7
| 5
| 5
| 3
| 6
|
| 45
| 6
| 4
| 8
| 3
| 2
|
| 85
| 9
| 4
| 6
| 2
| 7
|
| 20
| 3
| 1
| 7
| 6
| 2
|
| 50
| 5
| 3
| 2
| 6
| 4
|
Ответы:
1) L(x*)= 575. 2) L(x*)= 710. 3) L(x*)= 360. 4) L(x*)= 910. 5) L(x*)= 750.
6) L(x*)= 200. 7) L(x*)= 209. 8) L(x*)= 184. 9) L(x*)= 285. 10) L(x*)= 785.
Лабораторная работа 6.
Все темы данного раздела:
Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п
Постановка задачи.
Решить систему линейных алгебраических уравнений
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 (оценки базисных переменных — нулевые).
Те
Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та
Алгоритм метода потенциалов.
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. Ю.Д.Попов. Линейное и нел
Новости и инфо для студентов