Разработка управленческих решений. 16

ВВЕДЕНИЕ

При рыночной системе хозяйствования коммерческая организация в сфере оптово-розничной  торговли является самоорганизующейся социально ориентированной системой, функционирующей в жестких условиях конкурентной среды, и имеет полную хозяйственную самостоятельность. В таком положении ее деятельность, в широком смысле, направлена , как на завоевание и удержание предпочтительной доли рынка, так и достижение превосходства над конкурентами. В соответствии  с таким положение, управленческие решения, их анализ и аудит, система учета и контроля ориентированы главным образом на обеспечение основных показателей эффективности работы в современных условиях, а именно:

-    устойчивое положение организации  на рынке (среди конкурентов);

- своевременную  адаптацию систем производства  и управления организацией и перманентно меняющейся внешней среде (конъюнктуре) и др.

В рыночных условиях, характеризующихся высокой  неопределенностью и нестабильностью  внешней среды, эффективное управление организацией в сфере оптово-розничной  торговли предполагает гораздо больший  объем плановой, а соответственно контрольной работы, чем при централизованной экономике. Более того, в настоящее время, в силу усиления конкурентных отношений на мировых и отечественных рынках, стремительного развития и смены технологий, растущей диверсификации бизнеса и усложнения бизнес - проектов управление коммерческой организацией работающей на рынке оптово-розничной торговли существенно усложняется, что обуславливает усложнение ее контрольных систем. Поэтому, в современных условиях внутренний анализ, контроль управленческих решений приобретает характер основы, присутствующей на всех уровнях управления, т.е. в более широком смысле в конкурентной среде рыночных отношений эффективный управленческий учет, контроль, анализ и аудит при прочих равных условиях являются гарантией успешной деятельности организации.

1. ТРАНСПОРТНАЯ ЗАДАЧА

Транспортная  задача (задача Монжа — Канторовича) — математическая задача линейного программированияспециального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.^[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из   в   груза  , а в маленькие клетки — соответствующие тарифы  .

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

Метод наименьшего  элемента

Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.

Алгоритм:

1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Данный  метод мы и используем при решении  нашей задачи.

Задача.

  Фирма имеет три магазина розничной  торговли, расположенные в разных  районах города (А, В, С). Поставки  продукции в эти магазины осуществляются  с четырех складов (1, 2, 3,4).

Найти оптимальное распределение поставок, при котором суммарные затраты  на перевозку были бы минимальны.

Решение.

Математическая  модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие  пункты назначения задана матрицей тарифов

Проверим  необходимое и достаточное условие  разрешимости задачи.

∑a = 30 + 25 + 15 + 30 = 100

∑b = 40 + 20 + 40 = 100

Занесем исходные данные в распределительную таблицу.

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

2. Подсчитаем  число занятых клеток таблицы,  их 5, а должно быть m + n - 1 = 6. Следовательно,  опорный план является вырожденным. 

Строим новый  план.

Значение  целевой функции для этого  опорного плана равно:

2. Подсчитаем  число занятых клеток таблицы,  их 5, а должно быть m + n - 1 = 6. Следовательно,  опорный план является вырожденным. 

Строим новый  план.

Значение  целевой функции для этого  опорного плана равно:

2. Подсчитаем  число занятых клеток таблицы,  их 5, а должно быть m + n - 1 = 6. Следовательно,  опорный план является вырожденным. 

Строим новый  план.

Значение  целевой функции для этого  опорного плана равно:

В результате получен первый опорный план, который  является допустимым, так как все  грузы из баз вывезены, потребность  магазинов удовлетворена, а план соответствует системе ограничений  транспортной задачи.

2. Подсчитаем  число занятых клеток таблицы,  их 6, а должно быть m + n - 1 = 6. Следовательно,  опорный план является невырожденным.

Значение  целевой функции для этого  опорного плана равно:

Этап II. Улучшение опорного плана.

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем  максимальную оценку свободной клетки (1;2): 1

Для этого  в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

Цикл приведен в таблице (1,2; 1,1; 4,1; 4,2; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем  максимальную оценку свободной клетки (1;3): 3

Для этого  в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

Цикл приведен в таблице (1,3; 1,1; 4,1; 4,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем  максимальную оценку свободной клетки (3;1): 4

Для этого  в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

Цикл приведен в таблице (3,1; 3,2; 1,2; 1,1; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют  условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 1*15 + 3*15 + 2*25 + 4*10 + 3*5 + 1*30  = 195

Ответ: Оптимальный план содержит 6 перевозок: от первого поставщика 15 ед. ко второму потребителю и 15 ед. к третьему; от второго поставщика 25 ед. к третьему потребителю; от третьего поставщика 10 ед. к первому потребителю и 5 ед. ко второму; от четвертого поставщика 30 ед. к первому потребителю. При этом общая сумма транспортных расходов минимальна и составляет 195 ден.ед.

2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы  решить поставленную задачу, требуется  решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического  программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно  в случаях, когда число повторяющихся  подзадач экспоненциально велико.

Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

Словосочетание «динамическое  программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, каксистемный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Слово «программирование» в словосочетании «динамическое программирование»  в действительности к "традиционному"программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Подзадачи решаются делением их на подзадачи  ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи,   и   — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали   дважды. Если продолжать дальше и посчитать  , то   посчитается ещё два раза, так как для вычисления   будут нужны опять   и  . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.

Чтобы избежать такого хода событий  мы будем сохранять решения подзадач, которые мы уже решали, и когда  нам снова потребуется решение  подзадачи, мы вместо того, чтобы вычислять  его заново, просто достанем его  из памяти. Этот подход называетсякэширование. Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.