2. Транспортная задача

Имеется p пунктов производства и q пунктов потребления некоторого однородного продукта. Известные объемы производства P_k в пунктах производства и объемы потребления Q₁ в пунктах потребления , а также затраты d_kl, связанные с перевозкой единицы продукта из пункта производства k в пункт потребления l. Требуется прикрепить пункты потребления к пунктам производства таким образом, чтобы суммарные расходы на транспортировку достигали минимума.

Через x_kl обозначим планируемый объем перевозок из пункта производства k в пункт потребления l. Тогда интересующий нас вопрос сводится к разысканию прямоугольной матрицы

, , , .

Будем считать, что суммарный объем производства совпадает с суммарным объемом по­требления, т. е.

. (11)

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

Определить матрицу

, (12)

максимизирующую линейную функцию

(13)

при ограничениях

, , , (14)

, , (15)

, , (16)

где , и d_kl — заданные величины, удовлетворя­ющие условию (11).

3. Решение задач линейного программирования с помощью пакета Solver

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

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

При этом пакет обеспечивает возможность:

• использовать одновременно до 200 адресов ячеек, содержащих отыскиваемые значения переменных (параметров);

• устанавливать конкретный результат для целевой функции и для этого значения отыскивать значение параметров;

• отыскивать оптимальное значение (минимальное или максимальное) целевой функции, то есть находить одно из наилучших возможных решений;

• генерировать множество различных решений для сложных задач линейного программирования. При этом возможно сохранение вариантов решении в виде сценариев.

Алгоритм решения задачи линейного программирования сводится к 3 этапам:

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

2. подготовка пакета Solver для решения задачи. На этом этапе в пакете передается значение адреса ячейки, содержащей целевую функцию, определяется отыскиваемое оптимальное или конкретное значение целевой функции, указывается диапазон ячеек, содержащий значения неизвестных (он должен быть непрерывным), заносятся все ограничения;

3. решение задачи. На этом этапе уточняется характеристика пакета и осуществляется поиск множества различных решений.