Векторное пространство Решение задач линейного программирования графическим способом (стр. 2 из 5)

Предположим, что для элемента

имеются два противоположных ему элемента и . Тогда

С другой стороны,

Сравнивая результаты, имеем

[3, с.103].

3) Произведение числа 0 на любой элемент х есть нулевой элемент.

Действительно,

[3, с.104].

4)

.

С линейными пространствами в первую очередь связано понятие линейного подпространства – такое множество векторов из L, которое само является линейным пространством над полем P. Чтобы подмножество было подпространством, необходимо и достаточно, чтобы выполнялись 2 условия:

1.

;

2.

.

Свойства подпространств:

· Пересечение любого семейства подпространств — снова подпространство;

· Сумма конечного семейства подпространств — снова подпространство.

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

Векторное пространство, в котором определена норма, называется нормированным векторным пространством или просто нормированным пространством.

Топологическое линейное пространство – линейное пространство наделённое топологией, относительно которой операции сложения и умножения на число непрерывны.

Действительным евклидовым пространством или просто евклидовым пространством называется действительное линейное пространство, на элементах которого определено скалярное произведение.

Гильбертово пространство — обобщение евклидова пространства, допускающее бесконечную размерность.

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

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

L однозначно определен третий элемент z L, называемый их суммой и обозначаемый x + y , и для каждого числа и любого элемента x L определен элемент x L так, что введенные операции сложения и умножения на число удовлетворяют условиям существования линейного пространства. Часто элементы абстрактных линейных пространств называют векторами, а само пространство векторным. Так, линейные пространства могут быть образованы не только лишь арифметическими векторами ─ эти пространства могут быть построены из объектов самой различной природы, что отличает математику от других наук.

2 Задача линейного программирования и этапы ее решения графическим методом

Векторные пространства широко используются не только в линейной алгебре. На множествах n-мерного векторного пространства решением экстремальных задач, задаваемых системами линейных уравнений и неравенств, занимается такая математическая дисциплина, как линейное программирование. Методы и модели линейного программирования широко применяются при оптимизации процессов в экономике. Это, например: задача об оптимальном использовании ресурсов при производственном планировании, задача о смесях (планирование состава продукции), задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке"), транспортные задачи (анализ размещения предприятия, перемещение грузов).

Первая работа, в которой были разработаны методы линейного программирования, была написана в 1939 г. советским математиком-экономистом Л.В. Канторовичем и носила название «Математические методы организации и планирования производства». Именно ее появление открыло новый этап в применении математики в экономике. Через 10 лет американским математиком Дж. Данцингом был разработан важный и очень эффективный метод решения подобного типа задач – симплекс-метод. Сам же термин «линейное программирование» впервые появился в 1951 г. в работах Дж. Данцига и Т. Купманса.

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

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

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

· целевая функция:

= c1x1 + c2x2 + ... + cnxn → max(min);(1.1)

· ограничения:

a11x1 + a12x2 + ... + a1nxn ≤ b1,a21x1 + a22x2 + ... + a2nxn ≤ b2,

...

am1x1 + am2x2 + ... + amnxn ≤ bm;(1.2)

· требование неотрицательности:

xj ≥ 0,

(1.3)

При этом aij, bi, cj (

, ) -заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор

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

Каноническая задача линейного программирования:

= c1x1 + c2x2 + ... + cnxn → max(min);

a11x1 + a12x2 + ... + a1nxn = b1,

a21x1 + a22x2 + ... + a2nxn = b2,

...

am1x1 + am2x2 + ... + amnxn = bm;

xj ≥ 0,

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

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

1. Задача об оптимальном использовании ресурсов при производственномпланировании.

Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (

, ).Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль преприятия была бы наибольшей.

Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?