Линейное программирование: решение задач графическим способом - реферат

Министерство Образования Русской Федерации

Тюменский Муниципальный Нефтегазовый Институт филиал в городке Ишиме

Курсовая работа по программированию на тему:

Линейное программирование: решение задач графическим способом

Выполнил:
студент 1 курса

АиУ-02. Афанасьев В. Ю.

Проверил:
Андреенко О.В.

Дата сдачи « » июня 2003г.

Оценка_______________

Подпись______________

Ишим 2003

Содержание:

Введение 3

Гл 1Математические базы решения задачки линейного программирования Линейное программирование: решение задач графическим способом - реферат графическим способом_ 4

1.1 Математический аппарат 4

1.2 Геометрическая интерпретация задачки линейного программирования. 5

1.3 Этапы решения графического способа задач линейного программирования 7

Гл 2 Решение задач линейного программирования графическим методом на ЭВМ 15

2.1 Описание работы программы_ 15

2.1 Текст программы_ 20

Заключение 29

Литература_ 31

Рецензия_ 33


Введение

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

Вправду, путь нужно изучить на Линейное программирование: решение задач графическим способом - реферат экстремум линейную функцию

Z = С1 х1 +С2 х2 +... +СN xN

при линейных ограничениях

a11 x1 + a22 x2 + ... + a1N ХN = b1

a21 x1 + a22 x2 + ... + a2N ХN = b2

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

aМ 1 x1 + aМ 2 x2 + ... + aМ N ХN = bМ

Потому что Z - линейная функция, то Z = Сj , (j = 1, 2, ..., n), то все Линейное программирование: решение задач графическим способом - реферат коэффициенты линейной функции не могут быть равны нулю, как следует, снутри области, образованной системой ограничений, экстремальные точки не есть. Они могут быть на границе области, но изучить точки границы нереально, так как личные производные являются константами.

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

Гл 1Математические базы решения задачки линейного программирования графическим методом

1.1 Математический аппарат

Для осознания всего предстоящего полезно знать и представлять для Линейное программирование: решение задач графическим способом - реферат себя геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n =2 и n =3.

Более наглядна эта интерпретация для варианта n =2, т.е. для варианта 2-ух переменных и . Пусть нам задана задачка линейного программирования в стандартной форме

(1.19)

Возьмём на плоскости декартову систему координат и каждой паре чисел поставим в соответствие точку на Линейное программирование: решение задач графическим способом - реферат этой плоскости.

Обратим сначала внимание на ограничения и . Они из всей плоскости вырезают только её первую четверть (см. рис. 1). Разглядим сейчас, какие области соответствуют неравенствам вида . Поначалу разглядим область, подобающую равенству . Как Вы, естественно, понимаете, это ровная линия. Строить её проще всего по двум точкам.

Пусть . Если Линейное программирование: решение задач графическим способом - реферат взять , то получится . Если взять , то получится . Таким макаром, на прямой лежат две точки и . Далее через эти две точки можно по линейке провести прямую линию (смотри набросок 2).

Если же b=0, то на прямой лежит точка (0,0). Чтоб отыскать другую точку, можно взять хоть какое хорошее от нуля значение и вычислить соответственное ему Линейное программирование: решение задач графическим способом - реферат значение .

Эта построенная ровная разбивает всю плоскость на две полуплоскости. В одной её части , а в другой напротив . Выяснить, в какой полуплоскости какой символ имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, к примеру, начало координат, т.е. точка (0,0).

1.2 Геометрическая интерпретация задачки линейного Линейное программирование: решение задач графическим способом - реферат программирования.

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

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

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

(**)

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

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

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

(***)

а m 1 х1 + а m 2 х2 + … + а mn х n ≤ bm

х j ≥ 0, j Линейное программирование: решение задач графическим способом - реферат = 1, 2, …, n .

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

а11 х1 + а12 х2 ≤ b 1

а21 х1 + а22 х2 ≤ b 2

…………..

а m 1 х1 + а m 2 х2 ≤ bm

x 1 ≥ 0; х2 ≥ 0.

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

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

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

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

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

1.3 Этапы решения графического способа задач линейного программирования

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

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

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

Шаг 1.

Поначалу на координатной плоскости x 1 Ox 2 строится допустимая многоугольная область (область допустимых решений, область определения), соответственная ограничениям:

