Математическое программирование (стр. 1 из 3)
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. Запасы ресурсов, нормы их использования и прибыль от реализации единицы продукции приведены в таблице. Найти план производства продукции, которой бы при заданных условиях обеспечивал наибольшую прибыль.
Задачу решить графическим способом и симплексным методом, составить двойственную задачу к исходной и выписать ее оптимальный план из последней симплекс-таблицы решенной исходной задачи.
 PiRi | Р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 строке.
Умножаем его на -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 есть ключевой, поскольку в ней минимальное Q1=69/7.
Ключевой элемент находится на их пересечении и равный числу 7/2.
Вместо вектора x3 , который выводим из базиса, вводим вектор x2.
Делим ключевую строку на ключевой элемент 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 будут свободные члены исходной системы. Знаки неравенств изменятся на противоположные. Оптимизирующая функция – минимум функции. Двойственная задача будет заключаться в том, чтобы составить такой план производства, при котором затраты ресурсов будут минимальными.
Следовательно, через y1 обозначим стоимость единицы ресурса 1 вида или А1, y2 – стоимость единицы А2, y3 – стоимость единицы А3. Тогда
– стоимость продукции Р1, которая не может быть дешевле чем 15 у.д.е. (условных денежных единиц), то есть первое неравенство: 
. Аналогично 
.Общие потери ресурсов выражаются оптимизирующей функцией:
при 
.Следовательно, математически это запишется так:
