Решение задачи линейного программирования симплекс-методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ация 3
-10000CBX7X8X9X400,20,30,320X500001X6061111X13060-100X228100-10X3150500-1?iF3(x) 2830-30-28-150
В таблице 4 переменные главного столбца и главной строки вместе со своими коэффициентами меняются местами, а все остальные переменные и их коэффициенты переписываются без изменений.
Элементы главной строки пересчитываются согласно алгоритму.
Элементы главного столбца делятся на минус главный элемент.
Вместо главного элемента необходимо записать обратное ему число и оно равно единице.
В главной строке и столбце есть ноль, поэтому элементы столбца и строки соответствующие нулю переписываются без изменений. Все остальные элементы пересчитываются по правилу прямоугольника.
В базисе не остались искусственные переменные, но данный план не оптимален т.к. среди относительных оценок есть одна отрицательная (-150).
Необходим переход к следующему базисному плану, представленному таблицей 5.
Таблица 5 - Итерация 4
-10000CBX7X8X9X400,20,30,320X900001X606111-1X13060-100X228100-10X31505001?iF4(x) 2830-30-28150
Заполнение и пересчёт новой итерации происходит аналогично предыдущей итерации.
В базисе нет искусственных переменных, но данный план не оптимален т.к. среди относительных оценок есть одна отрицательная (-30).
Необходим переход к следующему базисному плану, представленному таблицей 6.
Таблица 6 - Итерация 0
-10000CBX4X8X 5X700,663,31,060X900001X6060,33-0,3-0,02-1X13060,666670,30,320X22810010X31505001?iF5(x) 2850937,6150
Заполнение и пересчёт новой итерации происходит аналогично предыдущей итерации.
Все относительные оценки положительные и среди базисных переменных нет искусственных, следовательно, план является оптимальным и задача решена, решение находится в столбце B.
x1=60,66667 (руб.);
x2=10 (руб.).
x3=5 (руб.)
2.3 Решение задачи линейного программирования в Microsoft Excel
Решим задачу линейного программирования на нахождение максимального значения, алгоритм описан в пункте 1.2.
По условию задачи составим начальный план в Microsoft Excel. Выделим сначала ячейки под набор ограничений, под искомые переменные коэффициенты, значение целевой функции. Необходимо задать значение целевой функции как сумму произведений искомых переменных на коэффициенты. Так же надо сделать и для набора ограничений.
Начальный план решения задачи в Microsoft Excel дан на рисунке 1.
Рисунок 1 - Начальный план решения задачи
Вызываем Поиск решения, устанавливаем ячейки, которые будут изменяться и устанавливаем ячейку целевой функции, это представлено на рисунке 2.
Рисунок 2 - Поиск решений
Вводим набор ограничений и нажимаем кнопку выполнить.
После первых вычислений получаем X1, это представлено на рисунке 3.
Рисунок 3 - Первое значение
Далее нажимаем на кнопку продолжить.
После второго вычисления получим X2, это показано на рисунке 4.
Рисунок 4 - Второе значение
Повторяя те же самые действия, решим задачу.
Результат решения задачи и значение целевой функции представлено на рисунке 5.
Рисунок 5 - Результат поиска решения
Заключение
В данной курсовой работе было рассмотрено решение задачи линейного программирования симплекс методом. Задача была решена симплекс методом, также решение задачи линейного программирования представлено в Microsoft Excel.
Таким образом, вычислительная техника в настоящее время находит широкое применение, как в общей математике, так и в одном из её разделов - математических методах.
В данной работе был составлен оптимальный план выпуска продукции каждого вида, обеспечивающий максимальную прибыль.(заключение маловато)
линейное программирование симплекс метод
Список используемой литературы
1Зайченко Ю.П. Исследование операций. Киев: Высшая школа, 1997. - 152 с.
2Шумилова Л. Исследование операций. Киев: Высшая школа, 2004. - 137 с.
Реклейтис Г. Оптимизация в технике. М.:Мир,1982г. (В 2-х томах).
Вентцель Е.С. Исследование операций. М.: Высшая школа, 2002. - 255 с.
Кузнецов Ю.Н. Математическое программирование. М.: ЮНИТИ, 1999. - 311 с.
Химмельблау Д. Прикладное программирование. М.: Мир, 1999. - 391 с.
Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 2001. - 214 с.
Сакович В.А. Исследование операций. Минск: Высшая школа, 1998. - 162 с.