(1.31)

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

1. Основной случай - получающаяся Линейное программирование: решение задач графическим способом - реферат область имеет вид ограниченного выпуклого многоугольника (рис. 3а)).

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

Рис. 3

б)

а)

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

Разглядим теорию на определенном примере:

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

(1.32)

Решение:

1. Разглядим прямую . При , а при . Таким макаром, эта ровная проходит через точки (0,1) и (-1,0). Беря получим, что -0+0<1 и потому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.а Линейное программирование: решение задач графическим способом - реферат.

2. Разглядим прямую . При , а при . Таким макаром, эта ровная проходит через точки (0, -1/2) и (1,0). потому что (4.б).

3. В конце концов, разгляди м прямую . Она проходит через точки (0,3) и (3,0) и потому что 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в.

Сводя все вкупе и добавляя условия получим набросок Линейное программирование: решение задач графическим способом - реферат 5, где выделена область, в какой производятся сразу все ограничения (1.32). Направьте внимание на то, что получившаяся область имеет вид выпуклого многоугольника .

Шаг 2.

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

Рис. 6

Разглядим прямую . Будем наращивать L. Что будет происходить с нашей прямой Линейное программирование: решение задач графическим способом - реферат?

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

А сейчас сведем всё вкупе. Итак, нужно решить задачку

Oграничения задачки вырезают на плоскости некий многоугольник. Пусть при неком L ровная пересекает Линейное программирование: решение задач графическим способом - реферат допустимую область. Это скрещение дает какие-то значения переменных , которые являются планами.

Шаг 3

Увеличивая L мы начнем двигать нашу прямую и её скрещение с допустимой областью будет изменяться (см. рис. 7). В конце концов эта ровная выйдет награницу допустимой области - обычно, это будет одна из вершин многоугольника . Предстоящее повышение L приведёт Линейное программирование: решение задач графическим способом - реферат к тому, что скрещение

Рис. 7

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

1.4 Примеры задач, решаемых графическим способом.

Пример:

Решить задачку

(1.41)

Решение

Допустимую Линейное программирование: решение задач графическим способом - реферат область мы уже строили - она изображена на рис. 5.

Повторим снова этот набросок, оставив только допустимую область и
нарисовав дополнительно прямые (см. рис. 8).

Рис. 8

Пусть, к примеру, L =2. Тогда ровная проходит через точки (2,0) и (0,1) и изображена на рис. 8. Будем сейчас наращивать L . Тогда ровная начнёт двигаться параллельно самой для себя в направлении Линейное программирование: решение задач графическим способом - реферат, обозначенном стрелкой. Просто додуматься, что наибольшее значение L получится тогда, когда ровная пройдет через верхушку многоугольника, обозначенную на рисунке, и предстоящее повышение L приведет к тому, что ровная выйдет за границы многоугольника и её скрещение с допустимой областью будет пустым.

Выделенная верхушка лежит на скрещении прямых

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

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

Рис. 9

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

Подводя результат этим примерам, можно сконструировать последующие положения:

1. допустимая область - это выпуклый многоугольник;

2. оптимум достигается в верхушке допустимой области (если допустимая область ограничена и не пуста);

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

Гл 2 Решение задач линейного программирования графическим методом на Линейное программирование: решение задач графическим способом - реферат ЭВМ

2.1 Описание работы программки

Программка написана с внедрением собственных функций и процедур и 3-х стандартных модулей System, Crt и Graph.

При запуске программки она инспектирует может быть ли внедрение графического интерфейса. Если это может быть то программка перебегает к последующему шагу.

Дальше процедурой ShowXOY Рисуется на экран координатные оси. На этом работа Линейное программирование: решение задач графическим способом - реферат этой процедуры завершается и юзер в последующей процедуре (EnterNerav и а именно в подпроцедуре GetNerav ) предлагается ввести коэффициенты неравенства a1 x+a2 y=b в последующем порядке: a 1 пробел a 2 пробел b . Сходу после ввода всех коэффициентов процедурой ShowLine рисуется подходящая линия. После нажатия [Esc] процедура EnterNerav завершается и Линейное программирование: решение задач графическим способом - реферат передает управление процедуре EnterMainF в какой юзеру предлагается ввести коэффициенты мотивированной функции. Дальше работа перебегает к процедуре GetResult где идет подсчет оконцательного товета с помощбю процедуры SolveOprtel где считаетя определитель т. е. точки скрещения мотивированной функции с каждой линией ограничения. Дальше выводится ответ, если это может быть Линейное программирование: решение задач графическим способом - реферат.

