Заключение.

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

Метод северо-западного угла.	1970
Метод минимального элемента.	1320
Метод аппроксимации Фогеля.	1340
Метод потенциалов.	1320
Метод дифференциальных рент.	1280
Симплексный метод.	1280

П р и л о ж е н и е 2

( Из курсового проекта студентки 216 группы Афанасьевой Н.)

Целочисленное программирование Постановки задач, приводящие к требованию целочисленности.

Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех (части) переменных. Они получили название задач целочисленного (частично целочисленного) программирования.

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

Задача о ранце. Имеется m ограниченных ресурсов b=(b₁, b₂, …, b_m), которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз (j=1, 2, …, n) характеризуется следующими свойствами:

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

• полезностью c_j ;

• расходом i-го ресурса для перевозки единицы j-го груза a_ij , (i=1, 2, … , m; j=1, 2, … , n).

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

Обозначим через x_j — количество выбранных для транспортировки предметов и запишем математическую модель этой задачи. Очевидно, требованию неделимости соответствует условие:

x_j0, x_j — целые, j=1, 2, …, n. (1)

Сопоставление расхода ресурсов каждого типа для транспортировки единицы груза и наличия ресурсов приводит к ограничению

(2)

Общую полезность рейса определяет значение функции

(3)

Частным случаем задачи (1—3) является задача о ранце, в которой любой из заданного набора предметов j=1, 2, … , n может быть выбран или нет, т.е. для каждого из x_j допустимыми значениями является 0 (предмет не выбирается) или 1 (предмет выбирается). Это приводит к тому, что условие (1) задачи (1—3) заменяется требованием

, (1’)

и математическая модель принимает вид: в области, заданной условиями

определить такие составляющие вектора решения x=(x₁, x₂, … , x_n), которые максимизируют функцию

Известно, что дискретная величина, принимающая лишь значения 0 или 1, называется булевой. Поэтому задачи, в которых на переменные накладывается условие вида (1’), получили название задач с булевыми переменными.

Задача о выборе типа судов. Речное пароходство, осуществляя обслуживание пассажиров по различным маршрутам, определило, что в среднем по любому из них за сезон переезжает постоянное количество человек. Эффективность использования транспорьных средств пароходства складывается из эффективности обслуживания каждого маршрута и определяется разностью между доходами от рейсов и расходами пароходства по обслуживанию рейсов. Доходы определяются количеством проданных билетов, расходы — содержанием обслуживающего персонала, расходом горючего.

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

Пусть по j-му маршруту за сезон переезжает b_j⁽¹⁾ человек. Перевозку пассажиров по этому маршруту можно осуществлять m различными типами судов. Для каждого i-го типа судов (i=1, 2, … , m) известны следующие характеристики:

• a_id — грузоподъемность (число мест);

• a_i2 — количество человек обслуживающего персонала;

• a_i3 — расход горючего за сезон;

• c_ij — прибыль за сезон от использования i-го транспортного средства по j-му маршруту.

Необходимо выбрать парк судов для каждого маршрута, при котором максимизируется прибыль пароходства при соблюдении ограничений: общий расход горючего за сезон не может превосходить b₃ единиц, общая численность обслуживающего персонала не более b₂ человек.

Запишем математическую модель сформулированной задачи. Обозначим через x_ij — искомое количество судов i-го типа (i=1, 2, … , m), которое целесообразно содержать для обслуживания j-го маршрута (j=1, 2, … , n). Область поиска решения определится условиями:

x_ij0, x_ij — целые (i=1, 2, …, m; j=1, 2, …, n). Требуется в этой области найти такие значения переменных x=(x₁₁, x₁₂, …, x_1n, x₂₁, x₂₂, …, x_2n,…, x_m1, x_m2,…, x_mn), которые максимизируют функцию

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