1.4. Решить задачу с использованием графического метода
,
Решение
1) Многоугольник решений.
Найдем точки, через которые пройдут предельные прямые [1, c. 20].
Строим многоугольник решений.
2) Оптимальные точки.
Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что Zmin находится в точке A, Zmax – в точке C.
3) Вычисление координат экстремумов.
Точка A – пересечение прямых L1 и L3:
Точка C – пересечение прямых L2 и L3:
4) Подсчет оптимальных значений.
Ответ: 88/3, 46.
2.4. Для изготовления 2-х видов продукции P1 и P2 используется 3 вида ресурсов R1, R2, R3. Запасы ресурсов, нормы их использования и прибыль от реализации единицы продукции приведены в таблице. Найти план производства продукции, которой бы при заданных условиях обеспечивал наибольшую прибыль.
Задачу решить графическим способом и симплексным методом, составить двойственную задачу к исходной и выписать ее оптимальный план из последней симплекс-таблицы решенной исходной задачи.
Pi
Ri
Р1
Р2
Запасы
ресурсов
R1
2 5 80
R2
4 3 91
R3
1 4 68 Прибыль 15 12
Решение
Составим математическую модель задачи. Искомый выпуск продукции P1 обозначим через x1, продукции P2 – через x2. Поскольку есть ограничение на выделенные ресурсы каждого вида, переменные x1, x2 должны удовлетворять такой системе неравенств:
Общая стоимость продукции при этом составляет: z = 15x1 + 12x2 .
По своему экономическому содержанию переменные x1, x2 больше 0.
Следовательно, приходим к математической задаче: среди всех неотрицательных решений системы неравенств нужно найти такое, при котором функция z примет максимальное значение.
Решим задачу графическим способом.
1) Многоугольник решений
Найдем точки, через которые пройдут предельные прямые [1, c. 20].
Строим многоугольник решений.
2) Оптимальные точки.
Строим вектор нормали, координаты которого . Передвигая линию уровня r в направлении нормали, находим, что Fmin находится в точке O, Fmax - в точке C.
3) Вычисление координат экстремумов.
Точка C - пересечение прямых L1 и L2:
4) Подсчет оптимальных значений.
Ответ: 4881/14.
Решим задачу ЛП симплекс-методом [1, c. 30].
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем к ограничениям-уравнениям. Введем дополнительные 3 переменные – x3, x4, x5, в результате чего ограничения запишутся в виде уравнений:
Построим начальную симплекс-таблицу, где 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 есть ключевой, поскольку в ней минимальное Q2=91/4.
Ключевой элемент находится на их пересечении и равный числу 4.
Вместо вектора x4 , который выводим из базиса, вводим вектор x1.
Делим ключевую строку на ключевой элемент 4.
Умножаем его на 15 и добавляем к 4 строке. ............