Дальше следует описание применяемых стандартных процедур и функций.

Процедуры и функции модуля System :

Function Frac (X : Real) : Real;

Возвращает дробную часть аргумента.

Параметр X - выражение вещественного типа. Итог - дробная часть X, другими словами Frac(X) = X-Int(X) .

Procedure Str (X [: Width [: Decimals ]]; Var S : String);

Преобразовывает число в строчку. Преобразовывает Линейное программирование: решение задач графическим способом - реферат числовое значение X в строковое представление этого числа, которое можно выводить операторами типа Write и OutText .

Function Round (X : Real) : Longint;

Округляет значение вещественного типа до значения целочисленного типа. X - выражение с реальным типом. Round возвращает значение типа Longint , которое является значением X, округлого к самому близкому Линейное программирование: решение задач графическим способом - реферат целому числу. Если X – ровно в центре меж 2-мя целыми числами, то результатом будет число с наибольшей абсолютной величиной.

Если округлое значение X ненаходится снутри допустимого спектра Longint , то происходит ошибка во время выполнения программки.

Модуль Crt :

В модуле Crt находятся массивные подпрограммы, которые дают вам возможность полного управления способностями вашего Линейное программирование: решение задач графическим способом - реферат PC.

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

Crt может употребляться исключительно в программках, созданных для IBM PC, AT, PS/2 и стопроцентно совместимых.

Procedure Read ( [ var F : Text; ] V1 [ , V2, …, VN ]); (текстовые файлы)

Читает одну либо более Линейное программирование: решение задач графическим способом - реферат величин из текстового файла в одну либо более переменных. Характеристики: F - необязательная переменная текстового файла, если не указана, то употребляется стандартная переменная Input ; V1,...,VN - переменные типа Char, Integer, Real либо String .

В случае переменной типа Char процедура Read считывает из файла один знак и присваивает его переменной. В случае Линейное программирование: решение задач графическим способом - реферат переменной целого типа процедура Read ждет поступления последовательности знаков, образующих число со знаком, согласно принятому в Паскале синтаксису. Любые пробелы, знаки табуляции либо метки конца строчки, предыдущие числовой строке, пропускаются. Считывание прекращается при обнаружении первого пробела, знака табуляции либо метки конца строчки, которые следуют за числовой строчкой, либо в Линейное программирование: решение задач графическим способом - реферат этом случае, если функция Eof ( F ) воспринимает значение True . Если числовая строчка не соответствует ожидаемому формату, то происходит ошибка ввода-вывода, в неприятном случае переменной присваивается считанное значение. Если Eof(F) воспринимала значение True перед выполнением процедуры Read , либо Eof(F) приняла значение True при пропуске исходных пробелов Линейное программирование: решение задач графическим способом - реферат, символов табуляции либо меток конца строчки, то переменной присваивается нулевое значение. Последующая операция Read начнется с пробела, знака табуляции либо метки конца строчки, которыми закончилась числовая строчка.

В случае переменной вещественного типа процедура Read ждет поступления последовательности знаков, которые образуют число со знаком в согласовании с принятым в Паскале Линейное программирование: решение задач графическим способом - реферат синтаксисом кроме того, что шестнадцатиричное представление не допускается. Любые пробелы, знаки табуляции либо метки конца строчки, предыдущие числовой строке, пропускаются. Считывание прекращается при обнаружении первого пробела, знака табуляции либо метки конца строчки, которые следуют за числовой строчкой либо в этом случае, если функция Eof(F) воспринимает значение True . Если Линейное программирование: решение задач графическим способом - реферат числовая строчка не соответствует ожидаемому формату, то происходит ошибка ввода-вывода, в неприятном случае переменной присваивается считанное значение.

