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

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

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

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

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (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	1                 2	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;

х₁ +х₂ + х₄ ≤ 30; (9)

х₁ + 4х₂ + х₅ ≤ 84.

Для нахождения первоначального базисного решения разобьём переменные на две группы – основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅ отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.

I шаг.

Основные переменные: х₃, х₄, х_5.

Не основные переменные: х₁, х_{2. .}

Выразим основные переменные через не основные :

х₃ = 75 - 3х₁ - х₂ ;

х₄ = 30 х₁ - х₂; (10)

х₅ = 84 - х₁ - 4х_2.

Положив основные переменные равными нулю, то есть х₁ = 0, х₂ = 0, получим базисное решение Х₁ = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:

F = 30х₁ + 40х_{2 .}

При решении Х₁ значение функции равно F(Х₁). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение F с положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х₁ и х₂ входят в выражение для F со знаком «+». Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х₂. Система (10) накладывает ограничения на рост переменной х₂ . Поскольку необходимо сохранять допустимость решений, то есть все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁ = 0 как не основная переменная):

х₃ = 75 - х₂ ≥ 0;                            х₂ ≤ 75;

х₄ = 30 - х₂ ≥ 0; откуда                х₂ ≤ 30;

х₅ = 84 - 4х₂ ≥ 0;                          х₂ ≤ 84.

Каждое уравнение системы, определяет оценочное отношение – границу роста переменной х_2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной свободного члена к коэффициенту при х₂ при условии, что эти числа имеют разные знаки.

Очевидно, что сохранение неотрицательности всех переменных возможно, если не нарушается ни одна из полученных границ. В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂ = min {75, 30, 84/4} = 84/4 = 21. При х₂ = 21 переменная х = 0 и переходит в не основные.

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

II шаг.

Основные переменные: х₂, х₃, х_4.

Не основные переменные: х₁, х_{. .}

Выразим основные переменные через новые не основные, начиная с разрешающего уравнения(его используем для записи выражения для х₂ ) :

 

х₂ = (84 - х₁ - х₅)/4;

х₃ = 75 - 3х ₁ - 84/4 + х₁/4 + х₅/4;

х₄ = 30 - х₁ - 84/4 + х₁ /4 + х₅/4;

или

х₂ =21 0,25 х₁ - 0,25х₅;

х =54 - 2,75х₁ + 0,25х₅;

х =9 - 0,75х₁ + 0,25х₅.

Второе базисное решение Х₂ = (0, 21, 54, 9, 0 ) является допустимым.

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

F = 30х₁ + 40 (84 - х₁ - х₅)/4 = 840 + 20х₁ - 10х₅

Значение линейной функции F₂ = F(X₂) = 840.

Поскольку необходимо сохранять допустимость решений, то должны выполняться следующие неравенства(при этом х₁ = 0 как не основная переменная):

х₂ =21 - 0,25х₅ ≥ 0;                       х₅ ≤ 84;

х₃ =54 + 0,25х₅ ≥ 0; откуда          х₅ ≤ -216;  (11)

х₄ =9 + 0,25х₅ ≥ 0.                        х₅ ≤ -36 .

Обнаруживаем возможность дальнейшего увеличения линейной функции за счёт переменной х_1, входящей в выражение для F с положительным