Использование линейного программирования для решения задач оптимизации (стр. 3 из 4)

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

Геометрический метод

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c₁x₁+c₂x₂ = а (1)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

Именно так и надо поступать при геометрическом решении задач линейного программирования . на многоугольнике решений следует найти точку, через которую проходит линия уровня функции Fс наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c₁ и c₂ и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :

F=c₁x₁ + c₂x₂ = а₁ (I)

F=c₁x₁ + c₂x₂ = а₂ (II)

F=c₁x₁ + c₂x₂ = а₃ (III)

Причём линия IIзаключена между линиями Iи III. Тогда а₁ < а₂ < а_{3 и} а₁ > а₂ >а_3.

В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 2) уровень является линейной функцией, а значит, при смещении в одном направлении возрастает, а в другом – убывает.

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c₁x₁ + c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

II. Практический раздел

2.1 Решение транспортной задачи

Имеются два склада с сырьём. Ежедневно вывозится с первого склада 60 т сырья, со второго – 80 т. сырьё используется двумя заводами, причём первый завод получает – 50 т, а второй – 90 т. нужно организовать оптимальную (наиболее дешёвую) схему перевозок, если известно, что доставка 1 т сырья с первого склада на первый завод стоит 7 рублей, с первого склада на второй завод – 9 рублей, со второго склада на первый завод – 10 рублей, со второго склада на второй завод – 8 рублей.

Решение:

Обозначим через х₁,х₂ количество сырья, который нужно доставить с первой базы соответственно на первый, второй заводы, а через х₃, хколичество сырья, который нужно доставить со второй базы соответственно на первый, второй заводы. Составим выражения, которые в соответствии с исходными данными должны удовлетворять следующим условиям:

х₁ +х₂ = 60;

х₃ + х₄ = 80;(1)

х₁ +х₃ = 50;

х₂ +х₄ = 90.

Первое и второе уравнения описывают количество сырья, которое необходимо вывезти с первого и второго складов, а третье и четвёртое – сколько нужно завести сырья на первый и второй заводы. К данной системе уравнений нужно добавить систему неравенств:

х_i ≥ 0, где i = 1, . ., 4, (2)

которая означает, что сырьё обратно с заводов на склады не вывозится. Тогда общая стоимость перевозок с учётом приведённых в таблице расценок выразится формулой :

f = 7х₁ + 9х₂ + 10х₃ + 8х _4. (3)

Таким образом, мы пришли к типичной задаче линейного программирования : найти оптимальные значения проектных параметров х_i(i = 1, . ., 4), удовлетворяющим условиям (2), (3) и минимизирующим стоимость перевозок (3).

Из анализа системы уравнений (1) следует, что только первые два уравнения являются независимыми, а последние можно получить из них. Поэтому фактически имеем систему :

х₁ +х₂ = 60;

х₃ + х₄ = 80;(4)

х₃ = 50 - х₁;

х₄ = 90 - х₂.

Поскольку в соответствии с (2) все проектные параметры должны быть неотрицательны, то с учётом (4) получим следующую систему неравенств:

х₁ ≥ 0, х₂ ≥ 0, 50 - х₁ ≥ 0, 90 - х₂ ≥ 0.

Эти неравенства можно записать в более компактном виде :

0≤ х₁ ≤ 50, 0≤ х₂ ≤ 90. (5)

Данная система неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных параметров х₁ и х₂ нужно найти оптимальные, минимизирующие целевую функцию f. Формула (3) для неё с учётом соотношений (4) принимает вид

f = 7х₁ + 9х₂ + 10(50 - х₁)+ 8(90 - х₂);

f = -3х₁ + х₂ + 1220.

Отсюда следует, что стоимость перевозок уменьшается с увеличением значений х₁; поэтому нужно взять его наибольшее допустимое значение. В соответствии с (5) х₁= 50, тогда получим, что х₂ = 60 - х₁ = 10. Тогда оптимальные значения остальных параметров можно найти по формулам (4):

х₃ = 50 - х₁ =50 – 50 = 0, х₄ = 90 - х₂ = 90 – 10 = 80.

В этом случае минимальная общая стоимость перевозок равна :

f = 7*50 + 9*10+ 10*0+ 8*80 = 350 + 90 + 0 + 640 = 1080.

То есть, минимальная общая стоимость перевозок f = 1080.

Покажем на рисунке схему доставки сырья на заводы. (Числа указывают количество сырья в тоннах).

2.2 Решение производственной задачи

Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

Вид сырья	Нормы расхода сырья на одно изделие, кг A B	Общее количество сырья, кг
I	2 4	300
II	4 4	120
III	12	252
Прибыль от реализации одного изделия, ден. ед.	30 40

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х₁ +4х₂) единиц ресурса I, (4х₁ +4х₂) единиц ресурса II, (3х₁ +12х₂) единиц ресурса III. Так кА потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

12х₁ +4х₂ ≤ 300; 3х₁ + х₂ ≤ 75;

4х₁ +4х₂ ≤ 120; или х₁ + х₂ ≤ 30; (6)

3х₁ +12х₂ ≤ 252. х₁ +4х₂ ≤ 84.

По смыслу задачи переменные х₁ ≥ 0, х₂ ≥ 0. (7)

Суммарная прибыль А составит 30х₁ от реализации продукции А и 40х ₂ от реализации продукции В, то есть : F = 30х₁ +40х ₂ (8)

Далее будем решать задачу двумя методами:

1способ – симплексный метод

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком « + », так как все неравенства имеют вид « ≤ ».

Получим систему ограничений в виде :

3₁ +х₂ +х₃ ≤ 75;