Если Eo f (F) воспринимало значение True перед выполнением процедуры Read , либо Eof(F) приняло значение True при пропуске исходных пробелов, символов табуляции либо меток конца строчки, то переменной присваивается нулевое Линейное программирование: решение задач графическим способом - реферат значение. Последующая операция Read начнется с пробела, знака табуляции либо метки конца строчки, которыми закончилась числовая строчка.

Procedure Write ( [ var F : Text; ] P1 [ , P2,…, PN ] ); (текстовые файлы) Записывает одну либо более величин в текстовый файл. F - переменная текстового файла, если не указана, то подразумевается внедрение стандартной файловой переменной Output , P1,...,PN - характеристики Линейное программирование: решение задач графическим способом - реферат записи, которые содержат выводимые выражения типов Char, Integer, Real, String, Packed String либо Boolean . Параметр записи также может содержать спецификацию ширины поля и количество десятичных символов. Параметр записи имеет последующий вид: OutExpr [ : MinWid th [ : DecPlaces ] ], где OutExpr представляет собой выводимое выражение, MinWidth - целое число, задающее наименьшую ширину поля, которая Линейное программирование: решение задач графическим способом - реферат должна быть больше нуля. Записывается ровно столько знаков, сколько определено в MinWidth (по мере надобности употребляются ведущие пробелы) кроме случаев, когда OutExpr имеет значение, которое должно быть представлено огромным количеством знаков, чем обозначено в MinWidth . В данном случае записывается количество знаков, достаточное для представления выводимой величины. Аналогично, если параметр Линейное программирование: решение задач графическим способом - реферат MinWidth опущен, то записывается нужное количество знаков. DecPlaces задает число десятичных символов в представлении вещественного значения с фиксированной точкой. Оно может указываться исключительно в том случае, если OutExpr имеет тип Real , и указан параметр MinWidth . Если параметр MinWidth указан, то он должен быть больше либо равен нулю.

Модуль Graph Линейное программирование: решение задач графическим способом - реферат находится библиотека, состоящая из более чем 50 графических подпрограмм от побитовых до подпрограмм высочайшего уровня.

Procedure SetColor (Color : Word);

Устанавливает текущий цвет, используя гамму. SetColor(5) делает 5-ый цвет в гамме цветом текущего рисунка. Цвет может быть задан числом от 0 до 15 (для стандартных драйверов), зависимо от текущего графического драйвера и Линейное программирование: решение задач графическим способом - реферат текущего графического режима.

Procedure Line (X1, Y1, X2, Y2 : Integer);

Отрисовывают линию из точки с координатами (X1, Y1) в точку с координатами (X2, Y2). Отрисовывают линию стилем и шириной, определенными SetLineStyle и употребляет цвет, установленный воззванием к процедуре SetColor .
Последовательность операторов

MoveTo(100, 100); LineTo(200, 200);

является эквивалентной

Line(100, 100, 200, 200); MoveTo(200, 200);

Procedure OutTextXY (X, Y Линейное программирование: решение задач графическим способом - реферат : Integer; TextString : String);

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

Процедура OutTextXY употребляет набор шрифтов SetTextStyle . Чтоб поддерживать сопоставимость кода при использовании нескольких шрифтов, используйте TextWidth и TextHeight для определения размера строчки.

Procedure SetFillStyle (Pattern : Word; Color : Word);

Устанавливает цвет и стиль закраски. Устанавливает шаблон Линейное программирование: решение задач графическим способом - реферат и цвет для всех операций закраски, производимых FillPoly, Bar, Bar3D и PieSlice . Доступно несколько предопределенных шаблонов закраски. Данный по дефлоту шаблон = Solid и данный по дефлоту цвет - цвет с наибольшим номером в гамме. Если в SetFillStyle переданы недопустимые характеристики, то в переменной GraphResult ворачивается значение grError , и текущие установки закраски Линейное программирование: решение задач графическим способом - реферат не будут изменены.

Если Pattern приравнивается UserFill , то активным шаблоном закраски станет шаблон, определяемый юзером (устанавливаемый при помощи процедуры SetFillPattern ).

Procedure FloodFill (X, Y : Integer; Border : Word);

Закрашивает замкнутую область, используя текущие стиль и цвет закраски. Закрашивает замкнутую область на растровых устройствах. Точка с координатами (X Линейное программирование: решение задач графическим способом - реферат, Y) - исходная точка снутри замкнутой области, с которой начнется закраска. Текущий шаблон закраски устанавливается процедурами SetFillStyle и SetFillPattern . Закрашивается область, ограниченная цветом с номером Border . Если точка (X, Y) находится снутри замкнутой области, то закраска будет происходить снутри области. Если же эта точка находится снаружи замкнутой области, то будет Линейное программирование: решение задач графическим способом - реферат закрашено все место вне области.

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

2.1 Текст программки

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O+,P-,Q-,R-,S+,T-,V+,X+}

{$M 16384,0,655360}

program Kurs1;{Геометрическая интерпретация решения задач}

uses

CRT, Graph;{используемы модули}

{Типы}

type

TNerav = record{коэффициенты неравенств Линейное программирование: решение задач графическим способом - реферат а1 х+а2 y<=b}

x: Real;{a1}

y: Real;{a2}

b: Real; {b}

end;

TMatrix = array[1..100] of TNerav;{Количество неравенств}

{Константы}

const

MaxX: Integer = 640-30; {максимальное значение X на экране}

MaxY = 20; {максимальное значение Y на экране}

MinX = 40; {x=0 малое значение X на экране}

MinY: Integer = 480-40;{y=0 малое значение Y на экране}

MASHT = 15; {Масштаб при Линейное программирование: решение задач графическим способом - реферат 15: maxY=28, MaxX=38}

STEP = 1; {шаг конфигурации свободного члена мотивированной функчии}

{Переменные}

var

Gd, Gm: Integer; {Иниц. гафики}

Matr: TMatrix; {Матрица неравенств}

c: Real; {Свободный член мотивированной ф-ии}

N: TNerav; {Коэффициенты неравенств}

i: 0..100; {Счетчик кол-ва неравенств}

MainF: TNerav; {Коэффициенты мотивированной ф-ии}

XResult,YResult: Real; {Ответ(кординаты)}

procedure ShowXOY Линейное программирование: решение задач графическим способом - реферат;{Проц. показа координатных осей}

Begin

SetColor(White);

Line(MinX, MaxY,MinX-4, MaxY+7);{стрелочки у Y}

Line(MinX, MaxY,MinX+4, MaxY+7);

OutTextXY(MinX-15, MaxY, 'У');

MoveTo(MinX, MaxY);

LineTo(MinX, MinY);{Сами оси}

LineTo(MaxX, MinY);

Line(MaxX, MinY, MaxX-7, MinY-4);{стрелочки у X}

Line(MaxX, MinY, MaxX-7, MinY+4);

OutTextXY(MaxX Линейное программирование: решение задач графическим способом - реферат, MinY+5, 'X');

End;

procedure ShowLine(_iN:TNerav);

var s: String;

Begin

if _iN.b/_iN.y<0 then begin{если коэффиц. при Y меньше 0}

MoveTo(MinX+Round((_iN.b-(Round(MinY/MASHT)*_iN.y))/_iN.x*MASHT),MaxY);

SetColor(15);

LineTo(MinX+Round(_iN.b/_iN.x*MASHT),MinY);

end;

if _iN.b/_iN Линейное программирование: решение задач графическим способом - реферат.x<0 then begin{если коэффиц. при X меньше 0}

MoveTo(MinX,MinY-Round(_iN.b/_iN.y*MASHT));

SetColor(15);

LineTo(MaxX,MinY-Round((_iN.b-(Round(MaxX/MASHT)*_iN.x))/_iN.y*MASHT));

end;

SetColor(LightGreen);

Str(_iN.b/_iN.x:3:1,s);

OutTextXY(MinX+Round(_iN.b/_iN.x*MASHT Линейное программирование: решение задач графическим способом - реферат),MinY+5,s);{рисуем значения на оси OX}

Str(_iN.b/_iN.y:3:1,s);

OutTextXY(MinX-40,MinY-Round(_iN.b/_iN.y*MASHT),s);{рисуем значения на оси OY}

MoveTo(MinX,MinY-Round(_iN.b/_iN.y*MASHT));

SetColor(15);{Рисуем саму линию}

LineTo(MinX+Round(_iN.b/_iN.x*MASHT),MinY Линейное программирование: решение задач графическим способом - реферат);

End;

procedure EnterNerav;{процедура ввода неравенств до нажатия Esc}

