2 Решение задачи о распределении ресурсов
2.1 Математическая модель
Фабрика выпускает три вида тканей. Суточные ресурсы фабрики следующие: 700 ед. производственного оборудования, 800 ед. сырья, 600ед. электроэнергии, расход которых на единицу ткани представлен в таблице:
Ресурсы |
Ткани |
||
I |
II |
III |
|
Оборудование |
2 |
3 |
4 |
Сырье |
1 |
4 |
5 |
Электроэнергия |
3 |
4 |
2 |
Цена одного метра ткани I равна 8 ден. ед., ткани II – 7 ден. ед. и III – 6 ден. ед. Сколько нужно произвести ткани каждого вида, чтобы от реализации была наибольшей?
Пусть по плану
предприятие должно выпускать
м. ткани первого вида,
м.
ткани второго вида и
м.
ткани третьего вида. Тогда
ден. ед.- стоимость ткани первого вида,
ден. ед. - стоимость ткани второго вида
и
ден. ед. стоимость ткани третьего вида.
Суммарная стоимость ткани будет равна
(
ден. ед.
Так как прибыль должна быть максимальной, то задача сводится к максимизации целевой функции
Опишем систему ограничений:
ед. производственного
оборудования требуется для выпуска
м ткани первого вида,
ед. производственного
оборудования – для выпуска
м ткани второго вида.
ед. производственного
оборудования – для выпуска
м ткани третьего вида.
На выпуск всей
ткани требуется
ед. производственного оборудования.
Аналогично, для
выпуска всей ткани потребуется
ед. сырья и
ед. электроэнергии.
Так как запасы ресурсов ограничены, то учитывая условия задачи, получаем:
Условия
неотрицательности:
,
,
.
Таким образом, математическая модель
задачи имеет вид:
При ограничениях:
2.2 Получение опорного плана
Это задача линейного
программирования записанная в стандартной
форме. Перейдем к канонической форме
записи задачи, для этого в левой части
ограничений вводим дополнительные
переменные:
,
,
Эти переменные выбираются так, чтобы
они выполнялись в равенства.
,
,
,
,
,
.
Физически
,
,
означают остатки ресурсов, не использованные
в производстве.
За базисные
переменные выбираем
Не базисными переменными являются
приравниваем к 0. В результате получим
первоначальный опорный план:
,
.
2.3 Проверка оптимального плана производства
Для проверки плана
на
оптимальность построим первую симплекс
таблицу:
|
|
8 |
7 |
6 |
0 |
0 |
0 |
|
||
|
|
|
|
|
|
|
|
|
||
|
700 |
2 |
3 |
4 |
1 |
0 |
0 |
700/2=350 |
||
|
800 |
1 |
4 |
5 |
0 |
1 |
0 |
800/1=800 |
||
|
600 |
3 |
4 |
2 |
0 |
0 |
1 |
600/3=200 min |
||
|
0 |
-8 |
-7 |
-6 |
0 |
0 |
0 |
|
||
Min (350; 800; 200)=200
Оценки в строке получены следующим образом:
– значение целевой
функции для текущих базисных переменных
Для оптимального
опорного решения в задачи на максимум
требуется не отрицательность всех
оценок
,
так как
в d
– строке отрицательны, то это
свидетельствует о правильности решения.
Улучшение решения.
Наибольшая по
модулю отрицательная оценка
.
В базис будет включена соответствующая
не базисная переменная
.
Составим отношения свободных членов к
положительным элементам разрешающего
столбца, данные отношения приводятся
справа от таблицы. Наименьшему частному
min
(350; 800; 200)=200 ему соответствует строка
.
Эта переменная исключается из базиса.
В таблице разрешающий столбец и
разрешающая строка выделена штриховкой
=3.
Построим новую симплекс – таблицу:
|
|
|
8 |
7 |
6 |
0 |
0 |
0 |
|
|
|
в |
|
|
|
|
|
|
|
0 |
|
300 |
0 |
0.33 |
2.67 |
1 |
0 |
-0.67 |
300/2.67=112.5 |
0 |
|
600 |
0 |
2.67 |
4.33 |
0 |
1 |
-0.33 |
600/4.33=138.46 |
8 |
|
200 |
1 |
1.33 |
0.67 |
0 |
0 |
0.33 |
200/0.67=300 |
|
|
1600 |
0 |
3.67 |
-0.67 |
0 |
0 |
2.67 |
|
Делим разрешающую
строку (3) на разрешающий элемент. Делаем
,
а все остальные элементы этого разрешающего
столбца (2) равными 0 (методом Гаусса).
Базисное решение,
которое дает таблица
,
0*300+0*600+8*200=1600.
Это
решение не является оптимальным, так
как в d
– строке имеется отрицательная оценка
.
Применяем последнюю таблицу за исходную,
повторяем запись и строим новую симплекс
– таблицу:
|
|
|
8 |
7 |
6 |
0 |
0 |
0 |
|
|
в |
|
|
|
|
|
|
6 |
|
112.5 |
0 |
0.13 |
1 |
0.37 |
0 |
-0.25 |
0 |
|
112.5 |
0 |
2.13 |
0 |
-1.63 |
1 |
0.75 |
8 |
|
125 |
1 |
1.25 |
0 |
-0.25 |
0 |
0.5 |
|
d |
1675 |
0 |
3.75 |
0 |
0.25 |
0 |
2.5 |
В последней строке таблицы d – строка не содержит отрицательных оценок, что свидетельствует об оптимальности полученного решения:
Ответ: Нужно выпускать 125 м ткани первого вида и 112.5 м ткани третьего вида. При этом оборудование и электроэнергия используются полностью, а сырье останется в количестве 112.5 ед. Прибыль от реализации ткани составит 1675 ден. ед. и будет максимальной.
3 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ НАДСТРОЙКИ EXCEL «ПОИСК РЕШЕНИЯ»