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

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

,

Решение

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

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

9 height=18 src="images/referats/14085/image004.png">

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

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. Запасы ресурсов, нормы их использования и прибыль от реализации единицы продукции приведены в таблице. Найти план производства продукции, которой бы при заданных условиях обеспечивал наибольшую прибыль.

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

Решение

Составим математическую модель задачи. Искомый выпуск продукции 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толбик 1 есть ключевым, поскольку он содержит минимальный отрицательный элемент

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

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

Вместо вектора x4 , который выводим из базиса, вводим вектор x1.

 Скачать реферат