Математическое программирование

1.4. Решить задачу с использованием графического метода

,

Решение

1) Многоугольник решений.

Найдем точки, через которые пройдут предельные прямые [1, c. 20].

Строим многоугольник решений.

2) Оптимальные точки.

Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что Z_min находится в точке A, Z_max – в точке C.

3) Вычисление координат экстремумов.

Точка A – пересечение прямых L₁ и L₃:

Точка C – пересечение прямых L₂ и L₃:

4) Подсчет оптимальных значений.

Ответ: 88/3, 46.

2.4. Для изготовления 2-х видов продукции P₁ и P₂ используется 3 вида ресурсов R₁, R₂, R₃. Запасы ресурсов, нормы их использования и прибыль от реализации единицы продукции приведены в таблице. Найти план производства продукции, которой бы при заданных условиях обеспечивал наибольшую прибыль.

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

Pi Ri	Р1	Р2	Запасы ресурсов
R1	2	5	80
R2	4	3	91
R3	1	4	68
Прибыль	15	12

Решение

Составим математическую модель задачи. Искомый выпуск продукции P₁ обозначим через x₁, продукции P₂ – через x₂. Поскольку есть ограничение на выделенные ресурсы каждого вида, переменные x₁, x₂ должны удовлетворять такой системе неравенств:

Общая стоимость продукции при этом составляет: z = 15x₁ + 12x₂ .

По своему экономическому содержанию переменные x₁, x₂ больше 0.

Следовательно, приходим к математической задаче: среди всех неотрицательных решений системы неравенств нужно найти такое, при котором функция z примет максимальное значение.

Решим задачу графическим способом.

1) Многоугольник решений

Найдем точки, через которые пройдут предельные прямые [1, c. 20].

Строим многоугольник решений.

2) Оптимальные точки.

Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что F_min находится в точке O, F_max - в точке C.

3) Вычисление координат экстремумов.

Точка C - пересечение прямых L₁ и L₂:

4) Подсчет оптимальных значений.

Ответ: 4881/14.

Решим задачу ЛП симплекс-методом [1, c. 30].

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем к ограничениям-уравнениям. Введем дополнительные 3 переменные – x₃, x₄, x₅, в результате чего ограничения запишутся в виде уравнений:

Построим начальную симплекс-таблицу, где Q – неотрицательное отношение столбца плана к ключевому столбцу.

№	Базис	Cб	План	15	12	0	0	0	Q
				x1	x2	x3	x4	x5
1	x3	0	80	2	5	1	0	0	40
2	x4	0	91	4	3	0	1	0	91/4
3	x5	0	68	1	4	0	0	1	68
4			0	-15	-12	0	0	0	–

Cтолбик 1 есть ключевым, поскольку он содержит минимальный отрицательный элемент

Строка 2 есть ключевой, поскольку в ней минимальное Q₂=91/4.

Ключевой элемент находится на их пересечении и равный числу 4.

Вместо вектора x₄ , который выводим из базиса, вводим вектор x₁.

Делим ключевую строку на ключевой элемент 4.

Умножаем его на 15 и добавляем к 4 строке.

Умножаем его на -2 и добавляем к 1 строке.

Умножаем его на -1 и добавляем к 3 строке.

Получим следующую симплекс-таблицу.

№	Базис	Cб	План	15	12	0	0	0	Q
				x1	x2	x3	x4	x5
1	x3	0	69/2	0	7/2	1	-1/2	0	69/7
2	x1	15	91/4	1	3/4	0	1/4	0	91/3
3	x5	0	181/4	0	13/4	0	-1/4	1	181/13
4			1365/4	0	-3/4	0	15/4	0	–

Cтолбик 2 есть ключевым, поскольку он содержит минимальный отрицательный элемент

Строка 1 есть ключевой, поскольку в ней минимальное Q₁=69/7.

Ключевой элемент находится на их пересечении и равный числу 7/2.

Вместо вектора x₃ , который выводим из базиса, вводим вектор x₂.

Делим ключевую строку на ключевой элемент 7/2.

Умножаем его на 3/4 и добавляем к 4 строке.

Умножаем его на -3/4 и добавляем к 2 строке.

Умножаем его на -13/4 и добавляем к 3 строке.

Получим окончательную симплекс-таблицу.

№	Базис	Cб	План	15	12	0	0	0
				x1	x2	x3	x4	x5
1	x2	12	69/7	0	1	2/7	-1/7	0
2	x1	15	215/14	1	0	-3/14	5/14	0
3	x5	0	185/14	0	0	-13/14	3/14	1
4			4881/14	0	0	3/14	51/14	0

Составим двойственную задачу к данной [1, c. 88]. Ее коэффициенты складываются с исходной путем транспонирования. Систему ограничений составят коэффициенты оптимизирующей функции. Коэффициентами оптимизирующей функции z будут свободные члены исходной системы. Знаки неравенств изменятся на противоположные. Оптимизирующая функция – минимум функции. Двойственная задача будет заключаться в том, чтобы составить такой план производства, при котором затраты ресурсов будут минимальными.

Следовательно, через y₁ обозначим стоимость единицы ресурса 1 вида или А₁, y₂ – стоимость единицы А₂, y₃ – стоимость единицы А₃. Тогда  – стоимость продукции Р₁, которая не может быть дешевле чем 15 у.д.е. (условных денежных единиц), то есть первое неравенство: . Аналогично .

Общие потери ресурсов выражаются оптимизирующей функцией:

 при .

Следовательно, математически это запишется так:

С 4 рядка последней симплекс-таблицы виписываем оптимальный план, где y₁=x₃, y₂=x₄, y₃=x₅, тоесть .

.

Значение  отвечает значению 4881/14, что находится в 0 рядке планового столбика.

С экономической точки зрения нулевое значение переменной у₃ значит, что для минимальных издержек стоимость ресурсів R₃ должна равняться 0.

Таким образом, продукции P₁ и P₂ нужно производить 215/14 и 69/14 ед. соответственно. Максимальная прибыль при этом составит 4881/14 у.д.е.

Ответ: