Системы линейных неравенств

Далее рассмотрим пример построения фундаментального набора решений системы линейных неравенств по данному алгоритму, состоящей из 5 неравенств и 4 неизвестных. Пусть дана следующая система линейных неравенств:1) К тривиальному неравенству следующего вида:Присоединим неравенство:На этом шаге базис U (С)составляют четыре вектора:Базис U( составят векторы:Система V(C) пуста. Так как, система V( состоит из одного вектора. Данный вектор, исходя из выполнения следующего неравенства:Выглядит так:2) Далее к системе добавляем ещё одно неравенство:Базис U (C) здесь составляют найденные векторы . Базис U ( здесь составят векторы:Система V(C) состоит из найденного вектора , система V(из векторов:3)Далее к системе добавляется неравенство:Базис U( здесь состоит из одного вектора:Система V( здесь состоит из трёх векторов:4)Далее к системе присоединяем неравенство:Базис U( здесь пуст, так как:Так как:Вектор:Можно включить в систему V(. Вместе с ним в эту систему войдут векторы:Все найденные векторы удовлетворяют неравенству:Это означает, что его можно удалить из взятой системы, не нарушая множества её решений.На этом процесс решения останавливается. Введя обозначения:Можно фундаментальный набор решений данной системы линейных неравенств записать в следующем виде:В данной формуле Глава 3. Решение произвольной системы линейных неравенств.Если S1 и S2 множества n-мерных векторов, то их суммой называется множество всех векторов вида α+β, где αпринадлежит множеству S1, β принадлежит множеству S2. Теорема. Множество S решений системы неравенств:Совпадает с суммой множеств S1 и S2, где S1 – множество решений следующей системы уравнений:S2 – это множество решений следующей системы неравенств:Теорема. Произвольное решение системы линейных однородных неравенствВыглядит так:В данной формуле:Алгоритм построения решения произвольной системы неравенств.1.Найти базис системы столбцов и ранг матрицы системы неравенств.2.Найти фундаментальное решение системы неравенств по соответствующим формулам.Рассмотрим примеры:Пусть требуется найти все решения следующей системы линейных неравенств:Сначала запишем вспомогательную однородную систему линейных неравенств:Множество фундаментального набора решений этой системы описывается следующими формулами:В данных формулах k-это любые неотрицательные числа. Так как нам нужны решения, в которых t>0, считаем, что хотя бы одно из чиселk5, k6положительно.Глава 4. Практическое применение систем линейных неравенств.При нахождении решений задач линейного программирования часто всё сводится к решению систем линейных неравенств. Покажем это на примерах двух различных задач линейного программирования.Пример 1 (Задача о диете). Из имеющихся в распоряжении видов пищи нужно составить такую диету, которая, с одной стороны, обеспечивала бы удовлетворение минимальных потребностей организма в питательных веществах (белках, жирах, углеводах, витаминах и т.д.) и вместе с тем требовала бы наименьших затрат.Рассмотрим простую математическую модель данной задачи. Пусть имеются два вида продуктов П1 и П2, содержащих питательные вещества A,B,C. Известно, сколько питательного вещества того или иного вида содержится в 1 кг пищи продуктов, эти сведения укажем в таблице:ABCв 1 кг П1a1b1c1в 1 кг П2a2b2c2Кроме этих данных также известны: a,b,c-ежесуточные потребности организма в A,B,C (соответственно) и стоимости 1 кг указанных продуктов.Требуется рассчитать количество x1 и x2 каждого из продуктов, так, чтобы обеспечить необходимое количество питательных веществ, при минимальных затратах на пищу. Очевидно, что функция стоимости, которую нужно будет минимизировать, выглядит так:Получаем, что решение задачи сводится к решению следующей системы неравенств:А также к минимизации следующей функции стоимости:Требуется, среди неотрицательных решений системы линейных неравенств выбрать такое, при котором функция S достигает наименьшего значения. Пример 2. На предприятии, выпускающем изделия двух типов, производственная мощность цеха сборки составляет 100 изделий типа A или 300 изделий типа B в сутки; в то же время отдел технического контроля в состоянии проверить не более 150 изделий (любого типа) в сутки. Известно далее, что изделие типа A стоит вдвое дороже, чем изделие типа B. Требуется при этих условиях найти такой план выпуска продукции, который обеспечивал бы предприятию наибольшую прибыль. Искомый план выпуска продукции задаётся с помощью двух неотрицательных целых чисел x,y, при этом:x- это количество изделий типа A,y- количество изделий типа B.Данный план выпуска должен удовлетворять следующим условиям:При этом:Значит, чтобы решить данную задачу, нужно найти решение следующей системы линейных неравенств:А также найти максимум функции:Чтобы найти решение данной задачи, нужно сначала решить систему линейных неравенств, а затем из полученных решений, выбрать те, которые максимизируют указанную функцию.ЗаключениеВ данной работе описано построение и решение фундаментального набора решений для систем, состоящих из одного или нескольких уравнений или неравенств. Доказано существование фундаментального набора решений систем линейных неравенств и показан способ его построения. Рассмотрены системы однородных и произвольных линейных уравнений и неравенств.Таким образом, в данной курсовой работе развита теория системы линейных уравнений и неравенств.СПИСОК ЛИТЕРАТУРЫ1.А.С. Солодовников. Системы линейных неравенств. М.: Наука, 1977 г.2. Черников С.Н. Линейные неравенства. – М., 1968.