Автор работы: Пользователь скрыл имя, 13 Января 2013 в 16:52, практическая работа
Задача может быть сформулирована как стандартная задача линейного программирования с максимизируемой целевой функцией. Обозначим через х1 — число изделий 1, а через х2 — число изделий 2, выпускаемых еженедельно.
Имеем следующие ограничения:
Все хi , i = 1, 2 — целые числа. По смыслу данной задачи х1 и х2 — целые числа.
Необходимо решить, какое количество машин и с какого кирпичного завода надо отгрузить на каждую стройку, чтобы еженедельные издержки на его транспортировку были минимальными.
Задача может быть сформулирована как стандартная задача линейного программирования с минимизируемой целевой функцией.
Обозначим через y1 — количество автомашин кирпича, доставляемого с завода F1 на стройку W1, а через y2 — количество автомашин кирпича, доставляемого с завода F1 на стройку W2. Поскольку общая потребность строек в кирпиче задана, а также задано количество автомашин кирпича, которые может отгрузить каждый завод, то можно от трехмерной задачи перейти к двумерной, выразив количество автомашин кирпича, отгружаемого с завода F1 на третью стройку W3, а также количество автомашин кирпича, отгружаемого с завода F2 на все три стройки, через введенные переменные y1 и y2. Тогда таблица перевозок будет выглядеть следующим образом (табл. 4).
Т а б л и ц а 4
Таблица перевозок
Кирпичные заводы |
Стройки |
Возможности поставок, | ||
W1 |
W2 |
W3 |
автомашин в неделю | |
F1 |
y1 |
y2 |
11 – (y1 + y2) |
f1 = 11 |
F2 |
5 – y1 |
9 – y2 |
8 – [11 – (y1 + y2)] |
f2 = 11 |
Потребность строек, автомашин в неделю |
w1 = 5 |
w2 = 9 |
w3 = 8 |
Обозначим через nij — число автомашин, перевозящих кирпич с i-го завода на j-ю стройку. Тогда целевая функция D — транспортные издержки — выразится формулой
D = .
Подставив вместо сij и nij их значения из табл. 3, 4, получаем:
D = 3y1 + 2y2 + 2[11 – (y1 + y2)] + 1(5 – y1) + 4(9 – y2) + 3{8 – [11 –
– (y1 + y2)]} = 3y1 - y2 + 54.
Ограничения следуют из того, что все числа в ячейках таблицы перевозок (табл. 4) не должны быть меньше нуля, т. е. имеем следующие шесть неравенств:
y1 ³ 0;
y2 ³ 0;
11 – (y1 + y2) ³ 0;
5 – y1 ³ 0;
9 – y2 ³ 0;
8 – 11 + (y1 + y2) ³ 0.
Преобразовав неравенства-ограничения, получаем:
y1 ³ 0;
y2 ³ 0;
y1 + y2 £ 11;
y1 £ 5;
y2 £ 9;
y1 + y2 ³ 3.
Теперь задача сводится к двумерной и формулируется следующим образом: найти вершину (или точку) области допустимых решений, заданной системой неравенств-ограничений
5 ³ y1 ³ 0;
9 ³ y2 ³ 0;
y1 + y2 £ 11;
y1 + y2 ³ 3,
для которой целевая функция D = 3y1 - y2 + 54 достигает минимального значения.
Находим множество допустимых решений и стром график.
y1 = 0, y1= 5, y2 = 0, y2 = 9,
y1 + y2 = 3, y1 + y2 = 11.
Из неравенств и геометрических соображений ясно, что область допустимых решений ограничена многоугольником ABCDЕ.
Оптимальное решение находим графическим методом. На том же рис. 2 строим прямую, отвечающую значению целевой функции D = 54. Из выражения для целевой функции D = 3y1 -y2 + 54 получаем
3y1 -y2 + 54 =54+ y2=-3y1
Это прямая, проходящая через начало координат и имеющая отрицательный наклон к оси Оу1. Другим значениям целевой функции также соответствуют прямые, параллельные прямой D = 54, причем по мере их “смещения” относительно исходной прямой D = 54 в направлении стрелки значения целевой функции будут увеличиваться. Крайняя прямая, касающаяся многоугольника допустимых решений в вершине В с координатами у1 = 0; у2 = 9, соответствует минимальному значению целевой функции D = 45 тыс. руб.
Подставляя значения у1 = 0; у2 = 9 в ячейки табл. 4, получаем оптимальный план перевозок (табл. 5).
Ответ. Оптимальным является план перевозок, указанный в табл. 5. Ему отвечают наименьшие транспортные издержки 45 тыс. руб.
Таблица 5
Оптимальный план перевозок
Стройки |
Всего, | |||
Кирпичные заводы |
W1 |
W2 |
W3 |
автомашин в неделю |
F1 |
0 |
9 |
2 |
11 |
F2 |
5 |
0 |
6 |
11 |
Всего, автомашин в неделю |
5 |
9 |
8 |
22 |
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