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

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

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

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

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

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

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

на тему:

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

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

Выполнила:

студентка 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..

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

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

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

Поток и паросочетание

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

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

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

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

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

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

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

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

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

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

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

Симплекс-метод

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

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

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

(1)

где - некоторое подмножество индексов

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

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

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

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

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

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

для и

для достаточно малых . Аналогично можно показать, что при этом и . Так как то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x_>1>, x_>2>, . . ., x_>n> на базисные и небазисные . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (x^B, x^N ).

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

c_>1>x_>1>+c_>2>x_>2>= а (1)

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

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

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

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

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

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

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

F=c_>1>x_>1>+ c_>2>x_>2>= а_>1>(I)

F=c_>1>x_>1>+ c_>2>x_>2> = а_>2> (II)

F=c_>1>x_>1>+ c_>2>x_>2> = а_>3>(III)

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

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

0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010096f60000000001000000180300000000000018030000010000006c0000000000000000000000350000004a00000000000000000000003e0100003e01000020454d46000001001803000012000000020000000000000000000000000000007f120000771a0000c80000001f010000000000000000000000000000000f030058600400160000000c000000180000000a00000010000000000000000000000009000000100000004b0000004b000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c00690062007200690000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110040ae110010000000a4b1110024af1100524f6032a4b111009cae1100100000000cb0110088b11100244f6032a4b111009cae11002000000049642f319cae1100a4b1110020000000ffffffff0c37e500d0642f31ffffffffffff0180ffff01800fff0180ffffffff000001000008000000080000e4ba120001000000000000005802000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c00690062007200000000000000000064af1100dee32e31e88d0832c4b21100d0ae11009c38273108000000010000000caf11000caf1100e87825310800000034af11000c37e5006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000004a00000001000000e7298740a48e87400000000057000000010000004c0000000400000000000000000000004b0000004b00000050000000200035003600000046000000280000001c0000004744494302000000ffffffffffffffff4c0000004c000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c020b000b00040000002e0118001c000000fb020200010000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f3ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000000b000b0020760800040000002d010000040000002d010000030000000000

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

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

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

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

Решение:

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

х_>1> +_>>х_>2>= 60;

х_>3>+ х_>4>= 80;_>>(1)

х_>1>+_>>х_>3>= 50;

х_>2>+_>>х_>4>= 90.

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

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

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

f = 7х_>1> + 9_>>х_>2>+ 10_>>х_>3>+ 8х_{> 4.}>(3)_>>

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

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

х_>1> +_>>х_>2>= 60;

х_>3>+ х_>4>= 80;_>>(4)

х_>3>= 50 - х_>1>;

х_>4>= 90 - х_>2>.

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

х_>1>≥ 0, х_>2>≥ 0, 50 - х_>1>≥ 0, 90 - х_>2>≥ 0.

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

0_>>≤ х_>1>≤ 50, 0_>>≤ х_>2>≤ 90. (5)

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

f = 7х_>1> + 9_>>х_>2>+ 10(50 - х_>1>)_>>+ 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_>>+ 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

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

Решение.

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

12х_>1> +4х_>2>≤ 300; 0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010096f60000000001000000180300000000000018030000010000006c0000000000000000000000350000004a00000000000000000000003e0100003e01000020454d46000001001803000012000000020000000000000000000000000000007f120000771a0000c80000001f010000000000000000000000000000000f030058600400160000000c000000180000000a00000010000000000000000000000009000000100000004b0000004b000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c00690062007200690000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110040ae110010000000a4b1110024af1100524f6032a4b111009cae1100100000000cb0110088b11100244f6032a4b111009cae11002000000049642f319cae1100a4b1110020000000ffffffff0c37e500d0642f31ffffffffffff0180ffff01800fff0180ffffffff000001000008000000080000e4ba120001000000000000005802000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c00690062007200000000000000000064af1100dee32e31e88d0832c4b21100d0ae11009c38273108000000010000000caf11000caf1100e87825310800000034af11000c37e5006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000004a00000001000000e7298740a48e87400000000057000000010000004c0000000400000000000000000000004b0000004b00000050000000200035003600000046000000280000001c0000004744494302000000ffffffffffffffff4c0000004c000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c020b000b00040000002e0118001c000000fb020200010000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f3ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000000b000b0020760800040000002d010000040000002d010000030000000000 3х_>1> + х_>2>≤ 75; 0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010096f60000000001000000180300000000000018030000010000006c0000000000000000000000350000004a00000000000000000000003e0100003e01000020454d46000001001803000012000000020000000000000000000000000000007f120000771a0000c80000001f010000000000000000000000000000000f030058600400160000000c000000180000000a00000010000000000000000000000009000000100000004b0000004b000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c00690062007200690000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110040ae110010000000a4b1110024af1100524f6032a4b111009cae1100100000000cb0110088b11100244f6032a4b111009cae11002000000049642f319cae1100a4b1110020000000ffffffff0c37e500d0642f31ffffffffffff0180ffff01800fff0180ffffffff000001000008000000080000e4ba120001000000000000005802000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c00690062007200000000000000000064af1100dee32e31e88d0832c4b21100d0ae11009c38273108000000010000000caf11000caf1100e87825310800000034af11000c37e5006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000004a00000001000000e7298740a48e87400000000057000000010000004c0000000400000000000000000000004b0000004b00000050000000200035003600000046000000280000001c0000004744494302000000ffffffffffffffff4c0000004c000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c020b000b00040000002e0118001c000000fb020200010000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f3ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000000b000b0020760800040000002d010000040000002d010000030000000000

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способ – симплексный метод

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

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

