Графическое решение ЗЛП
Графический способ решения задачи ЛП состоит из двух этапов.
1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.
2. Нахождение оптимального решения среди всех точек пространства допустимых решений.
Нахождение минимума целевой функции
Пример 2.2. Задача о диете
Фармацевтическая фирма Ozark ежедневно производит не менее 800 кг некой пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в следующей таблице.
| Мука | Белок | Клетчатка | Стоимость (в $ за кг) |
| (в кг на кг муки) | |||
| Кукурузная | 0,09 | 0,02 | 0,30 |
| Соевая | 0,6 | 0,06 | 0,90 |
Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма Ozark хочет определить рецептуру смеси минимальной стоимости с учетом требований диетологов.
Поскольку пищевая добавка состоит только из кукурузной и соевой муки, переменными для этой задачи, очевидно, будут
- количество (в кг) кукурузной муки, используемой в дневном производстве пищевой добавки;
- количество (в кг) соевой муки, используемой в дневном производстве пищевой добавки.
Целевая функция равна общей стоимости пищевой добавки, производимой за один день, и должна быть минимальной. В данном случае это можно записать следующим образом:
Минимизировать 
(или 
)
Ограничения модели должны отражать производственные требования и рекомендации диетологов. Фирма должна выпускать не менее 800 кг смеси в день; соответствующее ограничение будет записано следующим образом: 
.
Рассмотрим ограничение, связанное с количеством белка в пищевой добавке. Общее количество белка в смеси, состоящей из 
кг кукурузной муки и 
кг соевой муки, равно 
(кг).
Это количество должно составлять не менее 30% от общего объема смеси 
. Отсюда получаем следующее неравенство: 
Аналогично строится ограничение для клетчатки:
В последних двух неравенствах переменные и 
надо перенести из правых частей в левые. Окончательно модель примет следующий вид.
Минимизировать 
(или 
)
при ограничениях
, 
.
На рис. 2.3 показано графическое решение этой задачи.
Поскольку в данной модели следует минимизировать целевую функцию, поэтому нужно идти в направлении уменьшения ее значений (это направление на рис. 2.3 показано стрелкой). Оптимальное решение находится на пересечении прямых 
и 
, откуда получаем 
(кг) и 
(кг).
При этих значениях переменных минимальная стоимость производимой ежедневно пищевой добавки составляет 
Рис. 2.3. Графическое решение задачи о диете
Симплекс-метод решения ЗЛП
Графический способ решения задачи ЛП показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи ЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу ЛП к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
Стандартная форма задачи ЛП необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.
Стандартная форма ЗЛП
Задача, в которой требуется найти экстремум функции
при ограничениях
называется задачей линейного программирования, заданной в канонической (стандартной) форме.
Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.
1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
2. Все переменные неотрицательные.
3. Целевую функцию следует или максимизировать, или минимизировать.
Преобразование неравенств в равенства
Неравенства любого типа (со знаками неравенств £ или ³) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных (балансных) переменных – остаточных или избыточных, которые связаны с неравенствами типа «£» или «³» соответственно.
Для неравенств типа «£» в левую часть неравенства вводится неотрицательная переменная. Например, в модели компании Mikks, ограничение на количество сырья С1 задается в идее неравенства 
.
Вводя новую неотрицательную переменную 
, которая показывает остаток (неиспользованное количество) сырья С1, это ограничение преобразуется в равенство 
Неравенства типа «≥» в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели «диеты» неравенство 
показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству 
, 
.
Положительное значение избыточной переменной 
показывает превышение суточного производства добавки над минимальным значением 800 фунтов.
Пример 2.4.
Преобразуем следующую задачу ЛП в стандартную форму:
при выполнении следующих условий:
Для преобразования задачи в стандартную форму выполним следующие действия.
1. Вычтем из левой части первого неравенства дополнительную (избыточную) переменную 
и затем умножим все неравенство на -1, для того чтобы правая часть неравенства стала положительной.
2. Добавим дополнительную (остаточную) переменную 
к левой части второго неравенства.
3. Так как третье ограничение изначально записано в виде равенства, поэтому оставляем его без изменения.
Получаем следующую стандартную задачу линейного программирования.
при выполнении следующих условий:
Основы симплекс-метода
Рассмотрим общую ЗЛП с 
ограничениями и 
переменными, записанную в стандартной (канонической) форме
,
(2.1)
Как правило, число уравнений задачи меньше числа переменных (т.е. 
), поэтому множество ее допустимых решений равно 
. Задача состоит в том, чтобы найти наилучшее решение в смысле принятого критерия (минимума целевой функции).
Мы уже говорили, что оптимальное решение представляет собой одну из вершин многогранника допустимой области. Другими словами, оптимальное решение - это одно из базисных решений.
Получение одного из базисных решений основано на известном классическом методе решения систем линейных уравнений – методе Гаусса-Жордана.
Основная идея этого метода состоит в сведении системы 
уравнений с 
неизвестными к каноническому или ступенчатому виду при помощи элементарных операций над строками:
1) умножение любого уравнения системы на положительное или отрицательное число;
2) прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.
При использовании первых 
переменных такая система имеет следующий вид:
(2.2)
Переменные 
, входящие с единичными коэффициентами в одно уравнение системы (2.2) и с нулевыми в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная.
Остальные 
переменные 
называются небазисными переменными.
При записи системы в каноническом виде все ее решения можно получить, присваивая независимым переменным произвольные значения и решая затем получающуюся систему относительно базисных переменных.
Определение. Базисным решением системы (2.2) называется решение, полученное при нулевых значениях небазисных переменных.
Например, в системе (2.2) одно из базисных решений задается как
(2.3)
Определение. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных 
, что эквивалентно условию 
.
Т.к. различные базисные решения системы (2.2) соответствуют различным вариантам выбора 
из общего числа 
переменных 
, то число допустимых базисных решений (угловых точек) не превышает 
.
Поэтому ЗЛП можно решать посредством перебора конечного числа угловых точек допустимого множества 
, сравнивая значения ЦФ в этих точках. Это наихудший вариант решения ЗЛП, т.к. требует огромного объема вычислений.
Пример: если 
(задача небольшой размерности), то количество переборов составит 
(кол-во вариантов).
Обычно 
.
Идея симплекс-метода (СМ) состоит в направленном переборе угловых точек допустимого множества 
с последовательным уменьшением ЦФ 
. СМ разработал Дж. Данциг (американский ученый) в 1947 г. Этот метод называют также методом последовательного улучшения решения (плана). Гарантии результативности СМ обеспечиваются следующей теоремой.
Теорема (о конечности алгоритма симплекс-метода). Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Это решение может быть получено через конечное число шагов симплекс-методом, причем, начать можно с любого исходного базиса.
Шаг 4.
1. Поменять местами переменные 
и 
, остальные переменные оставить на прежних местах.
2. На место опорного элемента поставить число 
.
3. На остальных местах разрешающей (опорной) строки записать соответствующие элементы исходной таблицы, делённые на опорный элемент.
4. На свободные места разрешающего столбца поставить со знаком минус соответствующие элементы исходной таблицы, делённые на опорный элемент.
Шаг 5.
Оставшиеся свободные места в новой СТ заполнить построчно следующим образом: из строки элементов исходной таблицы вычесть произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы.
На этом заполнение новой таблицы заканчивается и происходит переход к Шагу 1.
Пример 2.5. Приведем ход решения задачи по данному алгоритму:
| Базисные переменные | 
| 
| Свободные члены |
| 6 | 4 | 24 |
| 1 | 2 | 6 |
| -1 | 1 | 1 |
| 0 | 1 | 2 |
|
| -5 | -4 | 0 |
| Базисные переменные |
|
| Свободные члены |
|
| 0,17 | 0,67 | 4,00 |
|
| -0,17 | 1,33 | 2,00 |
|
| 0,17 | 1,67 | 5,00 |
|
| 0,00 | 1,00 | 2,00 |
|
| 0,83 | -0,67 | 20,00 |
| Базисные переменные |
|
| Свободные члены |
|
| 0,25 | -0,50 | 3,00 |
|
| -0,13 | 0,75 | 1,50 |
|
| 0,38 | -1,25 | 2,50 |
|
| 0,13 | -0,75 | 0,50 |
|
| 0,75 | 0,50 | 21,00 |
Ответ: 
Транспортная задача
Транспортная задача является особым типом задач целочисленного программирования, для которых разработаны простые и эффективные способы нахождения оптимального решения, не требующие громоздких вычислений. Экономико-математическую модель транспортной задачи рассмотрим на следующем примере.
Пример 2.6. Имеются три поставщика некоторого товара и четыре потребителя этого товара. Причём известна стоимость перевозки товара от каждого поставщика к каждому потребителю. Требуется найти объёмы перевозок для каждой пары "поставщик − потребитель" так, чтобы суммарные затраты на перевозку были минимальны, запасы всех поставщиков реализованы и потребности всех потребителей удовлетворены (табл.2.1).
Таблица 2.1.
| Поставщики | Потребители | Запасы поставщиков, | |||||||
|
|
|
|
| ||||||
|
| 7 | 2 | 4 | 8 | 340 | ||||
| 
| 
| 
| ||||||
|
| 8 | 9 | 6 | 5 | 200 | ||||
| 
| 
| 
| ||||||
|
| 3 | 5 | 7 | 2 | 160 | ||||
| 
| 
| 
| ||||||
Спрос потребителей, 
| 120 | 170 | 150 | 260 | 
| ||||
В левом верхнем углу произвольной клетки стоит коэффициент, равный стоимости перевозки от поставщика, номер которого указан в этой строке, к потребителю, номер которого указан в столбце.
В теории транспортной задачи таблица вида табл. 2.1 называется таблицей поставок.
Построим экономико-математическую модель данной задачи, обозначив через 
объем поставляемого товара от i -го поставщика к j- му потребителю. Чтобы запасы каждого поставщика были полностью реализованы, должны быть справедливы уравнения баланса для каждой строки таблицы поставок, т. е. выполняться равенства
(2.4)
Чтобы спрос каждого из потребителей был удовлетворён, должны быть справедливы уравнения баланса для каждого столбца таблицы поставок, то есть
(2.5)
Поскольку объём перевозимого груза величина неотрицательная, то должны выполняться ограничения на переменные :
Суммарные затраты F на перевозку определяются указанными в таблице поставок тарифами перевозок и размерами поставок:
(2.6)
Решить транспортную задачу − значит на множестве неотрицательных решений системы ограничений найти такое решение, при котором линейная функция принимает минимальное значение.
Транспортная задача называется закрытой (сбалансированной) , если сумма запасов всех n поставщиков равна сумме потребностей всех m потребителей:
В противном случае транспортная задача называется открытой. Решение открытой транспортной задачи сводят к решению закрытой транспортной задачи введением фиктивных потребителей, когда сумма запасов превышает сумму потребностей, или фиктивных поставщиков, когда сумма потребностей превышает сумму запасов. При этом тарифы перевозок для фиктивных поставщиков и потребителей принимаются равными нулю.
Число основных (базисных) переменных закрытой транспортной задачи равно m + n −1, где n − число поставщиков; m − число потребителей; так как в закрытой транспортной задаче сумма запасов всех поставщиков равна сумме потребностей всех потребителей.
При заполнении таблицы поставок клетки, соответствующие неосновным (свободным) переменным, оставляют пустыми, а в клетки, соответствующие базисным переменным, проставляют числа, определяющие количество поставки . В частности, если транспортная задача вырожденная, некоторые поставки могут иметь нулевую величину и в этом случае в базисную клетку записываем число 0.
Нахождение первоначального базисного распределения – опорного плана задачи − возможно любым из известных методов: наименьшей стоимости, "северо-западного угла", Фогеля, наибольшего предпочтения.
Рассмотрим метод "северо-западного угла". "Северо-западным углом" называется ячейка таблицы поставок, соответствующая значению переменной 
. В эту ячейку записываем максимально возможную поставку, определяя её по формуле
(2.7)
Если 
, то запас первого поставщика распределен полностью, и переходим к заполнению клетки с 
, записывая в неё наименьшее из чисел 
и 
. Если 
, то полностью удовлетворена потребность первого потребителя, тогда переходим к заполнению клетки с 
, записывая в неё наименьшее из чисел 
и 
. Так, постепенно двигаясь по таблице поставок, распределяем все запасы и удовлетворяем все потребности. Движение по таблице поставок может быть или по горизонтали, или строго по вертикали, а повороты при движении по трассе делаются только под прямым углом.
При заполнении таблицы следим за выполнением баланса по строкам и столбцам. Число заполненных клеток в полученном распределении должно быть равным числу базисных (основных) переменных. Если поворот происходит в клетке, где размер поставки равен нулю, то говорят о вырожденном плане поставок. В этом случае нулевая поставка записывается в клетку, где трасса распределения поставок делает поворот, и клетка считается занятой.
Если распределение выполняется без вычислительных ошибок, в последнюю заполняемую клетку запишется число, получаемое автоматически и равное остатку нераспределённых количеств у последнего из участвующих в распределении поставщиков или количеству неудовлетворённого спроса последнего потребителя.
Получаемое распределение по методу "северо-западного угла" для транспортной задачи, исходные данные которой содержатся в табл. 2.1, показано в табл. 2.2.
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане, равное стоимости поставок, равно
Таблица 2.2.
| Поставщики | Потребители | Запасы поставщиков, | |||||||
|
|
|
|
| ||||||
|
| 7 | 2 | 4 | 8 | 340 | ||||
| 120 | 170 | 50 | |||||||
|
| 8 | 9 | 6 | 5 | 200 | ||||
| 100 | 100 | ||||||||
|
| 3 | 5 | 7 | 2 | 160 | ||||
| 160 | |||||||||
| Спрос потребителей,
| 120 | 170 | 150 | 260 |
| ||||
Другим методом определения опорного плана поставок является метод наименьшей стоимости.
В первую очередь при определении объёмов поставок занимают клетки, имеющие наименьшие тарифы перевозок. Так, в рассматриваемом примере начнём с клетки 
, имеющей тариф 2. От первого поставщика ко второму потребителю поставим максимально возможное количество груза, а именно 
. Потребности второго потребителя полностью удовлетворены, и все клетки второго столбца далее не рассматриваем.
На втором шаге распределения выбираем клетку 
с тарифом 2 и делаем в неё поставку 
. Теперь запас третьего поставщика полностью израсходован и все клетки третьей строки далее не рассматриваем.
Соответственно, по наименьшим значениям остающихся неиспользованными в табл. 2.3 тарифов делаем следующие поставки:
Последняя поставка получается автоматически, так как остаётся только одна клетка для заполнения и туда помещается остаток запасов и потребностей. Они равны, поскольку сумма всех запасов и сумма всех потребностей равны.
Таблица 2.3.
| Поставщики | Потребители | Запасы поставщиков, | |||||||
|
|
|
|
| ||||||
|
| 7 | 2 | 4 | 8 | 340 | ||||
| 20 | 170 | 150 | |||||||
|
| 8 | 9 | 6 | 5 | 200 | ||||
| 100 | 100 | ||||||||
|
| 3 | 5 | 7 | 2 | 160 | ||||
| 160 | |||||||||
| Спрос потребителей,
| 120 | 170 | 150 | 260 |
| ||||
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане равно
Методом наименьшей стоимости получился лучший опорный план, так как значение целевой функции на нем меньше на 100 единиц. Тем не менее, и этот план может быть не оптимальным.
Критерий оптимальности для транспортной задачи: базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.
Для определения оценок свободных клеток используют два взаимозаменяемых метода: распределительный и потенциалов. Рассмотрим один из них, а именно метод потенциалов.
Потенциалы - числа для нахождения оценок допустимого плана, полученного в ходе распределения запасов поставщиков. Потенциалы для поставщиков и потребителей вычисляются по тарифам 
занятых клеток таблицы поставок. Для потенциалов поставщиков 
и потребителей 
, соответствующих занятым клеткам, справедливы равенства
(2.8)
Так как занятых клеток на одну меньше, чем число потенциалов, значение одного из потенциалов (все равно какого) назначается произвольно и может быть любым действительным числом (обычно полагают равным нулю, чтобы не усложнять вычисления остальных потенциалов).
Разрешая равенства (2.8) относительно потенциалов, получаем их числовые значения. Оценки свободных клеток таблицы поставок рассчитываются по формулам
(2.9)
Если построенное первоначальное решение не удовлетворяет критерию оптимальности, то среди свободных клеток, имеющих отрицательную оценку, выбираем ту, для которой абсолютная величина оценки наибольшая. Отмечаем эту клетку знаком " + " и строим из неё цикл.
Циклом в таблице поставок называют ломаную линию, проходящую через занятые клетки, начинающуюся и заканчивающуюся в одной и той же свободной клетке. Эта ломаная линия имеет вершины в клетках и звенья, лежащие вдоль строк и столбцов таблицы поставок. Причём ломаная должна быть связной, и в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, а другое − по столбцу. Клетки, через которые проходит ломаная линия, не делая в них поворота, называются транзитными, и имеющиеся в них поставки не участвуют в процессе перераспределения. Таким образом, цикл проходит через занятые клетки и только через одну свободную клетку, начинаясь и заканчиваясь в ней.
Последовательно отмечаем вершины цикла знаками " + " и " − " так, чтобы соседние вершины были отмечены противоположными знаками.
Среди поставок, находящихся в клетках помеченных знаком "−", выбираем наименьшую и помещаем ее в пустую клетку, помеченную знаком " + ". Затем рассчитываем новые значения поставок, прибавляя выбранное число ко всем поставкам, стоящим в клетках, помеченных знаком " + ", и вычитая его из всех поставок, стоящих в клетках, помеченных знаком " − ". Для вновь полученного плана поставок рассчитываем по занятым клеткам потенциалы, а затем оценки новых свободных клеток.
Если критерий оптимальности выполняется для полученного плана, то задача решена. В противном случае продолжаем процесс перераспределения поставок до тех пор, пока не будет получено оптимальное решение транспортной задачи.
Для вычисления оценки свободной клетки 
таблицы поставок распределительным методом необходимо построить цикл для неё и найти оценку по формуле
где записаны в порядке прохождения цикла с чередованием знаков "+" и "-" тарифы перевозок для всех клеток, образующих цикл оцениваемой свободной клетки.
Пример 2.7. Решить транспортную задачу с опорным планом, заданным в табл. 2.3, методом потенциалов.
Вычислим потенциалы для занятых клеток и результаты расчётов поместим в табл. 2.4:
Рассчитаем оценки свободных клеток таблицы поставок:
Таблица 2.4.
| Поставщики | Потребители | Запасы поставщиков, | Потенциалы | |||||||||
|
|
|
|
| |||||||||
|
| 7 | 2 | 4 | 8 | 340 |
| ||||||
| 170 | 150 | ||||||||||
|
| 8 | 9 | 6 | 5 |
| 200 |
| |||||
|
| 100 | |||||||||||
|
| 3 | 5 | 7 | 2 | 160 |
| ||||||
| 160 | ||||||||||||
| Спрос потребителей,
| 120 | 170 | 150 | 260 |
| |||||||
Потенциалы 
|
|
|
|
| ||||||||
Среди найденных оценок одна меньше нуля, следовательно, найденный план не является оптимальным. Делаем перераспределение поставки в клетку 
. Цикл, найденный для перемены плана поставок, показан в табл. 2.4.
Находим размер перемещаемой в клетку поставки по размерам отмеченных знаком "-" поставок, а именно:
Прибавляем число 100 к поставкам, отмеченным знаком "+", вычитаем число 100 из поставок, отмеченных знаком "−", новое получаем распределение поставок. Заносим результаты в новую таблицу поставок (табл. 2.5). Для вновь полученного плана поставок и по тарифам занятых клеток считаем значения потенциалов.
Таблица 2.5.
| Поставщики | Потребители | Запасы поставщиков, | Потенциалы | |||||||
|
|
|
|
| |||||||
|
| 7 | 2 | 4 | 8 | 340 |
| ||||
| 20 | 170 | 150 | ||||||||
|
| 8 | 9 | 6 | 5 | 200 |
| ||||
| 200 | ||||||||||
|
| 3 | 5 | 7 | 2 | 160 |
| ||||
| 100 | 60 | |||||||||
| Спрос потребителей,
| 120 | 170 | 150 | 260 |
| |||||
| Потенциалы
|
|
|
|
| ||||||
Находим оценки свободных клеток:
Для найденного плана
Подсчитаем значение целевой функции:
Поскольку все оценки свободных клеток положительные, найденный план является оптимальным планом транспортной задачи. Минимальная стоимость перевозок определяется значением целевой функции на этом плане, и она равна 2500 денежных единиц.
ВВЕДЕНИЕ В ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Линейное программирование (ЛП) – это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны.
ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках.
Задача, в которой требуется найти экстремум функции
при ограничениях:
называется задачей линейного программирования.
Задача в краткой записи имеет вид
1.1. Модели линейного программирования с двумя
переменными
Пример 2.1. Компания Mikks производит краску для внутренних и наружных работ из сырья двух типов С1 и С2. Следующая таблица представляет основные данные для задачи.
|
| Расход сырья (в тоннах) на тонну краски | Максимально возможный ежедневный расход сырья | |
| Для наружных работ | Для внутренних работ | ||
| Сырье С1 | 6 | 4 | 24 |
| Сырье С2 | 1 | 2 | 6 |
| Доход (в тыс. долл.) на тонну краски | 5 | 4 | |
Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т (из-за отсутствия надлежащего спроса), а также поставил условие, чтобы ежедневное производство краски для внутренних работ не превышало более, чем на 1 т аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.
Задача (модель) линейного программирования (ЗЛП), как и любая задача исследования операций, включает три основных элемента.
1. Переменные, которые следует определить.
2. Целевая функция, подлежащая оптимизации.
3. Ограничения, которым должны удовлетворять переменные.
Определение переменных – первый шаг в создании модели. В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:
ежедневный объем производства краски для наружных работ;
ежедневный объем производства краски для внутренних работ.
Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тысячах долларов) и положим, что 
.
В соответствии с целями компании получаем задачу:
Максимизировать 
, или 
Итак, остался не определенным последний элемент модели - условия (ограничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом.
Из таблицы с данными имеем следующее.
Используемый объем сырья 
(т)
Используемый объем сырья 
(т)
Поскольку ежедневный расход сырья С1 и С2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.
(сырье С1)
(сырье С2)
Существует еще два ограничения по спросу на готовую продукцию:
1) максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т, т.е. 
2) ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну (разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны), т.е. 
Еще одно неявное ограничение состоит в том, что переменные 
и 
должны быть неотрицательными.
Таким образом, к сформулированным выше ограничениям необходимо добавить условие неотрицательности переменных: 
, 
. Окончательно задача будет записана следующим образом:
Максимизировать 
(или 
)
при выполнении следующих ограничений:
, 
.
Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение 
и 
будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения 
и 
в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно 
(тысяч долларов).
Итак, задача сформулирована.
Теперь встает вопрос о нахождении оптимального допустимого решения, доставляющего максимум целевой функции. После некоторых раздумий приходим к выводу, что задача имеет много (фактически, бесконечно много) допустимых решений. По этой причине невозможна подстановка значений переменных для поиска оптимума, т.е. нельзя применить простой перебор всех допустимых решений. Следовательно, необходима эффективная процедура отбора допустимых решений для поиска оптимального.
Графическое решение ЗЛП
Графический способ решения задачи ЛП состоит из двух этапов.
1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.
2. Нахождение оптимального решения среди всех точек пространства допустимых решений.
Дата: 2019-11-01, просмотров: 695.
