Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение. Общий вид задачи линейного программирования.
|
|
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Общий вид задачи линейного программирования.
Найти значения переменных x 1, x 2, x 3,..., xn, при которых максимума или минимума max (min) достигает целевая функция.
z = c 1 x 1 + c 2 x 2 +... + cnxn
Если для переменных x1, x2,..., xn выполняются ограничения
Точки для которых выполняются ограничения называются допустимыми решениями (или планами). Множество точек допустимых решений образуют многоугольник допустимых решений.
Матричная форма записи задачи линейного программирования получится, если мы введем такие матрицы:
пример.
Процесс изготовления двух видов промышленных изделий заключается в последовательной обработке каждого из них на трех станках. Время использования каждого из этих станков ограничено 10 часами в сутки. Время обработки и прибыли от продаж каждого изделия приведены в таблице.
| Время обработки, мин | ||||
| изделие | 1 станок | 2 станок | 3 станок | прибыль |
Нужно определить оптимальные объемы производства изделия каждого вида.
Решение
Пусть изделий 1го вида изготавливается x 1 штук, а 2го вида – x 2 штук.
Прибыль: max z = 2 x 1 + 3 x 2.
Ограничения: 
Итак, max z = 2 x 1 + 3 x 2;
Графический метод задачи линейного программирования с двумя переменными
max (min) z = c 1 x 1 + c 2 x 2;
Чтобы решить графически нужно выполнить следующее:
1) построить многоугольник допустимых решений
2) если при некоторых значениях x 1, x 2 целевая функция z = a, то прямая c 1 x 1 + c 2 x 2 = a будет перпендикулярна нормаль вектору 
3) если решается задача на максимум, то a должно увеличиваться, поэтому двигая прямую перпендикулярно 
в направлении до тех пор пока прямая не будет иметь только одной общей точки с многоугольником допустимых решений. В этом положении прямая называется опорной, а координата полученной точки опорным решением (или планом). При решении задачи на минимум прямую двигаем против направления .
Продолжаем рассматривать начатый выше пример.
max z = 2 x 1 + 3 x 2;
Решение
(1) 
пробная точка O (0, 0): 
выполняется.
O (0, 0) лежит в полуплоскости
(2) 
O (0, 0): 
выполняется.
(3) 
O (0, 0): 
выполняется.
z = 2 x 1 + 3 x 2;
Двигаем до точки А.
А – опорное решение
Найдем координаты точки А.
Прибыль: 