|
|
|
|
|
|
|
|
|
|
|
страницы:
1
2
3
4
5
6
7
Текущая страница: 1
|
|
Содержание.
Введение..............................................................................................
1.Транспортная задача линейного программирования
1.1 Постановка задачи и ее математическая модель...................
1.2 Открытая модель транспортной задачи....................................
1.3 Построение первоначального опорного плана........................
2. Дельта-метод решения транспортной задачи
2.1 Алгоритм решения транспортной задачи дельта-методом...
3. Проверка оптимальности методом потенциалов
3.1 Метод потенциалов..................................................................
3.2 Построение системы потенциалов.........................................
3.3 Проверка выполнения условия оптимальности для
незанятых клеток......................................................................
4. Пример построения первоначального опорного плана
дельта-методом
4.1 Построение математической модели
транспортной задачи..............................................................
4.2 Построение первоначального опорного плана
дельта-методом .....................................................................
5. Описание программы......................................................................
Список использованной литературы .............................................
Приложение.....................................................................................
Введение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта
Цель заданной работы - освоить алгоритм построения первого опорного плана закрытой транспортной задачи
дельта-методом и написать его программную реализацию.
1.Транспортная задача линейного программирования.
1.1 Постановка задачи и ее математическая модель.
Некоторый однородный продукт, сосредоточенный у m поставщиков Ai в количестве ai (i=1,2,3,...,m) единиц соответственно, необходимо доставить n потребителям Bj в количестве bj (j=1,2,3,...,n) единиц. Известна стоимость Cij перевозки единицы груза от i-го поставщика к j-му потребителю.
Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить Cij xij потребности и имеющий минимальную стоимость.
Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю; тогда условия задачи можно записать в виде таблицы, которую в дальнейшем будем называть матрицей планирования.
Таблица 1
Поставщики
Потребители
Запасы
B1
B2
...
Bn
A1
C11
x11
C12
x12
...
C1n
x1n
a1
A2
C21
x21
C22
x22
...
C2n
x2n
a2
...
...
...
...
...
...
Am
Cm1
xm1
Cm2
xm2
...
Cmn
xmn
am
Потребности
b1
b2
...
bn
Составим математическую модель задачи. Так как от i-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит Cijxij.
Стоимость всего плана выразится двойной суммой:
Z = .
Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть вывезены, т.е.
(i = 1,2,3,..., m) (эти уравнения получаются из строк таблицы 1);
б) все потребности должны быть удовлетворены, т.е.
(j = 1,2,3,...,n) (уравнения получаются из столбцов таблицы 1).
Таким образом, математическая модель транспортной задачи имеет следующий вид.
Найти наименьшее значение линейной функции:
Z = ( 1)
при ограничениях
, i = 1, 2, ..., m, ( 2 )
, j = 1,2,3,...,n , ( 3 )
xij ( 0 ( j = 1,2,3, ..., m; i = 1,2,3, ..., n).
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
( 4 )
Такая модель называется закрытой.
Теорема 1. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.
Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть = M > 0.
Тогда величины xij = aibj /M (i = 1,2,3, ... m ; j = 1,2,3, ..., n) являются планом, так как они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в ( 2 ) и ( 3 ) , находим
= ai ,
= bj .
Выберем из значений Cij наибольшее C( = max Cij и заменим в линейной функции ( 1 ) все коэффициенты на C( тогда, учитывая ( 2 ) , получим
Текущая страница: 1
|
|
|
|
|
 |
Предмет: Экономика
Математика
|
 |
Тема: Дельта-метод решения транспортной задачи |
 |
Ключевые слова: программа, Ещ¦, Дельта-метод решения транспортной задачи, моделирование, есть, Экономико-математическое моделирование, Экономико-математическое, задачи, karimov_aidar@chat.ru, решения, Ещ¦ есть программа пишите karimov_aidar@chat.ru , Дельта-метод, пишите, транспортной |
|
|
|
|
|
|
|
|
|
|
