Модель этой задачи

Основные задачи и модели, используемые в математическом программировании.

1. Задача распределения ресурсов. Пусть предприятие может выпустить 4-ре продукта измеряемых в следующих величинах: грамм, килограмм, центнер и тонна. Продукты продаются на рынке по ценам соответственно: 4 деньги за грамм, 5 денег за килограмм и 9 денег за центнер и 11 денег за тонну. Продукты изготавливаются из трех видов ресурсов запасы, которых соответственно: 15 метров, 120 литров и 100 часов. Нормы расходов каждого ресурса, на каждый продукт определяет следующей табличкой

I	II	III	IV
			5 (л/т)

Определить такой план выпуска продукции, чтобы суммарный доход был максимальный.

Ресурсы – технологии – деньги.

Обозначим выпуск продукции X1, X2, X3, X4. Это вещественные числа, т.е. любе доли грамм, килограмм, центнера и тонн.

Maxd = 4*X1 + 5*X2 + 9*X3 + 11*X4

По первому ресурсу ограничения 1р ~ 1*X1 + 1*X2 + 1*X3 + 1*X4 ≤ 15

По второму ресурсу ограничения 2р ~ 3*X1 + 2*X2 + 4*X3 + 5*X4 ≤ 120

По третьему ресурсу ограничения 3р ~ 10*X1 + 12*X2 + 13*X3 + 14*X4 ≤ 100

X>0 продукт выпускается, X<0 продукт не выпускается. (X – любое) Ограничение, а выпуск X≥0

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

Функция d соответствующий критерий принятия решения называется функцией цели. Ограничения по ресурсам называется ограничением задач, а ограничение на знак переменных (x≥0) называется ограничение на тип искомых величин – переменных. В нашем случае не отрицательная, вещественная.

Это классическая задача на выпуск продукции. Выпуск продукции – это программа предприятия, т.е. мы «программируем» предприятие с помощью математики. Значит, мы имеем задачу математического программирования (ЗМП). Придумал и сформулировал историю этой науки Конторович, он был гений, где-то в 37 году, он решил транспортную задачу и потом решил нашу задачу (см. выше) и много других подобный. Купнонс – другой ученый. Нобелевская премия в 72 году была получена ими двумя.

Замечания к задаче распределение ресурсов:

1. Могут быть ограничения на выпуск продукции, например, выпускать второго продукта не меньше 2 кг (X2≥2)

2. Ограничение на комплектность. Пусть, продукты следует выпускать в комплекте, каждая из которых содержит 2 грамма первого, 3 кг второго, 1 центнер третьего, 1 тонну четвертого. Тогда необходимо записать следующее;;.

3. X по своему типу может быть не только вещественным, но и целым числом. Например, вы считаете количество станков, количество деталей, людей и т.д., т.е. продукты неделимые. Тогда в ограничения необходимо написать Х – целое. Тип Х может быть и дискретный, т.е. вы берете не любое число, а из набора чисел. Например, X1 =.

4. Задача на максимум ОБЯЗАТЕЛЬНО содержит ограничения типа меньше или равно или равно, если таких ограничений нет, то ответ тривиальный – бесконечность.

5. Функция цели может быть и на минимум (например, минимум затрат на производство продукции), но тогда должны быть обязательно ограничения вида больше или равно, либо равно, чтобы не получить тривиальный ответ – 0. Т.е. если вы решаете на минимум затрат (наименьшие затраты), то обязательно должно быть условие на выпуск продукции (выпустить не меньше).

6. Именно противоречия между функцией цели и ограничениями дает нам наилучшую или оптимальную точку.

Эта задача для Х – произвольная, является линейной задачей или ЗЛП (задачей линейного программирования). При этом функция цели линейная для Х, а ограничения линейные, не строгие неравенства или равенства. Это классическая задача называется задачей распределения ресурсов, позволяет определить выпуск продукции так, чтобы получить максимальную выгоду.

Вторая задача: Задача о содержании.

Рассмотрим эту задачу в постановке задачи о питании студента.

Для того, чтобы студент мог нормально учиться и не попал в больницу, для этого необходимо, чтобы он получал 100 грамм жиров, 30 грамм углеводов и 5 грамм белков (цифры условные). Для этого студент закупил большое количество продуктов, которые он может брать в любых количествах, а именно суп, колбасу, шоколад, пиво.

Кг	Жиры	Углеводы	белки
Суп (150 р)
Колбаса (350 р)
Шоколад (500 р)
Пиво (100 р)	-

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

Математическая модель задачи

Обозначим в кг рацион питания Х1, Х2, Х3 и Х4. Тогда функция цели

Z=150*X1+350*X2+500*X3+100*X4. Тогда очевидно, что если Х≥0, то ответ равен нулю. Нужны ограничения.

Ограничения по жирам ~ 150*Х1+50*Х2+300*Х3 ≥ 100

Ограничения по углеродам ~ 20*X1+30*X2+100*X3+60*X4 ≥30

Ограничения по белкам ~ 2*X1+4*X2+1*X3+1*X4 ≥5

Замечание: в такой постановке (берем любое количество продуктов) задача линейная, однако если студент питается в столовой, продукты покупает, то суп он может брать кратно пол порции X1={0,2; 0,4; 0,6; 0,8, 1}. Суп X3 ={0,1; 0,2; 0,3; 0,4}. Колбаса Х3={любое}. Пиво X4={0,25; 0,5…}В этом случае задача становится существенно не линейная.

Задача о смеси

Возьмем нефтяную постановку.

Нефтеперерабатывающий завод выпускает 3 сорта бензина: А-80, А-92, А-95. И продает по следующим ценам за тонну: 25, 28, 30. Бензины производятся путем смешивания (примем, что без потерь массы) следующих 4-ех продуктов: алкилат 300 тонн, бензин прямой перегонки 200 тонн, крекинг бензин 150 тонн, изопентан 50 тонн.

Если смешать наши вещества в пропорциях 5:3:2:1, то получим А-80, если 3:2:2:1, то получим А-92, если 2:1:3:2, то получим А-95.

Вопрос: каких сортов, и какие бензины изготавливать, и сколько, чтобы получить максимум суммарного дохода?

Возможный вариант модели.

Обозначим Х1,Х2,Х3 в тоннах выпуск соответствующего бензина, тогда доход будет иметь следующий вид max d = 25*X1+28*X2+30*X3.

Ограничение по алкитату X1+ X2+ X3 ≤ 300

П X1+ X2+ X3 ≤200

К X1+ X2+ X3 ≤150

И X1+ X2+ X3 50

Задача о смеси линейная

Транспортная задача.

Пусть имеется 3 склада, на которых соответственно имеется 100, 80 и 120 единиц продукции. Пусть имеется 4 потребителя этой продукции, которые требуют не меньше чем 40, 160, 20, 80 ед продукции.!Заданно затраты на перевозку единицы продукции от каждого поставщика к каждому потребителю.

Сколько стоит переслать единицу продукции:

Поставщик 1
Поставщик 2
Поставщик 3

Вопрос: Определить такой план перевозки, чтобы затраты были минимальные (сколько кому вести)?

Дата добавления: 2014-01-03