Методы оптимизации в технико-экономических задачах

Выясним, до какого предела можно увеличивать x1:

из второго уравнения следует ограничение: x1 =0,38;

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

1=-12,53;

То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.

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

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

Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.

Задача оптимального распределения перевозок

Теоретическая часть

Разновидностью задачи линейного программирования, записанной сразу в канонической форме, является транспортная задача.

В типичной транспортной задаче предполагается наличие некоторого количества пунктов отправления А1, А2, … , Аm (это могут быть склады, базы, хранилища и др.) и некоторого количества пунктов назначения В1, В2, … , Вn (это могут быть фабрики, магазины и др.).

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

cij - стоимость перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения;

ai - запасы груза в i-ом пункте отправления;

bj - потребности в грузе в j-ом пункте назначения;

xij - количество единиц груза, перевозимого из i-ого пункта отправления в j-ый пункт назначения.

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

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

В случае, если запасы груза превышают потребность в них, то есть , то вводится фиктивный(n+1)-ый пункт назначения с потребностью bn+1=и стоимостью перевозки единицы груза (или эквивалентной характеристики) принимается равной нулю, то есть сi n+1=0 при i=1 m

В случае, если потребности больше, чем запасы груза, то есть , то вводится фиктивный (m+1)-ый пункт отправления с запасом груза am+1= и стоимость перевозки единицы груза (или эквивалентной характеристики) считаются равными нулю, то есть сm+1 j при j=1 n