2. Математическая модель

2.1. Исходные параметры

– количество пунктов A_i

– количество пунктов B_j

– количество товара в пункте A_i

– количество товара в пункте B_j, причем .

– тариф перевозки единицы товара из пункта A_i в пункт B_j.

2.2. Управляемые параметры

– количество товара, перевезенного из пункта A_i в пункт B_j.

– матрица управляемых параметров (решение, план перевозок).

2.3 Формулировка критерия оптимальности

Сформулируем критерий оптимальности. Пусть – стоимость произвольного плана перевозок . Требуется найти план перевозок наименьших транспортных затрат.

2.4. Ограничения модели

Необходимо вывезти весь товар из пунктов A_i и полностью удовлетворить потребности пунктов B_j в этом товаре Система ограничений имеет вид:

Таким образом, транспортная задача ставится как задача определения такого набора управляемых параметров ,

на котором достигается наименьшее значение критерия

при условии

.

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

4. Задача о раскрое.

1. Экономическая постановка задачи

Имеются стержни длиной 5 м. Необходимо их разрезать на заготовки 2-х видов: А – длиной 1,5 м; В – длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.

2. Математическая модель

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

Таблица 1

Способ	Количество заготовок А (по 1,5 м)	Количество заготовок В (по 0,8 м)	Отходы, м
1	3		0,5
2	2	2	0,4
3	1	4	0,3
4		6	0,2

Для изготовления 20 изделий потребуется 40 заготовок А (202=40) и 60 заготовок В (203=60).

Введем переменные (управляющие параметры). Обозначим за – количество стержней, которые будут разрезаны I способом, – II способом, – III способом, – IV способом.

Сформулируем критерий оптимальности. Пусть целевая функция Z описывает отходы. Ее будем минимизировать. Найдем отходы, полученные при разрезании стержней:

– отходы, полученные при разрезании стержней 1-м способом, так как 5 - 3·1,5 = 0,5;

– отходы, полученные при разрезании стержней 2-м способом, так как 5 - 2·1,5 - 2· 0,8 = 0,4;

– отходы, полученные при разрезании стержней 3-м способом, так как 5 - 1·1,5 - 4· 0,8 = 0,3;

– отходы, полученные при разрезании стержней 4-м способом, так как 5–6· 0,8 = 0,2.

Тогда .

Составим систему ограничений задачи.

Ограничение на заготовки А.

При разрезании стержней 1-м способом получим заготовок А, стержней 2-м способом – заготовок А, стержней 3-м способом – заготовок А, при разрезании стержней 4-м способом заготовок А не образуется. Таким образом, всего получим + + заготовок А, что по условию задачи должно быть не менее 40, т.е. + + .

Аналогично получим ограничение на заготовки В:

.

Составим ограничения на смысл переменных. Так как количество стержней может быть только неотрицательным числом, то и – целые.

Итак, математическая модель данной задачи имеет вид

;

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