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

ГОСУДАРСТВЕННОЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«Приднестровскийгосударственный университет им. Т.Г. Шевченко»

Рыбницкий филиал

Кафедра физики,математики и информатики

Курсовая работа

по дисциплине:«Численные методы»

на тему:

«Использованиелинейного программирования

длярешения задач оптимизации»

Выполнила:

студенткаII курса;

230йгруппы

специальности:«Информатика

сдоп. специальностью английский язык»

НисторА.Г.

Проверила:

преподавательБалан Л.А.

г. Рыбница

2007год

Оглавление

Введение

I.Теоретическийраздел

1.1 Понятие о линейномпрограммировании. Формулировка задачи линейного программирования

1.2 Виды задач линейного программирования

1.3 Методырешения задач линейного программирования

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

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

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

Заключение

 

Введение

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

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

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

Таким образом целью данной курсовой работы является: освоить навыки использования линейного программирования для решения задачоптимизации. Для этого были поставлены следующие задачи :

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

2)Изучить методырешения задач линейного программирования.

3)Решить поставленные задачи,используя рассмотренные методы линейного программирования.

I. Теоретический раздел 1.1 Понятие о линейном программировании. Формулировказадачи линейного программирования

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

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

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

Термин «программирование» нужно понимать в смысле«планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом,одним из основателей линейного программирования, еще до того, как компьютерыбыли использованы для

решения линейных задач оптимизации.

Формулировка задачи линейного программирования

Нужно максимизировать

/>

при условиях

/>

при i = 1, 2, 3,… ., m..

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

Такую задачу называют «основной» или«стандартной» в линейном программировании.

 1.2 Виды задач линейного программированияПоток ипаросочетание

Рассмотрим задачу о максимальном паросочетании: естьнесколько юношей и девушек; для каждой пары известно, любят ли они друг друга.Нужно поженить максимальное число пар. Введем переменные xij — онисоответствуют паре из i-того юноши и j-той девушки.Введем ограничения: xij≥ 0, xij<sub/>≤ 1, />, />, />. Можно показать, что среди оптимальныхрешений этой задачи найдется целочисленное. Переменные, равные 1, будутсоответствовать парам, которые следует поженить.

Вторая важная задача — максимальный поток. Пустьимеется граф (с ориентированными ребрами), в котором для каждого ребра указанаего пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать длякаждого ребра, сколько через него будет протекать жидкости (не больше егопропускной способности) так, чтобы максимизировать суммарный поток из стока висток (жидкость не может появляться или исчезать во всех вершинах, кроме стокаи истока). Возьмем в качестве переменных xi — количество жидкости, протекающихчерез i-тое ребро.Тогда />,/>,где ci — пропускнаяспособность i-того ребра. Этинеравенства надо дополнить равенством количества втекающей и вытекающейжидкости для каждой вершины, кроме стока и истока. В качестве функции f естественновзять разность между количеством вытекающей и втекающей жидкости в истоке.

Обобщение предыдущей задачи — максимальный потокминимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужносреди максимальных потоков выбрать поток с минимальной стоимостью. Эта задачасводится к 2 задачам линейного программирования: сначала нужно решить задачу омаксимальном потоке, а потом добавить к этой задаче ограничение />, где m — величинамаксимального потока, и решить задачу с новой функцией f(x) — стоимостьюпотока.

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

Транспортнаязадача

Имеется некий однородный груз, который нужноперевести с n складов на m заводов. Длякаждого склада i известно,сколько в нем находится груза ai, а для каждого завода известна егопотребность bj в грузе.Стоимость перевозки пропорциональна расстоянию от склада до завода (всерасстояния cij от i-го склада до j-го заводаизвестны). Требуется составить наиболее дешевый план перевозки. Решающимипеременными в данном случае являются xij — количества груза, перевезенногоиз i-го склада на j-й завод.

Ограничениями будут />и

/>.

Целевая функция имеет вид: />, которую надоминимизировать.

Игра снулевой суммой

Есть матрица A размера />. Первый игрок выбираетчисло от 1 до n, второй — от 1до m. Затем онисверяют числа и первый игрок получает aij очков, а второй ( − aij) очков (i — число,выбранное первым игроком, j— вторым). Нужно найти оптимальную стратегию первого игрока. Пусть воптимальной стратегии число iнужно выбирать с вероятностью pi. Тогда оптимальная стратегияявляется решением следующей задачи линейного программирования: />, />, />, />(/>), в которой нужномаксимизировать функцию />. c в оптимальномрешении будет математическим ожиданием выигрыша первого игрока в наихудшемслучае.

 1.3 Методы решения задач линейного программированияСимплекс-метод

