Динамическое и линейное программирование
Категория реферата: Рефераты по математике
Теги реферата: оформление титульный реферата, шпаргалки по гражданскому праву
Добавил(а) на сайт: Пыстогов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Таким образом, получена задача линейного программирования:
максимизировать функцию (3.1) при условиях (3.4) и (3.5).
Эту задачу с двумя переменными можно решить графически:
График 1.
На графике видно, что система линейных неравенств (3.4), (3.5), образует
область допустимых решений, ограниченную прямыми:
[pic], [pic], [pic], [pic]
при этом линии уровня функции (3.1) перпендикулярны вектору-градиенту [pic]
и образуют семейство параллельных прямых (градиент указывает направление
возрастания функции). Наибольшего значения функция (3.1) достигает в точке
[pic]пересечения прямых:
[pic] и [pic]
Координаты этой точки и определяют искомые объемы дополнительных
ресурсов. Следовательно, программа «расшивки узких мест производства имеет
вид:
[pic], [pic], [pic] и прирост прибыли составит:
[pic]
Сводка результатов по пунктам 1-3 приведена в таблице 2.
|Таблица 2. |
|[pic|30 |11 |45 |6 |B |[pic|[pic|[pic]|
|] | | | | | |] |] | |
|[pic|3 |2 |6 |0 |150 |0 |6 |50 |
|] | | | | | | | | |
| |4 |2 |3 |5 |130 |0 |3 |[pic]|
| |4 |3 |2 |4 |124 |8 |0 |0 |
|[pic|22 |0 |14 |0 |1290 | | |[pic]|
|] | | | | | | | | |
|[pic|0 |7 |0 |9 | | | | |
|] | | | | | | | | |
4. Транспортная задача
Транспортная задача – это задача о минимизации транспортных расходов, связанных с обеспечением пунктов потребления определенным количеством
однородной продукции, производимой (хранимой) в нескольких пунктах
производства (хранения). В общем виде задача может быть сформулирована
следующим образом:
Однородный продукт, сосредоточенный в [pic] пунктах производства
(хранения), необходимо распределить между [pic] пунктами потребления.
Стоимость перевозки единицы продукции известна для всех маршрутов.
Необходимо составить такой план перевозок, при котором запросы всех пунктов
потребления были бы удовлетворены за счет имеющихся продуктов в пунктах
производства и общие транспортные расходы по доставке продуктов были бы
минимальными.
Примем следующие обозначения:
|[pic]|Номер пункта производства (хранения) (i=1,2,…,m) |
|[pic]|Номер пункта потребления (j=1,2,…,n) |
|[pic]|Количество продукта, имеющиеся в i-ом пункте |
| |производства |
|[pic]|Количество продукта, необходимое для j-го пункта |
| |потребления |
|[pic]|Стоимость перевозки единицы продукта из i-го пункта |
| |отправления в j-ый пункт назначения |
|[pic]|Количество груза, планируемого к перевозке от i-го |
| |пункта отправления в j-ый пункт назначения |
Тогда, при наличии баланса производства и потребления:
[pic] математическая модель транспортной задачи будет выглядеть следующим образом: найти план перевозок
[pic], где [pic]; [pic] минимизирующий общую стоимость всех перевозок
[pic]
при условии, что из любого пункта производства вывозиться весь продукт
|[pic], где [pic] |(4.1) |
и любому потребителю доставляется необходимое количества груза
|[pic], где [pic] |(4.2) |
причем, по смыслу задачи
[pic], …, [pic]
Для решения транспортной задачи чаще всего применяется метод потенциалов, при котором вводят обозначение вектора симплексных множителей или
потенциалов:
[pic]
Тогда:
[pic], где [pic]; [pic]
Откуда следует:
[pic], где [pic]; [pic]
При этом один из потенциалов можно выбирать произвольно, т.к. в системе
(4.1) и (4.2) одно уравнение линейно зависит от остальных, а остальные
потенциалы находятся, что для базисных значений [pic].
Предположим, что однородный продукт, находящийся в трех пунктах
производства (m=3), необходимо доставить в четыре пункта потребления
(n=4). При этом матрица [pic] транспортных затрат на перевозку единицы
продукта из любого пункта отправления в любой пункт назначения, вектор
[pic] объемов запасов продукта в пунктах производства и вектор [pic]
объемов продукта, необходимых пунктам потребления, имеют вид:
|[pic] |[pic] |
|[pic] | |
Тогда получается, что общий объем продукта в пунктах производства
[pic] больше, чем требуется всем потребителям [pic], т.е. имеем открытую
модель транспортной задачи.
Для того чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления
Рекомендуем скачать другие рефераты по теме: конспекты 9 класс, реферат великая.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата