Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 4 из 14)
Обозначим через xjk - количество единиц материала j-го вида, раскраиваемых k-м способом,
.Математическая модель задачи имеет следующий вид:
.Вместо критерия минимизации себестоимости в задаче может быть взят, например, критерий минимизации отходов. В этом случае в условии должно быть задано количество отходов, получаемых при каждом способе раскроя для единицы материала каждого вида.
2.3. Геометрическая интерпретация и графическое решение ЗЛП.
Геометрическая интерпретация экономических задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически.
Случай двух переменных не имеет особого практического значения, но его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.
Пусть дана задача:
Z=c1x1+c2x2
max (2.6)
(2.7)
(2.8)Дадим геометрическую интерпретацию элементов этой задачи.
Введем на плоскости декартову прямоугольную систему координат x1Ox2 и сопоставим каждой паре чисел (x1,x2) точку плоскости с координатами x1 и х2. Выясним сначала, что представляет собой множество точек, соответствующих допустимым решениям данной задачи.
Рассмотрим одно линейное неравенство
.Оно определяет на плоскости одну из двух полуплоскостей, на которые прямая
разбивает плоскость (сторона в которой располагается полуплоскость от прямой, указывается штриховкой).Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству соответствует другая плоскость.
Каждое из ограничений (2.7), (2.8) задает на плоскости х1Oх2 некоторую полуплоскость. Нас интересуют те точки плоскости, координаты которых принадлежат всем полуплоскостям. Следовательно, допустимое множество ЗЛП геометрически изображается пересечением (общей частью) полуплоскостей, определяемых отдельными ограничениями. Полуплоскость - выпуклое множество. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Пересечение любого числа выпуклых множеств является выпуклым множеством. Таким образом, область допустимых решений задачи (2.6) - (2.8) есть выпуклое множество. На рис.2.1 представлены возможные ситуации, когда область допустимых решений ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая линия (г), луч (д), отрезок (е), пустое множество (ж).
X2 
X2 X2  |
 |
б)0 а) X1 0 X1
Х2 Х2 Х2  |
 |
 |
в) 1 д)г)
0 Х1 0 Х1 0 Х 1
Х2 Х2
 |
 |
е) ж)Х1
X2 
B C 
M 
A 
D