Дополнительная литература

1. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах.-М.:Высшая школа, 1999, 1ч.

2. Кондаков В.М. Математическое программирование. Элементы линейной алгебры и линейного программирования. Уч. пособие.-Пермь, 1997.

3. Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические методы в планировании.-М.:Высшая школа, 1991.

4. Ромахин М.И. Элементы линейной алгебры и линейного программирования.-М.:Высшая школа, 1963.

5. Карасев А.И., Кремер Н.Ш., Савельева Т.И. Математические методы и модели в планировании. -М.:Экономика,1987.

6. Канторович Л.В., Горстко А.Б. Оптимальные решения в экономике.-М.:Наука,1972.

Часть II транспортная задача. Методы решения Общая постановка транспортной задачи

Транспортная задача – это классическая задача линейного программирования о нахождении рационального с точки зрения затрат плана перевозок однородного продукта от изготовителя (поставщика) к потребителю.

Общая формулировка транспортной задачи:

Имеется nпунктов – изготовителей однородной продукции (i= 1,2,…,n) иmпунктов – потребителей этой продукции (j=1,2,…,m).

Пусть при одной и той же единице измерения объема продукции объем производства в каждом из пунктов-изготовителей равен a₁,а₂,…а_nсоответственно, а объем той же продукции, требующийся потребителю -b₁,b₂, …b_m. Стоимость доставки единицы продукции отi–го изготовителя кj–му потребителюизвестна, ее обозначим через с_ij. Объем поставляемой продукции отi–го изготовителя кj–у потребителю являетсянеизвестнойвеличиной, ее обозначим через х_{i j}.

Требуется определить, какое количество продукции (х_{i j}) и в адрес каких потребите-лей должен отправить каждый из пунктов-изготовителей, чтобы общая сумма затрат на перевозки была минимальной, при этом вся производственная продукция была бы реализована, а заявленная потребность пунктов-потребителей полностью удовлетворена.

Построение математической модели

Исходя из общей формулировки задачи и введенных нами обозначений следует, что:

1. расходы по транспортировке всей продукции будут равны ; требование минимизировать транспортные расходы представим в виде выражения;

2. суммарный объем поставок j-му потребителю должен быть равным его потребности в данном продукте, т.е.;

3. общая сумма поставок, произведенных i-м поставщиком равна объему всей произведенной им продукцией, т.е.

Замечание 1: Если в транспортной задаче вся изготовленная продукция строго равна заявленной потребности, т.е., тогда такая задача называетсясбалансированнойи ее модель будет иметь следующий вид:

,,, с_ij0, х_{i j}0.

Замечание 2: Если баланс производства и потребления нарушен в сторону произведенной продукции, т.е. ее часть не вывозится>, то задача называетсяоткрытойи ее решение необходимо начать с приведения к виду закрытой путем введения фиктивного потребителя. Потребность в произведенной продукции фиктивного потребителя принимают равнойb_m+1=-.

Замечание 3: Если баланс производства и потребления нарушен в сторону потребляемого продукта, т.е. суммарный объем производимого продукта меньше объема продукта, необходимого потребителям<, то задача называетсяоткрытойи ее решение необходимо начать с приведения к виду закрытой путем введения фиктивного поставщика. Объем продукта, производимый фиктивным поставщиком принимают равнымa_m+1=-.

Представление условия транспортной задачи в табличной форме. Табличная форма является наиболее оптимальной для представления условия транспортной задачи, а также подготавливает к первому шагу исследования. Приведем общий вид таблицы (Таблица 1).

Построенная таблица называется Т-таблицейилитаблицей перевозок. Она содержитnmклеток, содержащих величину стоимости доставки единицы продукции отi–го изготовителя кj–му потребителю (с_ij) и объемы поставляемой продукции (х_{i j}).

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

Таблица 1