Пример задачи оптимизации и её решение

Симплекс-методом.

Необходимо загрузить судно в порту 3-мя родами груза а, б, в. Грузоподъёмность судна = 2000т (Q_p); грузовместимость(W) = 3080м³; удельный погрузочный объём каждого груза: W_а =2, 1м³/т

W_б = 1, 5м³/т

W_в = 1, 7м³/т

Max возможное время погрузки (Т_n^max) = 36ч = 2160 мин

Удельное время погрузки каждого рода груза:

t_а = 0, 8мин/т

t_б = 0, 9мин/т

t_в = 1, 3мин/т

Имеется в порту в наличии груза:

а = 900т

б = 1300т

в = неограниченное количество

За перевозку 1т груза взимается провозная плата:

Са = 8 у. е.

Сб = 7, 5 у. е.

Св = 7 у. е.

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

Обозначим: х₁ – количество груза а, загруженного в оптимальном плане.

х₂ – количество груза б, загруженного в оптимальном плане.

х₃ – количество груза в, загруженного в оптимальном плане.

Целевая функция - доход

Z = 8x₁ + 7, 5x₂ + 7x₃ → max

Ограничения.

Перейдём от системы неравенств к системе равенств, добавляя свободные переменные.

х₄– неиспользуемая грузоподъёмность

х₅ – неиспользуемая грузовместимость

х₆ – неиспользуемое до max время

погрузки.

х₇ – недопогруженное количество груза а.

х₈ – недопогруженное количество груза б.

Представим условия (т. е. ограничения) в виде векторов.

Р₁ = Р₂ = Р₃ = Р₄ =

Р₅ = Р₆ = Р₇ = Р₈ = Р₀ =

Вектора Р₁, Р₂, Р₃, образованные из коэффициентов при реальных переменных, называются структурными.

Вектора Р₄, Р₅, Р₆, Р₇, Р₈ называются линейно не зависимыми (свободными) векторами, Р_о – вектор решений.

Данная задача решается относительно m линейно независимых базисных векторов. В данном случае, это свободные векторы (образующиеся из коэффициентов при свободных переменных) Р₄ - Р₈.

Алгоритм решения предусматривает построение симплекс-таблиц.

Z _j – симплекс-оценка

Zj =

Z _j – C_j – признак оптимальности в симплекс-методе.

Если задача решается на max и значение последней строки ≥ 0 по всем столбцам, то план является оптимальным.

Если задача решается на min и значение последней строки 0, то план так же является оптимальным.

Если при решении задач на max. хотя бы у одного вектора значение

Z_j – C_j < 0, то план не оптимален и требует улучшения.

В общем виде первоначальная симплекс-таблица выглядит следующим образом:

Симплекс-метод . Алгоритм перехода от одного допустимого плана к другому.

Данный алгоритм позволяет превратить неоптимальный план в оптимальный.

Алгоритм имеет следующие этапы:

I. Определятся вектор, который вводится в базис.

Это вектор, который имеет max. нарушение признака оптимальности.

Столбец, который соответствует вводимому в базис вектору, называется ключевым, его индекс обозначается буквой k .

В нашем примере k = 1

II. Определяется вектор, который выводится из базиса. Это тот вектор, у которого имеет место следующее соотношение.

для x_ik > 0

x_i – элементы вектора решений (столбца Р₀)

x_ik – элементы ключевого столбца.

Строка, которая соответствует минимуму, т. е. выводимому из базиса вектору, называется ключевой строкой, её индекс обозначается буквой r. Элемент таблицы, который находится на пересечении k-ого столбца и r-той строки, называется генеральным элементом и обозначается x_rk.

III. Определяется новые значения элементов вектора решений.

Р^’₀ = P₀ - ΘP_k

х^’_i = x_i - Θxik

Для ключевой строки значение Р₀ = Θ, т.е. х^’r = q

IV. Определяется новое значение ключевой строки

x^’_{r j} =

V. Определяются новые значения всех остальных элементов симплекс-таблицы

x’_ij = x_ij -

Где – элемент данного вектора в ключевой строке.

– соответствующий элемент в ключевом столбце.

– генеральный элемент.