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

 

 

 

 

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

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

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

на тему:

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

Вариант № 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