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

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

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

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

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

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

на тему:

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

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

Выполнила:

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

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

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

2)

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

для и