РУБРИКИ

Курсовая: Динамическое и линейное программирование

 РЕКОМЕНДУЕМ

Главная

Правоохранительные органы

Предпринимательство

Психология

Радиоэлектроника

Режущий инструмент

Коммуникации и связь

Косметология

Криминалистика

Криминология

Криптология

Информатика

Искусство и культура

Масс-медиа и реклама

Математика

Медицина

Религия и мифология

ПОДПИСКА НА ОБНОВЛЕНИЕ

Рассылка рефератов

ПОИСК

Курсовая: Динамическое и линейное программирование

при условии сохранения структуры производственной программы:

Курсовая: Динамическое и линейное программирование

(3.2)

предполагая, что можно надеяться получить дополнительно не более одной трети первоначального объема ресурса каждого вида, т.е.:

Курсовая: Динамическое и линейное программирование

(3.3)

причем дополнительные объемы ресурсов, по смыслу задачи, не могут быть отрицательными, т.е.:

Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование

(3.4)

Т.к. неравенства (3.2) и (3.3) должны выполняться одновременно, то их можно переписать в виде одной системы неравенств:



ƒ

Курсовая: Динамическое и линейное программирование

(3.5)

Таким образом, получена задача линейного программирования: максимизировать функцию (3.1) при условиях (3.4) и (3.5). Эту задачу с двумя переменными можно решить графически:

Курсовая: Динамическое и линейное программирование

График 1. На графике видно, что система линейных неравенств (3.4), (3.5), образует область допустимых решений, ограниченную прямыми: Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование при этом линии уровня функции (3.1) перпендикулярны вектору-градиенту Курсовая: Динамическое и линейное программирование и образуют семейство параллельных прямых (градиент указывает направление возрастания функции). Наибольшего значения функция (3.1) достигает в точке Курсовая: Динамическое и линейное программирование пересечения прямых: Курсовая: Динамическое и линейное программирование и Курсовая: Динамическое и линейное программирование Координаты этой точки и определяют искомые объемы дополнительных ресурсов. Следовательно, программа «расшивки узких мест производства имеет вид: Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование , Курсовая: Динамическое и линейное программирование и прирост прибыли составит: Курсовая: Динамическое и линейное программирование Сводка результатов по пунктам 1-3 приведена в таблице 2.

Таблица 2.

Курсовая: Динамическое и линейное программирование

3011456B

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

32601500650
423513003

Курсовая: Динамическое и линейное программирование

4324124800

Курсовая: Динамическое и линейное программирование

2201401290

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

0709

4. Транспортная задача

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

Курсовая: Динамическое и линейное программирование

Номер пункта производства (хранения) (i=1,2,.,m)

Курсовая: Динамическое и линейное программирование

Номер пункта потребления (j=1,2,.,n)

Курсовая: Динамическое и линейное программирование

Количество продукта, имеющиеся в i-ом пункте производства

Курсовая: Динамическое и линейное программирование

Количество продукта, необходимое для j-го пункта потребления

Курсовая: Динамическое и линейное программирование

Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения

Курсовая: Динамическое и линейное программирование

Количество груза, планируемого к перевозке от i-го пункта отправления в j-ый пункт назначения
Тогда, при наличии баланса производства и потребления: Курсовая: Динамическое и линейное программирование математическая модель транспортной задачи будет выглядеть следующим образом: найти план перевозок Курсовая: Динамическое и линейное программирование , где Курсовая: Динамическое и линейное программирование ; Курсовая: Динамическое и линейное программирование минимизирующий общую стоимость всех перевозок Курсовая: Динамическое и линейное программирование при условии, что из любого пункта производства вывозиться весь продукт

Курсовая: Динамическое и линейное программирование , где Курсовая: Динамическое и линейное программирование

(4.1)

и любому потребителю доставляется необходимое количества груза

Курсовая: Динамическое и линейное программирование , где Курсовая: Динамическое и линейное программирование

(4.2)

причем, по смыслу задачи Курсовая: Динамическое и линейное программирование , ., Курсовая: Динамическое и линейное программирование Для решения транспортной задачи чаще всего применяется метод потенциалов, при котором вводят обозначение вектора симплексных множителей или потенциалов: Курсовая: Динамическое и линейное программирование Тогда: Курсовая: Динамическое и линейное программирование , где Курсовая: Динамическое и линейное программирование ; Курсовая: Динамическое и линейное программирование Откуда следует: Курсовая: Динамическое и линейное программирование , где Курсовая: Динамическое и линейное программирование ; Курсовая: Динамическое и линейное программирование При этом один из потенциалов можно выбирать произвольно, т.к. в системе (4.1) и (4.2) одно уравнение линейно зависит от остальных, а остальные потенциалы находятся, что для базисных значений Курсовая: Динамическое и линейное программирование . Предположим, что однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица Курсовая: Динамическое и линейное программирование транспортных затрат на перевозку единицы продукта из любого пункта отправления в любой пункт назначения, вектор Курсовая: Динамическое и линейное программирование объемов запасов продукта в пунктах производства и вектор Курсовая: Динамическое и линейное программирование объемов продукта, необходимых пунктам потребления, имеют вид:

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Тогда получается, что общий объем продукта в пунктах производства Курсовая: Динамическое и линейное программирование больше, чем требуется всем потребителям Курсовая: Динамическое и линейное программирование , т.е. имеем открытую модель транспортной задачи. Для того чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления Курсовая: Динамическое и линейное программирование единиц, при этом тарифы на перевозку продукта в этот пункт потребления будут равны нулю, т.к. фактического перемещения продукта не происходит. Тогда, первое базисное допустимое решение легко построить по правилу «северо-западного угла». А т.к. оценки базисных клеток транспортной таблицы равны нулю, то, приняв, что Курсовая: Динамическое и линейное программирование , первая транспортная таблица и потенциалы имеют вид:

Курсовая: Динамическое и линейное программирование Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

3011453628

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование 50

30119*

Курсовая: Динамическое и линейное программирование

703634

Курсовая: Динамическое и линейное программирование

30228

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24 и производим перераспределение поставок вдоль цикла пресчета:

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

9*®

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

®09
3634

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

4525

Курсовая: Динамическое и линейное программирование

То получаем второе базисное допустимое решение и находим новые потенциалы, полагая Курсовая: Динамическое и линейное программирование :

Курсовая: Динамическое и линейное программирование Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

3011453628

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование 50

30119

Курсовая: Динамическое и линейное программирование

70*4525

Курсовая: Динамическое и линейное программирование

30228

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Т.к. теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 22, то строим цикл пересчета: 22‑12‑14‑24 и производим перераспределение поставок вдоль цикла пресчета:

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

119®

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

®020
*25

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

1114

Курсовая: Динамическое и линейное программирование

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

Курсовая: Динамическое и линейное программирование Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

3011453628

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование 50

3020

Курсовая: Динамическое и линейное программирование

70*114514

Курсовая: Динамическое и линейное программирование

30228

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, теперь соответствует клетке 21, то строим цикл пересчета: 21-11-14- 24 и производим перераспределение поставок вдоль цикла пресчета:

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

3020®

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

®1634
*14

Курсовая: Динамическое и линейное программирование

Курсовая: Динамическое и линейное программирование

140

Курсовая: Динамическое и линейное программирование

Страницы: 1, 2, 3, 4


© 2010
Частичное или полное использование материалов
запрещено.