Сведём задачу линейногопрограммирования к просмотру крайних точек допустимого множества. Именнонаправленный перебор крайних точек допустимого множества и осуществляется всимплекс-методе, изложенном ниже.

Рассмотрим связь между геометрическим понятиемкрайней точки и его аналитической интерпретацией. Для ограниченного множества />,описанного с помощью системы неравенств

/>

крайними точкамиявляются решения невырожденных подсистем вида:

/>

 (1)

где /> — некотороеподмножество индексов

/>

и

/>

и матрица, составленнаяиз строк-векторов аi,неособенная.

Обозначим единственное решение системы (3) через x. Предположимтеперь, что существуют />и />такие, что для /> />Посколькудля />

 

/>

то, очевидно, />. В силу единственности решения (3) />.

С другой стороны, если /> — крайняя точка, то можнообозначить через />множество равенств

/>

Обозначим через />матрицу,составленную из строк />Если предположить, что />,то существует нетривиальное нуль-пространство

/>2)

 

Выбирая />достаточно малым понорме, можно добиться того, что для />вектор />или />

для />и />

для достаточно малых />.Аналогично можно показать, что при этом и />. Так как /> тополучаем противоречие с определением крайней точки. Для направленного просмотракрайних точек допустимого многогранника применяют симплекс-метод, предложенныйДж. Данцигом и затем усовершенствованный многочисленными математиками. Основнаяидея метода заключается в разбиении множества переменных x= x1,x2,… ., xnнабазисные />и небазисные />. Не умаляя общности, можно считать,что базисные переменные являются первыми в векторе x,т.е. x= (xB,xN).

Система ограничений канонической формы задачилинейного программирования может быть соответственно переписана в виде:

/>(3)

Предположим, что матрица/>имеетполный ранг, т.е. /> - невырожденная. Тогда из равенства (5) следует

/>4)

 

Целевая функция задачиЛПР также может быть разбита на базисную и не базисную части:

/>

Подстановка (6) дает

/>5)

 

Предположим, что мы находимсяв некоторой начальной точке />со значением целевойфункции

/>

Каким образом можноуменьшить далее значение целевой функции? Из соотношения (5) следует, что дляэтого достаточно сделать положительными те компоненты вектора />, которымсоответствуют отрицательные значения координат вектора модифицированныхстоимостей

/>

сохраняя при этомнеотрицательность базисных переменных />.

Увеличение />может быть проделано различнымобразом, и за время существования симплекс-метода были проделаны многочисленныеэксперименты по поиску наиболее эффективных стратегий увеличения />

Здесь будет рассмотрена простейшая:

·                    средикомпонент вектора />находится минимальная;

·                    соответствующаянебазисная переменная />получает максимально возможноеприращение, сохраняющее неотрицательность базисных переменных.

Поскольку приувеличении />-й компоненты вектор />приобретает вид:

/>

где />это />-й орт, а />--степень увеличения этой переменной или шаг алгоритма, то модифицированныйбазисный вектор выражается следующим образом:

/>

где /> — />-й столбец матрицы />Шаг/>определяетсяпри этом из условия:

/>

Максимально возможноезначение />определится при этом как

/>6)

Пусть/>--номер />,на которой достигается минимум (6). Очевидно, что при этом

/>

При этом говорят, что переменная/>выводитсяиз базиса (обращается в нуль), а переменная />вводится в базис. Целевая функцияпри этом уменьшается на величину

/>

Важную роль в теориисимплекс-метода играет условие невырожденности, в котором предполагается полныйранг AB<sub/>и строгая положительность базисного решения β.При этом λ > 0 и δcx< 0, то есть целевая функция уменьшается при переходе к новому базису.

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

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

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

/>

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

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

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

c1x1+c2x2=а (1)

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

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

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

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

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

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

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

F=c1x1+c2x2=а1 (I)

F=c1x1+c2x2= а2 (II)

F=c1x1+c2x2= а3 (III)

Причём линия IIзаключенамежду линиями IиIII. Тогда а1 < а2 <а3 и а1 > а2 ><sub/>а3.

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

/>

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

II. Практический раздел 2.1 Решение транспортной задачи

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

Решение:

Обозначим через х1,<sub/>х2количество сырья, который нужно доставить с первой базы соответственно напервый, второй заводы, а через х3, х<sub/>количество сырья, которыйнужно доставить со второй базы соответственно на первый, второй заводы.Составим выражения, которые в соответствии с исходными данными должныудовлетворять следующим условиям:

/> <td/> />  

х1 +<sub/>х2= 60;

х3 + х4= 80;<sub/>(1)

х1 +<sub/>х3= 50;

х2 +<sub/>х4= 90.

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

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

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

f = 7х1 + 9<sub/>х2+ 10<sub/>х3 + 8х4. (3)<sub/>

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

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

