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 Решение производственной задачи

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

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

Решение.

Обозначим через х₁ и х₂ количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (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 с положительным коэффициентом. Система уравнений (11) определяет наибольшее возможное значение для х₅ :

Х₅ = min {84, -216,-36} = -36 .

При х₅ = -36 х₄ = 0 переходит в неосновные переменные.

Разрешающим будет третье уравнение.

III шаг.

Основные переменные : х₁ , х₂ , х_3.

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

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

х₁ = 12– 4/3х₄ + 1/3х₅ ;

х₂ = 18 + 1/3х₄ - 1/3х₅ ;

х₃ = 21 + 11/3х₄ - 11/3х_5.

Третье базисное решение Х₃ = (12, 18, 21, 0, 0) является допустимым.

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

F = 30(12– 4/3х₄ + 1/3х₅ )+ 40(18 + 1/3х₄ - 1/3х₅ ) = 1080 – 80/3х₄ - 10/3х_5.

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

Это выражение не содержит положительных коэффициентов при не основных переменных, поэтому значение F₃ = F(X₃ ) = 1080 максимальное. Функцию F невозможно ещё увеличить, переходя к другому допустимому базисному решению, то есть решение X₃ – оптимальное. Вспоминая экономический смысл всех переменных можно сделать выводы.

Прибыль предприятия принимает максимальное значение 1080 ден. ед. при реализации 12 единиц продукции Р₁ (Х₁ =12) и Р₂ (Х ₂ =18). Дополнительные переменные х ₃ , х ₄ , х _5.

показывают разницу между запасами ресурсов каждого вида и их потреблением, то есть остатки ресурсов. При оптимальном плане производства х ₄ = х ₅ = 0, остатки ресурсов S₂ и S₃ равны нулю, а остатки ресурсов S₁ = 21.

Ответ: максимальная прибыль от реализации продукции равна 1080 ден. ед.

2 способ – геометрический мето д

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

линейной функции F = 30х₁ + 40х₂ →maxпри следующих ограничениях:

3х₁ + х₂ ≤ 75, (I)

х₁ + х₂ ≤ 30, (II) (12)

х₁ +4х₂ ≤ 84, (III), х₁ ≥ 0, х₂ ≥ 0, х₂ ≥ х₁

по смыслу задачи.

Изобразим многоугольник решений данной задачи.

3х₁ + х₂ ≤ 75, х₁ = 12,

х₁ + х₂ ≤ 30, или х₂ = 18., т. е. А(12, 18)

максимальное значение линейной функции равно :

F_max = 30*12 + 40*18 = 1080.

Итак, F_max = 1080 при оптимальном решении х₁ = 12, х₂ = 18, т. е. максимальная прибыль в 1080 ден. ед. может быть достигнута при производстве 12 единиц продукции А и 18 единиц продукции В. Ответ: F_max = 1080.

З аключение

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

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

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

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