Предыдущая страница реферата | 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 | Следующая страница реферата