Процентный состав и запасы напитков
Напиток | Спирт | Вода | Сахар | Примеси | Количество, л/сут. |
Водка | 40% | 57% | 1% | 2% | |
Вино | 18% | 67% | 9% | 6% | |
Сок | 0% | 88% | 8% | 4% |
Постройте модель, на основании которой можно будет определить, хватит ли ресторану имеющихся ежедневных запасов напитков для удовлетворения возросшего спроса на коктейль.
Задача №1.10*
Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины – по 20 ед. ширины. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров приведены в табл.1.8.
Таблица 1.8
Варианты заказов на рулоны нестандартных размеров
Заказ | Требуемая ширина рулона, ед.шир. | Требуемое количество рулонов, шт. |
Все допустимые варианты разрезания рулонов приведены в табл.1.9. Рис.1.4 иллюстрирует 1-й вариант раскроя рулонов.
Таблица 1.9
Допустимые варианты раскроя рулонов
Требуемая ширина, ед.шир. | Вариант раскроя рулонов | Минимальное кол-во рулонов, шт. | |||||
1 | 2 | 3 | 4 | 5 | 6 | ||
Потери, ед.шир. |
Рис.1.4. 1-й вариант раскроя рулонов
Постройте математическую модель, позволяющую найти такой план разрезания рулонов, при котором поступившие заказы на нестандартные рулоны удовлетворяются с минимальными потерями (т.е. непригодными для реализации остатками рулонов).
Примечание 1.5. В данной задаче для удобства записи модели можно ввести переменные, не являющиеся искомыми величинами.
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ОДНОИНДЕКСНЫХ ЗАДАЧ
Теоретическое введение
Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи ЛП (1.1) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соотвествующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучем, одной точкой. В случае несовместности системы ограничений задачи (1.1) ОДР является пустым множеством.
Примечание №2.1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство
можно представить в виде системы двух неравенств (см. рис.2.1)
ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см. рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположнонаправлению вектора .
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня ( ), соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.