procedure GetNerav;{подпроцедура ввода коэф-тов 1-го неравенства}

var j,k: Real;

Begin

repeat

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY-1);

OutTextXY(7,3,'Введите коэффициенты неравенств: ');

Window(34,1,80,1);

Read(N.x, N.y, N.b);{вводим коэффициенты}

j:=N.x;

k:=N.y;

repeat{далее идет Линейное программирование: решение задач графическим способом - реферат сокращение коэффициентов если это возможно}

if (Frac(N.b / j) = 0) then

if (Frac(N.x / j) = 0) then Break;

j:=j-1;

until (j<=0);

if J>=0 then

repeat

if (Frac(N.b / k) = 0) then begin

if (Frac(N.y / k) = 0) then

if (j=k) then begin

N.b:=N.b / k;

N.x:=N.x / k;

N.y Линейное программирование: решение задач графическим способом - реферат:=N.y / k;

Break;

end

end;

k:=k-1;

until (k<=0);

until (N.x0) and (N.y0); {Ограничение чтобы небыло нулей}

Inc(i); {Увеличиваем счетчик}

Matr[i]:=N;{Добавляем в матрицу коэффициенты}

ShowLine(N);{Вызываем функцию рисования линии}

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY-1);

OutTextXY(7,3,'Ввести еще? (Enter=Да/Esc=Нет)');

End;

var

Key:Char;

Begin

GetNerav Линейное программирование: решение задач графическим способом - реферат;

repeat

key:=#0;

if KeyPressed then begin

key:=ReadKey;

case key of

#13: GetNerav;{ввод еще 1-го нер-ва}

end;

end;

