Алгоритмы по математике
Методическое пособие - Математика и статистика
Другие методички по предмету Математика и статистика
?вобождается одна из занятых клеток, получается новое опорное решение, которое нужно проверить на оптимальность.
Решение транспортной задачи методом дифференциальных рент
Алгоритм решения транспортной задачи методом дифференциальных рент
1) В каждом столбце отметить клетку с минимальным тарифом.
) В эти отмеченные клетки максимально распределить груз. Сначала в клетки, единственные отмеченные в строке и столбце, потом единственные в столбце или в строке с минимальными тарифами.
) Необходимо получить оценки поставщиков:
а) если поставщик не все вывез, то его оценка +n, где n - количество оставшегося груза у данного поставщика;
б) если все запасы исчерпаны, а потребности потребителей не удовлетворены с учетом распределения по всему столбцу, то оценка поставщика -, где - количество груза, необходимого потребителям в отмеченных столбцах данной строки, с учетом того груза, который, возможно, получил потребитель от других поставщиков. Потребности потребителя, которому не хватило товара, при оценке поставщиков учитываются один раз;
в) если все запасы поставщика исчерпаны и в отмеченных клетках столбцов потребитель удовлетворен с учетом всего столбца, то оценка 0. Знак нуля: если отмеченная клетка в строке связана в столбце с отмеченной клеткой только в отрицательной строке, то знак у нуля -. В остальных случаях знак +.
) Для каждого столбца найти ренту: разницу между отмеченным тарифом в отрицательной строке и минимальным тарифом в положительной строке.
) Выбрать минимальную не нулевую разность, которая называется промежуточной рентой.
) Промежуточная рента добавляется к тарифам в отрицательных строках. После чего составить новую таблицу с измененными тарифами и перейти к пункту 1 данного алгоритма. Если все оценки равны 0, то найдено оптимальное решение.
Замечания:
) Сумма всех оценок в каждой таблице должна быть равна 0.
) При подсчете общей стоимости перевозки использовать исходные тарифы, а не те, которые получились в последней таблице.
Решение транспортной задачи с дополнительными ограничениями\
Если даны дополнительные ограничения в транспортной задаче
то в таблице данные изменятся
а) если , то
б) если , то
в) если , то столбец разбивается на два столбца:
и
В найденном решении поставки в этих столбцах суммируются.
Метод динамического программирования
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом.
I. Задача об оптимальном распределении ресурсов состоит в том, что предприятие имеет возможность выделить С ден.ед. n филиалам (в зависимости от вложенной суммы филиал дает прирост прибыли ) с целью максимизации прибыли предприятия.
симплексный преобразование алгоритм базисный переменный
Алгоритм решения задачи об оптимальном распределении ресурсов
1. Составляется таблица, где вводят последовательность функций - максимальная прибыль фирмы, если х средств выделить одновременно
Очевидно, что
2. Выполняется обратный ход:
а) по определению
б) средства в объеме x распределяются между первым и вторым филиалами: второму в объеме x2 ден.ед., тогда средств выделяется первому филиалу. Общая прибыль двух филиалов
в) включается в рассмотрение 3-й филиал: из общей суммы х выделяется третьему филиалу х3 ден.ед., тогда остальная часть средств оптимальным образом распределяется между двумя первыми филиалами; общая прибыль
г) аналогично находится
и т.д.
3. Выполняется прямой ход:
находится и оптимальное такое, что , после чего результаты вычислений просматриваются в обратном порядке. Зная , находят - объем финансирования остальных n-1 филиалов, а следовательно, и и , и т.д. до нахождения и .
II. Пусть известны: возраст оборудования на начало планового периода лет, остаточная стоимость оборудования s(t) ден.ед., цена нового оборудования p ден.ед., стоимость продукции , произведенной за 1 год на оборудовании возраста и издержки на обслуживание оборудования возраста . Для расчета оптимальной стратегии предприятия по замене оборудования вводят функцию - максимальная прибыль за последние i лет планового периода. Очевидно, что
Алгоритм решения задачи о замене оборудования
1. Определить из условия задачи
,
и справа таблицу дополнить столбцом .
. Заполнить строку, переписав из таблицы данных соответствующие значения , а все значения заменить
числом , т.о.,
3. Начиная с индекса i = 2, расчет по строкам производится в соответствии с формулами
т.е. в следующей последовательности:
а) вычислить
где берется из уже заполненной строки;
б) вычислить
Получаемые значения вносить в соответствующие клетки строки, но начиная с первого , оставшиеся клетки заполнить значением mi;
в) клетки с первым значением в процессе заполнения таблицы отделить от значений, расположенных в строке левее, разделительной границей смены управления;
г) аналогично продолжить заполнение таблицы до последней строки, т.е. перейти к п. а) данного алгоритма.
. Дойдя до последнего ша