Задачи по "Математическому моделированию"

Вопрос 1

Постановка задачи линейного программирования, целевая функция, система ограничений, граничные условия на переменные, область допустимых решений, оптимальное решение. Вопрос существования и единственности решения задачи линейного программирования.

Ответ:

Линейное программирование - математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции

[pic 1]

при условиях

[pic 2];   [pic 3];   [pic 4]

Указанная функция F называется целевой функцией (или линейной формой) задачи ЛП, а условия  – ограничениями данной задачи.

Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального значения функции F при выполнении ограничений, где k = m и l = n.

Канонической задачей линейного программирования называется задача, которая состоит в определении максимального значения функции F при выполнении ограничений, где k = 0 и l = n.

Совокупность чисел X=(x1;…xn) , удовлетворяющих ограничениям задачи, называется допустимым решением (или планом).

Совокупность чисел X=(x*1;…x*n), удовлетворяющих ограничениям задачи ЛП, называется допустимым решением (или планом).

Решение задачи линейного программирования называется вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является невырожденным.

Вопрос 2

Постановка задачи выбора варианта как задачи дискретного программирования, логическая переменная «включения процесса», дискретная функция прибыли, ограничения потребления ресурсов запасами ресурсов, оптимальный вариант «включения процессов», нахождение оптимального решения методом перебора.

Ответ:

Основная задача дискретного программирования — выбор наилучшего варианта из конечного, возможно, очень большого их числа.

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

Для решения задач дискретного программирования используются следующие основные методы:

— метод отсечения для задач (частично) целочисленного линейного программирования;
—комбинаторные методы;
— приближенные методы.

Для примера решим  задачу выбора вариантов. Будем считать, что для получения результата в виде прибыли необходимо два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли.

Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех (k ≤ 3).

Для составления модели принимаем, что j-му варианту будет соответствовать [pic 5] (j = 1,...,4).

При этом [pic 6]

Математическая модель задачи будет иметь вид:

F([pic 7]) = 65x [pic 8] + 80x [pic 9] + 90x [pic 10] + 210x[pic 11] [pic 12]

при ограничениях

200x [pic 13] + 180x [pic 14]+ 240x [pic 15] + 250x[pic 16] £ 800

10x [pic 17] + 15x [pic 18] + 22x[pic 19] + 28x [pic 20] £ 50

[pic 21] + [pic 22] + [pic 23] + [pic 24] £ 3

0 £ [pic 25] £ 1, [pic 26]- целые, ( j = 1,...,4).

Результаты решения задачи приведены в первом столбце

Из решения видно, что наибольшая прибыль F([pic 27]) = 300 будет получена в том случае, если будут приняты третий и четвертый варианты.