Задачи для самостоятельного решения

1*. При выращивании некоторой культуры (или группы родственных культур) может быть использован i -тый вид удобрений в количестве, не большем, чем b_i кг (i= 1, …, m). Вся посевная площадь содержит n почвенно-климатических зон, причем площадь j -той зоны равна d_j га(j= 1, …, n). Внесение на каждый гектар площади j -той зоны 1 кг удобрений i -того вида увеличивает среднюю урожайность на c_ij центнеров. Требуется распределить выделенный фонд удобрений между посевными зонами так, чтобы суммарный прирост урожайности культур за счет внесения удобрений бы максимальным.

2*. Для производства чугунного литья используется n различных исходных шихтовых материалов (чугун различных марок, стальной лом, феррофосфор и др.). Химический состав чугунного литья определяется содержанием в нем химических элементов (кремния, магния, фосфора и др.). Готовый чугун должен иметь строго определенный химический состав, который задается величинами H_j, представляющими собой доли (в процентах) j -того химического элемента в готовом продукте. При этом известны величины: h_ij – содержание в процентах j -того химического элемента в i -том исходном шихтовом материале; с_i – цена единицы каждого i -го шихтового материала. Определить состав шихты, обеспечивающий получение литья заданного качества при минимальной общей стоимости используемых шихтовых материалов.

3*. Для выполнения четырех видов землеройных работ могут быть использованы экскаваторы четырех типов. Производительность экскаватора i -того типа при выполнении j -той работы задается матрицей

Учитывая, что на каждой из работ может быть задан только лишь один экскаватор и что все экскаваторы должны быть задействованы, найти такое распределение экскаваторов между работами, которое обеспечивает максимальную производительность.

Практика 2

Геометрическая интерпретация ОЗЛП

Пример.

Требуется определить максимум функции, если целевая функция имеет вид:

, (1)

при условиях:

, (2)

Решение.

Рассмотрим случай, когда число переменных n на два больше, чем число линейно независимых m, то есть n–m =2, тогда две неотрицательных переменных, например, и ≥ 0 можно выбрать в качестве свободных, а остальные , , , , ≥ 0 – базисные переменные – выразить через эти свободные переменные

(3)

После преобразования получим систему уравнений

(4)

Также выразим целевую функцию через свободные переменные.

. (5)

Далее дадим задаче геометрическую интерпретацию. По осям ОХ ₁ и ОХ ₂ будем откладывать значение свободных переменных , . А так как они положительнв, то значения и будут находиться в первом квадранте. Остальные переменные тоже будут неотрицательными.

, (6)

И поэтому необходимо изобразить систему уравнений (6) на плоскости Х ₂ ОХ ₁.

Строим прямые:

, (7)

Прямые изображены на рис. 1.

Рис.1. Область допустимых значений

По одну сторону этих прямых базисные переменные больше нуля, по другую – меньше. Мы выбираем ту сторону, где переменные больше нуля (это следует из условия постановки задачи).

Каждая из этих прямых определяет допустимую плоскость в соответствии с системой (6). Часть плоскости Х ₂ ОХ ₁ принадлежащая одновременно всем этим полуплоскостям представляет собой область допустимых решений (ОДР).

После построения ОДР возник вопрос о нахождении в этой области оптимального решения, то есть такого решения, которое обращает в максимум целевую функцию.

Рис.3.1.а. Область допустимых значений

Свободный член в приведенной целевой функции первоначально не присутствует, он появляется при переходе к переменным , .

Функции и достигают оптимального значения при одних и тех же значениях , , поэтому дальше будем использовать функцию .

Вместо набора прямых на плоскости строиться основная прямая =0. При перемещении этой прямой в одну сторону будет возрастать, при перемещении в другую убывать. Направление воздействия целевой функции должно определяться знаками коэффициентов.

Дадим геометрическую интерпретацию нахождения оптимального решения основной задачи линейного программирования среди допустимых решений.

Пусть имеется область допустимых решений, построена основная прямая и известно направление ее воздействия (рис.3.1.). Двигая основную прямую в направлении, указанных стрелок найдем максимальное значение, рисунок 3.1.а.

Поскольку при перемещении прямой L остается неясным какая же из точек, а именно, точка А или точка В является ее крайней границей, то проверим обе точки.

Точка А образована пересечением прямых . Найдем ее координаты:

X₆ =0, X₂ = 5;

Х ₇ =0, X₂ = 2 х ₁ - 12.

5=2 х ₁ - 12→ х ₁= 8,5;

x₂ = 5.

Координаты точки В (8,5;5). Значение целевой функции в этой точке L_B=19.

Точка В образована пересечением прямых . Найдем ее координаты:

X₃ =0, X₂ = х ₁ - 4;

Х ₇ =0, X₂ = 2 х ₁ - 12.

х ₁ - 4=2 х ₁ - 12→ х ₁= 8;

x₂ = 4.

Координаты точки В (8;4). Значение целевой функции в этой точке L_B=20.

Таким образом, функция L=20 достигает своего максимального значения в точке В с координатами (8;4).