/>х1 +<sub/>х2= 60;

х3 + х4= 80;<sub/>(4)

х3 = 50 — х1;

х4 = 90 — х2.

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

х1 ≥0, х2 ≥ 0, 50 — х1 ≥ 0, 90 — х2 ≥0.

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

0<sub/>≤ х1≤ 50, 0<sub/>≤ х2 ≤ 90. (5)

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

f= 7х1 + 9<sub/>х2 + 10(50 — х1)<sub/>+8(90 — х2);

f= -3х1 + х2 + 1220.

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

х3 = 50 — х1=50 – 50 = 0, х4 = 90 — х2 = 90 – 10 = 80.

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

 

f= 7*50 + 9*10<sub/>+ 10*0<sub/>+ 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

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

Решение.

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

/>/>12х1 +4х2 ≤300; />                            3х1+ х2 ≤ 75; />

4х1 +4х2≤ 120; или                          х1 + х2 ≤30; (6)

3х1 +12х2≤ 252.                               х1 +4х2 ≤84.

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

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

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

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

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

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

/>31 +х2 +<sub/>х3 ≤ 75; />

х1 +х2 +х4 ≤ 30; (9)

х1 + 4х2+ х5 ≤ 84.

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

Iшаг.

Основные переменные: х3,х4, х5.

Не основные переменные:х1, х2…

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

/>х3= 75 — 3х1 — х2;

х4 = 30 х1 — х2; (10)

х5 = 84 — х1 — 4х2.

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

F= 30х1 + 40х2.

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

/>/>х3= 75 — х2 ≥ 0;                            х2 ≤75;

х4 = 30 — х2≥ 0; откуда                х2 ≤ 30;

х5 = 84 — 4х2≥ 0;                          х2 ≤ 84.

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

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

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

IIшаг.

Основные переменные: х2,х3, х4.

Не основные переменные:х1, х…

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

 

/>х2= (84 — х1 — х5)/4;

х3 = 75 — 3х1 — 84/4 + х1/4 + х5/4;

х4 = 30 — х1 — 84/4 + х1 /4 + х5/4;

или

/>х2=21 0,25 х1 — 0,25х5;

х<sub/>=54 — 2,75х1+ 0,25х5;

х<sub/>=9 — 0,75х1+ 0,25х5.

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

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

F = 30х1 +40 (84 — х1 — х5)/4 = 840 + 20х1 — 10х5

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

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

х2 =21 — 0,25х5 ≥ 0;                       х5 ≤ 84;

/>/>х3 =54<sub/>+0,25х5 ≥ 0; откуда          х5 ≤ -216;  (11)

х4 =9 + 0,25х5≥ 0.                        х5 ≤ -36.

Обнаруживаемвозможность дальнейшего увеличения линейной функции за счёт переменной х1,входящей в выражение для Fс положительным коэффициентом. Система уравнений (11) определяет наибольшеевозможное значение для х5:

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

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

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

IIIшаг.

Основные переменные: х1,х2, х3.

Неосновные переменные:х4, х5.

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

/>х1=12<sub/>– 4/3х4 + 1/3х5;

х2 = 18 + 1/3х4 — 1/3х5;

х3 = 21 + 11/3х4 — 11/3х5.

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

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

F= 30(12<sub/>– 4/3х4 + 1/3х5)<sub/>+ 40(18 + 1/3х4 — 1/3х5) = 1080 – 80/3х4 — 10/3х5.

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

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

Прибыль предприятияпринимает максимальное значение 1080 ден. ед. при реализации 12 единицпродукции Р1(Х1=12) и Р2(Х2=18).Дополнительные переменные х3, х4, х5.

показывают разницумежду запасами ресурсов каждого вида и их потреблением, то есть остатки ресурсов.При оптимальном плане производства х4 = х5 = 0, остаткиресурсов S2и S3 равнынулю, а остатки ресурсов S1=21.

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

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

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

линейной функции F= 30х1 + 40х2 →<sub/>maxприследующих ограничениях:

/>3х1+ х2 ≤ 75, (I)

х1 + х2≤ 30, (II) (12)

х1 +4х2≤ 84, (III), х1 ≥0, х2 ≥ 0, х2 ≥ х1

 

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

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

II

 

I

 

 />

С

 

В

 

А

  ОбластьАВС, изображённая на рисунке, является областью допустимых значений функции F.Принимая во внимание систему (12), можно заметить, что самое оптимальноерешение Находится в точке А, находящейся на пересечении прямых IиII, то есть координаты точки Аопределяются решением системы уравнений:

/>/>3х1+ х2 ≤ 75,             х1 = 12,

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

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

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

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

Заключение

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

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

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

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