Until Key in [#27];{до нажатия Esc}

End;

procedure EnterMainF;

{эта процедура предлагает избрать юзеру избрать выход из ОДЗ}

var key: Char;

j: 0..100;

S: String;

Begin

SetFillStyle(3,1); FloodFill(MinX+1, MinY-1, 15);

SetFillStyle(1,0); Bar(0,0,GetMaxX,MaxY Линейное программирование: решение задач графическим способом - реферат-1);

SetColor(White);

OutTextXY(7,3,'Введите коэффициенты мотивированной функции: ');

Window(40,1,80,25); Read(MainF.x, MainF.y);

End;

procedure GetResult;

var

k,j: 0..100;

X: Real;

Y: Real;

XTmp: Real;

YTmp: Real;

cTmp: Real;

boolAnswer: Boolean;

key: Char;

STmp: String;

Result: String;{Строка для вывода на экра результата}

procedure SolveOprtel(inN, inMainF: TNerav Линейное программирование: решение задач графическим способом - реферат; ic:Real; var outX, outY: Real);

{в этой подпроцедуре подностью рассчитывается определитель}

var

_d: Real;{Дельта определителя}

dx: Real;{Дельта X определителя}

dy: Real;{Дельта Y определителя}

Begin

_d:=(inN.x*(inMainF.y)) - (inN.y*inMainF.x);

dx:=(inN.b*(inMainF.y)) - (inN.y*ic);

dy:=(inN.x*ic) - (inN.b*inMainF.x);

if Линейное программирование: решение задач графическим способом - реферат _d 0 then begin{исклюсаем бессчетное мн-во решений}

outX:=dx/_d;

outY:=dy/_d;

end;

if (_d = 0) and ((dx = 0) xor (dy = 0)) then begin{исклюсаем - нет решений}

SetColor(Red);

OutTextXY(300,230,'Нет решений!!!');

ReadKey;

CloseGraph;

Halt;

end;

End;

Begin

Bar(0,0,GetMaxX,MaxY-1);

SetColor(White);

OutTextXY(7,3,'Пожалуйста подождите... (Esc - Отмена Линейное программирование: решение задач графическим способом - реферат)');

{считаем координаты выхода}

c:=0;

cTmp:=0;

repeat

if i=1 then SolveOprtel(Matr[1], MainF, c, XResult, YResult)

else

for j:=1 to i-1 do begin

SolveOprtel(Matr[j], MainF, c, XTmp, YTmp);

for k:=j+1 to i do begin

SolveOprtel(Matr[k], MainF, c, X, Y);

if X=XTmp then XResult:=X;

if Y=YTmp then YResult Линейное программирование: решение задач графическим способом - реферат:=Y;

end;

end;

{далее мы находим максимум функции}

BoolAnswer:=False;

for k:=1 to i do begin

N:=Matr[k];

if (N.x*XResult+N.y*YResult<=N.b) then begin

{Если в ОДЗ}

c:=cTmp;

boolAnswer:=True;

end;

{далее проверяем вышла ли cTmp за ОДЗ}

if (N.x*XResult+N.y*YResult Линейное программирование: решение задач графическим способом - реферат>N.b) then begin Exit

end;

end;

cTmp:=cTmp+STEP;{Увеличиваем cTmp на STEP}

if keyPressed then key:=ReadKey;{если Esc нажата, то прерываем}

until (key=#27) or (cTmp>=10000);

if boolAnswer then begin

{пишем ответ:}

{1. Рисуем мотивированную ф-ю в подходящем месте}

c:=MainF.x*XResult+MainF.y*YResult;

MoveTo(MinX Линейное программирование: решение задач графическим способом - реферат+1,MinY-Round(C/MainF.y*MASHT)-1);

SetColor(Red);{рисуем мотивированную линию на экр. красным}

LineTo(MinX+Round(C/MainF.x*MASHT)+1,MinY-1);

SetLineStyle(1,0,NormWidth);

SetColor(Yellow);

{2. Считаем max(f)}

Str(MainF.x*XResult+MainF.y*YResult:2:1,STmp);

Result:='max(f)='+Stmp;

{3. Рисуем значение на оси X}

Line(MinX+Round(XResult)*MASHT,MinY Линейное программирование: решение задач графическим способом - реферат-Round(YResult)*MASHT,MinX+Round(XResult)*MASHT,MinY+3);

Str(XResult:2:1,STmp);

OutTextXY(MinX+Round(XResult)*MASHT,MinY+4,STmp);

Result:=Result+' при x='+Stmp;

{4. Рисуем значение на оси Y}

Line(MinX+Round(XResult)*MASHT,MinY-Round(YResult)*MASHT,MinX-3,MinY-Round(YResult)*MASHT);

Str(YResult:2:1,STmp);

OutTextXY(MinX-30,MinY Линейное программирование: решение задач графическим способом - реферат-Round(YResult)*MASHT,STmp);

Result:=Result+' y='+Stmp;

SetColor(White);

SetLineStyle(0,0,NormWidth);

OutTextXY(300,230,Result);{Выводим строчку ответа}

end

else

OutTextXY(7,3,'Вычисления не окончены!!!');

{Завешение программы}

Bar(0,0,GetMaxX,MaxY-1);

SetColor(White);

OutTextXY(7,3,'Нажмите всякую кнопку для выхода');

ReadKey;

End;

BEGIN

i:=0;{Начальное значение кол-ва неравенств}

Gd:=Detect;

InitGraph(Gd, Gm, 'C:\BP Линейное программирование: решение задач графическим способом - реферат\BGI'); { Путь к BGI драйверам }

if GraphResult grOk then Halt(1);

ShowXOY;

EnterNerav;

EnterMainF;

GetResult;

CloseGraph;

END.

Заключение

Программка решения задач линейного программирования графическим методом на IBM PC была написана на языке Borland Pascal 7.1. В ней, для удобства, рассматривается случай когда количество переменных равно двум т. е. решение задачки можно расположить Линейное программирование: решение задач графическим способом - реферат на плоскости. При помощи этой программки можно наглядно показать способ графического решения задач.

Вообщем, при помощи графического способа может быть решена задачка линейного программирования, система ограничений которой содержит n неведомых и m линейно независящих уравнений, если N и M связаны соотношением N – M = 2.

Вправду, пусть поставлена Линейное программирование: решение задач графическим способом - реферат задачка линейного программирования.

Отыскать наибольшее значение линейной функции

Z = С1 х1 +С2 х2 +... +СN xN при ограничениях

a11 x1 + a22 x2 + ... + a1N ХN = b1

a21 x1 + a22 x2 + ... + a2N ХN = b2

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

aМ1 x1 + aМ2 x2 + ... + aМN ХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

где все уравнения линейно независимы и производится cоотношение Линейное программирование: решение задач графическим способом - реферат N - M = 2.

Используя способ Жордана-Гаусса, производим M исключений, в итоге которых базовыми неведомыми оказались, к примеру, M первых неведомых х1 , х2 , ..., хM , а свободными - два последних: хМ+1 , и хN , т. е. система ограничений приняла вид:

x1 + a1,М+1 xМ+1 + a1N ХN = b1

x2 + a2,М+1 xМ+1 + a Линейное программирование: решение задач графическим способом - реферат2N ХN = b2

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

xМ + aМ, М+1 x2 + aМN ХN = bМ

xj ≥ 0 (j = 1, 2, ..., N)

При помощи уравнений перевоплощенной системы выражаем линейную функцию только через свободные неведомые и, беря во внимание, что все базовые неведомые - неотрицательные: хj ≥ 0 (j = 1, 2, ..., M), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств.


Литература

1. Абрамов Л.М Линейное программирование: решение задач графическим способом - реферат., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

2. Акулич И.Л. Математическое программирование в примерах и задачках: Учеб. пособие - 2-е изд., испр. и доп. - М.: Высш. шк. ,1993 - 336 с.

3. Ашманов С.А.Линейное программирование. - М.: Наука, 1981.

4. Баканов М.И., Шеремет А.Д. Теория экономического анализа Линейное программирование: решение задач графическим способом - реферат: Учебник. -4-е изд., доп. и перераб. - М.: Деньги и статистика, 2000. - 416 с.

5. Баканов М.И., Шеремет А.Д.Экономический анализ: ситуации, испытания, примеры, задачки, выбор хороших решений, финансовое прогнозирование: Учеб. пособие. - М.: Деньги и статистика, 1999. -656 с.

6. Банди Б. Базы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. -176 с.

7. Габасов Р., Кириллова Линейное программирование: решение задач графическим способом - реферат Ф.М. Способы линейного программирования. Ч.1. Общие задачки, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 176 с.

8. Габасов Р., Кириллова Ф.М. Способы линейного программирования. Ч.2. Транспортные задачки, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 240 с.

9. Глухов В.В., Медников М.Д., Коробко С.Б. Математические Линейное программирование: решение задач графическим способом - реферат способы и модели для менеджмента - СПб.: Издательство “Лань”, 2000. -480 с.

10. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование,теория, способы и приложения. - М.: Наука, 1969.

11. Гасс С.Линейное программирование. - М.: Физматгиз, 1961.

12. Заварыкин В. М. и др. Численные способы: Учеб. пособие для студентов физ.-мат. спец. пед. ин-тов / В.М. Заварыкин, В.Г. Житомирский Линейное программирование: решение задач графическим способом - реферат, М.П. Лапчик. - М.: Просвещение, 1990. - 176 с

13. .Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. /Под общ. ред. проф. Кузнецова А.В., М., “ВЫШЭЙШАЯ ШКОЛА”, 1994. - 288 с.

14. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие. – 2-е изд., перераб Линейное программирование: решение задач графическим способом - реферат и доп. - М.: Высш. школа, 1980. -300 с.

15. Ляшенко И.Н, Карагодова Е.А, Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Издательское объединение “Вища школа”, 1975. - 372 с.

16. Пер. с яп. /М. Кубонива, М. Табата, С. Табата, Ю. Хасэбэ, под ред. М. Кубонива. Математическая экономика на компьютере: - М.: Высш. школа, 1980.

17. Под Линейное программирование: решение задач графическим способом - реферат ред и с предисл. Е.З. Демиденко – М.: Деньги и статистика, 1991. – 304 с.

18. Солодовников А.С. Введение в линейную алгебру и линейное программирование. М., Изд. “Просвещение”, 1966. - 184 с.

19. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т.1: Пер с англ. - М.: Мир, 1991. -360 с.

20. Тынкевич М.А. Экономико-математические способы Линейное программирование: решение задач графическим способом - реферат (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000. - 177 с.

Рецензия



liga-obshestv-krasnogo-kresta-i-krasnogo-polumesyaca.html
ligazakonua-15062012-v-parlamente-predlagayut-snizit-pensionnij-vozrast-dlya-zhitelej-ekologicheski-opasnih-regionov.html
lihachev-dmitrij-sergeevich-referat.html