Линейное программирование. Геометрический метод решений задач

 

 

 

 

Контрольная работа

по дисциплине:

«Исследование операций и методы оптимизации»

на тему:

«Линейное программирование. Геометрический метод решений задач»

Вариант № 4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оглавление

 

 

 

Введение

 

Линейное программирование - это наука о методах исследования и

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

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

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

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

2) Разобрать алгоритм решения ЗЛП геометрическим методом.

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

 

 

I. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

 

1.1 Линейное программирование

 

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

Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.

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

Математическая формулировка задачи линейного программирования

 

 

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

 

 

при условиях  при i = 0, 1, 2, . . . , m .

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

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

Формулировка задачи

 

Дана линейная функция Z=С1х1+С2х2+...+СNxN (1.1)

и система линейных ограничений

 

a11x1 + a22x2 + ... + a1NХN = b1

a21x1 + a22x2 + ... + a2NХN = b2

. . . . . . . . . . . . . . .

ai1x1 + ai2x2 + ... + aiNХN = bi (1.2) . . . . . . . . . . . . . . .

aM1x1 + aM2x2 + ... + aMNХN = bM

xj 0 (j = 1, 2, ... ,n) (1.3)

 

где аij, bj и Сj - заданные постоянные величины.

Найти такие неотрицательные значения х1, х2, ..., хn, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение.

Общая задача имеет несколько форм записи.

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 + А2x2 + ... + АNxN = Ао, X0 (1.4)

где С = (с1, с2, ..., сN); Х = (х1, х2, ..., хN); СХ - скалярное произведение; векторы A1 = A2 = ,..., AN состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0Х0, где С = (с1, с2, ..., сN) - матрица-cтрока; А = (аij) - матрица системы; Х =(xij)- матрица-столбец, А0 = (аi) матрица-столбец

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = Сjхj при ограничениях

Определение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2, ..., хN), удовлетворяющий условиям (1.2) и (1.3).

Определение 2. План Х = (х1, х2, ..., хN) называется опорным, если векторы А (i = 1, 2, ..., N), входящие в разложение (1.4) с положительными коэффициентами х , являются линейно независимыми.

Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

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

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

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

Геометрический метод решений задач

Рассмотрим задачу ЛП в стандартной форме записи:

 

max f(X) = с1х1 + с2х2 + ... + спхп (*)

 

при ограничениях

 

а11х1 + а12х2 + … + а1nхn ≤ b1

а21х1 + а22х2 + … + а2nхn ≤ b2

……………………………..

аm1х1 + аm2х2 + … + аmnхn ≤ bm

хj ≥ 0, j = 1, 2, …, n.

 

Рассмотрим эту задачу на плоскости, т.е. при п = 2. Пусть система неравенств (**), (***) совместна (имеет хотя бы одно решение):

 

а11х1 + а12х2 ≤ b1

а21х1 + а22х2 ≤ b2

…………..

аm1х1 + аm2х2 ≤ bm

x1 ≥ 0; х2 ≥ 0.

 

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой аi1х1 + аi2х2 ≤ bi i = 1, m. Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми x1 = 0; х2 = 0.. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область.