3_>1> +х_>2>+_>>х_>3> ≤ 75; 0100090000032a0200000200a20100000000a201000026060f003a03574d4643010000000000010096f60000000001000000180300000000000018030000010000006c0000000000000000000000350000004a00000000000000000000003e0100003e01000020454d46000001001803000012000000020000000000000000000000000000007f120000771a0000c80000001f010000000000000000000000000000000f030058600400160000000c000000180000000a00000010000000000000000000000009000000100000004b0000004b000000250000000c0000000e000080250000000c0000000e000080120000000c00000001000000520000007001000001000000a4ffffff00000000000000000000000090010000000000cc04400022430061006c00690062007200690000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110040ae110010000000a4b1110024af1100524f6032a4b111009cae1100100000000cb0110088b11100244f6032a4b111009cae11002000000049642f319cae1100a4b1110020000000ffffffff0c37e500d0642f31ffffffffffff0180ffff01800fff0180ffffffff000001000008000000080000e4ba120001000000000000005802000025000000372e9001cc00020f0502020204030204ef0200a07b20004000000000000000009f00000000000000430061006c00690062007200000000000000000064af1100dee32e31e88d0832c4b21100d0ae11009c38273108000000010000000caf11000caf1100e87825310800000034af11000c37e5006476000800000000250000000c00000001000000250000000c00000001000000250000000c00000001000000180000000c0000000000000254000000540000000000000000000000350000004a00000001000000e7298740a48e87400000000057000000010000004c0000000400000000000000000000004b0000004b00000050000000200035003600000046000000280000001c0000004744494302000000ffffffffffffffff4c0000004c000000000000004600000014000000080000004744494303000000250000000c0000000e000080250000000c0000000e0000800e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c020b000b00040000002e0118001c000000fb020200010000000000bc02000000cc0102022253797374656d0000000000000000000000000000000000000000000000000000040000002d010000040000002d01000004000000020101001c000000fb02f3ff0000000000009001000000cc0440002243616c6962726900000000000000000000000000000000000000000000000000040000002d010100040000002d010100040000002d010100050000000902000000020d000000320a0d00000001000400000000000b000b0020760800040000002d010000040000002d010000030000000000

х_>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>;

х_>>=54 - 2,75х_>1>+ 0,25х_>5>;

х_>>=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>

Значение линейной функции F_>2> = F(X_>2>) = 840.

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

х_>2>=21 - 0,25х_>5>≥ 0; х_>5>≤ 84;

х_>3>=54_>>+ 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_>>– 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_>>– 4/3х_>4> + 1/3х_>5>)_>>+ 40(18 + 1/3х_>4>- 1/3х_>5>) = 1080 – 80/3х_>4>- 10/3х_>5.>

Значение линейной функции F_>3> = F(X_>3>) = 1080.

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

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

показывают разницу между запасами ресурсов каждого вида и их потреблением, то есть остатки ресурсов. При оптимальном плане производства х_{> 4}> = х_{> 5}> = 0, остатки ресурсов S_>2> и S_>3>равны нулю, а остатки ресурсов S_>1>= 21.

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

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

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

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

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

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

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

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

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

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

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

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

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

F_>max>= 30*12 + 40*18 = 1080.

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

Заключение

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

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

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

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