Главная | Обратная связь

Транспортная задача(классическая)- решается симплекс-методом

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

Алгоритм:

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

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

3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Алгоритм решения транспортной задачи

методом потенциалов

1. Найти исходное опорное решение.

2. Найти потенциалы из системы уравнений u_i + v_j = c_ij, справедливых для занятых клеток. Так как занятых клеток m+n-1, то система будет состоять из m+n-1 уравнений с m+nнеизвестными. Эта система имеет бесконечное множество решений. Для того чтобы найти частное решение системы, придадим одному из неизвестных любое числовое значение, например u₁=0, и найдем значения остальных.

Потенциалы u_i и v_j записываем в столбце и в строке, которые добавляем к таблице.

3. Для всех свободных клеток найти оценки D_ij= u_i + v_j - c_ij.

4. Проверка решения на оптимальность.

Если все D_ij£0, то найденное решение оптимально

Если среди оценок есть хотя бы одно положительное число, то найденное решение не оптимально и его надо улучшить.

5. Выбирается клетка с наибольшей положительной оценкой, и соответствующую переменную вводят в базис, для этого строят цикл для этой клетки. Даем поставку в эту клетку . Тогда нарушится баланс и в строке, и в столбце, следовательно, нужно отнимать  от одной из поставок данного столбца и строки до тех пор, пока цикл не замкнется.

Свойства цикла:

1) в цикле всего одна свободная клетка, в которую пишем +;

2) если строка или столбец участвует в цикле, то двумя клетками + и -;

3) число клеток цикла четно.

Можно доказать, что для любой свободной клетки можно построить единственный цикл.

6. Определяется  так, чтобы одна из занятых клеток освободилась и чтобы оставшиеся поставки x_ij 0, т.е. =min x_ij для четных клеток цикла.

7. Строится новая распределительная таблица, в которой изменяются только клетки цикла, остальные переписываются без изменения.

8)Переход в п. 2.

Задача формирования оптимального портфеля ценных бумаг

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

Решение задачи:

Расчет доходности и риска (дисперсии) по каждому виду ценных бумаг и корреляции доходности между двумя ценными бумагами

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