Решение задачи линейного программирования симплекс-методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ак сумма парных произведений элементов столбца C на соответствующий столбец.
)Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.
.2 Алгоритм решения задач линейного программирования в Microsoft Excel
Для того чтобы решить задачу линейного программирования в редакторе Microsoft Excel, необходимо выполнить следующие действия:
-Ввести условия задачи:
а)создать экранную форму для ввода условия задачи:
1)переменных (дать имя массиву переменных);
2)ограничений;
3)целевой функции;
4)граничных условий;
б)ввести исходные данные в экранную форму:
1)коэффициенты целевой функции;
2)коэффициенты при переменных в ограничениях;
3)правые части ограничений;
в)ввести зависимости из математической модели в экранную форму:
1)формулу для расчета целевой функции;
2)формулы для расчета значений левых частей ограничений;
г)задать целевую функцию (в окне Поиск решения):
1)целевую ячейку;
2)направление оптимизации целевой функции;
д)ввести ограничения и граничные условия (в окне Поиск решения):
1)ячейки со значениями переменных;
2)граничные условия для допустимых значений переменных;
3)соотношения между правыми и левыми частями ограничений;
-Решить задачу:
а)Для решения задач в Microsoft Excel необходимо иметь надстройкуПоиск решения. Если в меню Сервис нет такого пункта, то установите пакет Поиск решения. Для этого запустите Сервис-> Надстройки. В открывшемся окне выберите надстройку Поиск решения. После этого пункт Поиск решения появится в меню Сервис.
б)Запустить задачу на решение (в окне Поиск решения).
2 Практическая часть
.1 Построение математической модели задачи
Для решения задачи составим ее математическую модель. Для этого введем обозначения:
Х1 - прибыль от реализации 1 т молока;
Х2 - прибыль от реализации 1 т кефира;
X3 - прибыль от реализации 1 т сметаны.
Стоимость:
X1 = 30 руб. ;
X2 = 28 руб;
X3 = 150 руб.
Критерий задачи:
Максимальная прибыль(max).
Итак, модель имеет вид:
.
.2 Нахождение максимальной прибыли
Для нахождения максимальной прибыли приведём модель к канонической форме.
Каноническая форма:
;
Симплекс-таблица заполняется в соответствии с алгоритмом, изложенным в пункте 1.1.
Нахождение оптимального плана, приводящего к максимальной прибыли, приведено в таблицах 1-5.
Таблица 1 - Итерация 0
-103028150000CBX1X2X3X7X8X9X4021,40,30,323,25000X505001000X60136111000Y1 -M60100-100Y2 -M100100-10Y3 -M 500100-1?iF0(x) -75M-M-30-M-28-M-150MMM
Значения целевой функции определяется путём вычисления суммы парных произведений столбца C и столбца B:
(руб.)
Значение относительных оценок так же вычисляются как сумма парных произведений элементов столбца C на соответствующий столбец:
Данный план не оптимален т.к. среди относительных оценок есть отрицательные:
M-30;
M-28;
M-150.
Из отрицательных относительных оценок нужно выбрать наибольшую по модулю, (-M-150), соответствующий ей столбец называется главным.
Для определения главной строки нужно столбец B поэлементно разделить на главный столбец:
,251=16,25;
1=136;
51=5.
Из всех значений необходимо выбрать наименьшее частное, оно равно пяти, это и будет главная строка.
На пересечении главной строки и главного столбца находится главный элемент, и он равен единице. В базисе остались искусственные переменные Y1 и Y2, Y3 .
Необходим переход к следующему базисному плану, представленному таблицей 2.
Таблица 2 - Итерация 1
-103028000CBX1X2X7X8X9X4021,40,30,32000X50000001X6013111001Y1-M6010-100Y2-M10010-10X315050000-1F1(x) -70M+750-M-30-M-28MM-150
В таблицу 2 переменные главного столбца вместе со своими коэффициентами записываются на место переменных главной строки, при этом главный столбец уходит, а все остальные переменные и их коэффициенты переписываются без изменений.
Элементы главной строки делятся на главный элемент:
,40,3=71,333;
1=131;
601=60.
В главной строке есть нули, поэтому элементы соответствующие этим нулям, переписываются без изменений. Все остальные элементы пересчитывают по правилу прямоугольника.
Данный план не оптимален т.к. среди относительных оценок есть отрицательные:
M-30;
M-28;
.
В базисе остались две искусственные переменные Y2 и Y1.
Необходим переход к следующему базисному плану, представленному таблицей 3.
Таблица 3 - Итерация 2
-10200000CBX2X7X8X9X403,40,320,300X5000001X60711101X130600-100Y2-M1010-10X31505000-1?iF2(x) -M+2550-М-28-30ММ
В таблицу 3 переменные главного столбца вместе со своими коэффициентами записываются на место переменных главной строки, при этом главный столбец уходит, а все остальные переменные и их коэффициенты переписываются без изменений.
Элементы главной строки делятся на главный элемент:
,40,32=10,625;
1=71;
101=10.
В главной строке есть нули, поэтому элементы соответствующие этим нулям, переписываются без изменений. Все остальные элементы пересчитывают по правилу прямоугольника.
Данный план не оптимален т.к. среди относительных оценок есть отрицательные:
M-28;
.
В базисе осталась одна искусственная переменная Y1.
Необходим переход к следующему базисному плану, представленному таблицей 4.
Таблица 4 - Ите