Если в системе ограничений (**) - (***) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого аi1х1 + аi2х2 + аi3х1 ≤ bi, а условия неотрицательности — полупространства с граничными плоскостями соответственно xi = 0 (i = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений.

Пусть в системе (**) - (***) п > 3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью аi1х1 + аi2х2 + … + аinхn ≤ bi i = 1, т , а условия неотрицательности — полупространства с граничными гиперплоскостями xj = 0, j = 1, n.

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

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

 

 

 

II. ПРАКТИЧЕСКИЙ РАЗДЕЛ

 

Задача № 1

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

Вид сырья	Нормы расхода сырья (т) на 1 т карамели			Общее количество сырья (т)
	А	В	С
Сахарный песок	0.8	0.5	0.6	800
Патока	0.4	0.4	0.3	600
Фруктовое пюре	-	0.1	0.1	120
Прибыль от реализ. 1 т продукции (ден. ед.)	108	112	126

 

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

Решение. Симплекс-метод.

F=108x1+112x2+126x3=max

Система ограничений

0,8х1+0,8х2+0,6х3≤800

0,4х1+0,4х2+0,3х3≤600

0,1х2+0,13≤120

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

Решим систему уравнений относительно базисных переменных: x4, x5, x6

 

0,8х1+0,8х2+0,6х3+1х4 =800

0,4х1+0,4х2+0,3х3+1х5 =600 

0,1х2+0,13+1х6 =120

 

F=108x1+112x2+126x3+0х4+0х5+0х6

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	800	0.8	0.5	0.6	1	0	0
0	x5	600	0.4	0.4	0.3	0	1	0
0	x6	120	0	0.1	0.1	0	0	1
		0	-108	-112	-126	0	0	0

 

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	800	0,8	0,5	0,6	1	0	0
0	x5	600	0,4	0,4	0,3	0	1	0
0	x6	120	0	0,1	0,1	0	0	1
		0	-108	-112	-126	0	0	0

 

Шаг 2: элементы столбца х0 делят на соответствующие коэффициенты ключевого столбца (только для положительных элементов ключевого столбца)

800/0,6=1333,3     600/0,3=2000       120/0,1=1200

Строка с наименьшим соотношением принимается за ключевую.

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
0	x4	800	0,8	0,5	0,6	1	0	0
0	x5	600	0,4	0,4	0,3	0	1	0
0	x6	120	0	0,1	0,1	0	0	1
		0	-108	-112	-126	0	0	0

 

Ключевой элемент 0,1

Формируем следующую часть симплексной таблицы.

Вместо переменной x6 в план 1 войдет переменная x3

Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=0.1

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x3  плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x3  и столбец x3 .

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

Шаг 3: Элементы таблицы преобразуются и записывают в новую таблицу

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
126	x6	1200	0	1	1	0	0	10

 

Остальные элементы преобразуются по следующему правилу:

– для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке – элемент ключевого столбца;

– соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключевой элемент;

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

Столбец х0

                  

 

x0

80

240

1200

151200

 

После преобразований получаем новую таблицу:

Итерация 1

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

Включение на первой итерации в план неизвестной х3 обеспечит сумму прибыли 151200 руб.

Шаг 4: Решение задачи продолжается, так как в целевой строке так находятся отрицательные коэффициенты.

Наибольший по модулю элемент -108. Значит ключевой столбец х1.

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.8) и находится на пересечении ведущего столбца и ведущей строки.

 

 

 

Формируем следующую часть симплексной таблицы.

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	x6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

Определяем ключевую строку:

80/0,8=100            240/0,4=600         

Минимальное значение в х4

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 2 войдет переменная x1

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=0.8

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x1  плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1  и столбец x1 .

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
0	x4	80	0.8	-0.1	0	1	0	-6
0	x5	240	0.4	0.1	0	0	1	-3
126	x3	1200	0	1	1	0	0	10
		151200	-108	14	0	0	0	1260

 

После преобразований получаем новую таблицу:

 

 

 

 

Итерация 2

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
108	x1	100	1	-0.13	0	1.25	0	-7.5
0	x5	200	0	0.15	0	-0.5	1	0
126	x3	1200	0	1	1	0	0	10
		162000	0	0.5	0	135	0	450

 

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

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

cj прибыль в план	p0	x0	108	112	126	0	0	0
			x1	x2	x3	x4	x5	X6
108	x1	100	1	-0.13	0	1.25	0	-7.5
0	x5	200	0	0.15	0	-0.5	1	0
126	x3	1200	0	1	1	0	0	10
		162000	0	0.5	0	135	0	450

Оптимальный план можно записать так:

x1 = 100

x3 = 1200

F(X) = 108 • 100 + 126 • 1200 = 162000

Далее решим задачу с помощью MS Excel.

Отведем ячейки С3, С4 и С5 под значения переменных Х1, Х2, и Х3(рис. 1).

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

В ячейку С6 ведем функцию цели: =СУММ(С3:С5), в ячейки А10 : С10 введем левые части ограничений:

=0,8*В3+0,5*В4+0,6*В5

=0,4*В3+0,4*В4+0,3*В5

=0,1*В4+0,1*В5,

а в ячейки С3, С4 и С5 введем левые части ограничений (рис.1.):

=108*В3

=112*В4

=126*В5

Выберем команды Сервис/Поиск решения и заполним открывшееся диалоговое окно Поиск решения как показано на рис 2.

Для ввода ограничений нажмем кнопку Добавить.

 

Рис. 2. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике

В диалоговом окне Параметры поиска решения установим флажок Линейная модель (Рис.3.).

Рис 3. Параметры поиска решения

После нажатия кнопки Выполнить открывается окно Результаты поиска решения, которое сообщает, что решение найдено (рис. 4).

Рис. 4. Результаты поиска решения

Результаты расчета задачи представлены на рис. 5,  из которого видно, что максимальную прибыль в количестве 162000 руб. можно получить производя сырья А в количестве 100 т и сырья С в количестве 1200 т и не произведя при этом сырья В.

Рис. 5. Результаты расчета

 

 

 

 

 

Заключение

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

 

1. Ашманов С.А. Линейное программирование. – М.: Наука, 2008.
2. Коротков М., Гаврилов М. «Основы линейного программирования», 2007 г..
3. Лищенко «Линейное и нелинейное программирование», М. 2006 г.
4. Филькин Г.В., «Линейное программирование» (лекции), Шахты, 2007 г.

Интернет – ресурсы

5. http://ru.wikipedia.org/