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

Размещено на http://www.allbest.ru/

Введение

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

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие, в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику? Такие методы объединяются под общим названием -- математическое программирование.

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи -- это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д.

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

Один из разделов математического программирования называется - линейным программированием.

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

I. Основная часть

Модель задачи математического программирования включает:

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

целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант -из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач -- симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

умение находить начальный опорный план;

наличие признака оптимальности опорного плана;

умение переходить к улучшенному опорному плану.

1.1 Понятие линейного программирования.

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

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

1.2 Симплекс метод

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

1.3 Экономическая постановка задачи

Для откорма крупно рогатого скота используют два вида кормов: b1, b2, в которые питательные вещества а1,а2,а3,а4. Содержание количества единиц питательных веществ в 1 кг каждого корма, стоимость 1 кг корма и содержание питательных веществ в рационе животного представлены в таблице 7. Составьте рацион при условии минимальной стоимости.



Питательные вещества	Виды кормов	Норма содержание питательных веществ
	b1	b2
а1	3	4	24
а2	1	2	18
а3	4	0	20
а4	0	1	6
Стоимость 1кг корма, руб	1	2

1.4 Понятие математической модели

Решение какой-либо задачи управления можно разбить на несколько этапов:

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

разработка математической модели изучаемой системы;

выбор метода и отыскание решения с помощью этой модели;

проверка решения.

В каждой задаче мы должны ясно определить цели, поставленные перед системой, изучить обстановку, освоиться с терминологией, процессом, определить различные способы действия, приемлемые для ситуации, дать в какой-то форме постановку задачи. Построить подходящую логическую, или математическую модель, которая свяжет переменные задачи с реальными ограничениями, целями задачи, мерой эффективности. Затем, исходя из полученной модели, выбрать метод, и найти решение, оптимизирующее эту меру эффективности, т. Е. оптимальное решение. И сравнить это полученное с помощью математической модели решение с действительностью, чтобы выяснить, в самом ли деле мы сформулировали и решали ту реальную задачу, с которой начали? Когда меняется ситуация, какие изменения надо вносить в математическую модель? Можно ли улучшить модель, что привело бы к новым решениям, более реалистичным и точным.

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

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

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

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

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

1.5 Двойственная задача линейного программирования

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

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

Количество переменных в двойственной задаче равно количеству неравенств в исходной.

Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Условиям неотрицательности переменных исходной задачи соответствуют неравенства ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.

Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных y_i в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными .

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

Теорема 1 (первая теорема двойственности)

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II

Теорема 2 (вторая теорема двойственности)

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.

1.6 Решение исходной задачи двойственным симплекс методом

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

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

Возможны ситуации:

В индексной F- строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.

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

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

Имеем задачу (I) построим ей двойственную (II).

I. II.

F=2X₁+X₂min G=24Y₁ + 18Y₂ + 20Y₃ + 6Y ₄max

Приведем ее к каноническому виду.

Введем базисные переменные ,

G=- G = -24Y₁ - 18Y₂ - 20Y₃ - 6Y ₄ min

Решаем симплекс-методом задачу .

1.Найдем разрешающий элемент.

1.1. Из отрицательных элементов индексной F- строки выберем наибольший по модулю, назовем соответствующий ему столбец - разрешающим.

1.2. Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов к только положительным элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим. Будем выделять его цветом.

В нашем примере, (Таблица 1), элемент 3 - разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.

базисные	-Y1	-Y2	-Y3	-Y 4	свободные
Y5	3	1	4	0	2
Y6	4	2	0	1	1
-G	-24	-18	-20	-6	0

2. Выбрав разрешающий элемент, делаем перечет таблицы по правилам:

2.1. В новой таблице, таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В данной задаче: Y ₁ входит в базис, вместо

Y ₅, которая выходит из базиса, и теперь свободная.

2.2. На месте разрешающего элемента записываем обратное ему число (Таблица 2).

2.3. Элементы разрешающей строки делятся на разрешающий элемент.

2.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком.

2.5. Чтобы заполнить оставшиеся элементы таблицы 5, осуществляем пересчет по правилу прямоугольника.

Пусть мы хотим посчитать элемент, стоящий на месте 2(Y₂;Y₆ )

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

Итак, . Записываем на место, где было 3(Таблица 2).

Пересчитываем так все элементы:

базисные	Y5	Y2	Y3	Y 4	свободные
Y1				0
Y6				1
-G	8	-10	12	-6	16

Проверим целевую функцию, согласно условиям.

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

базисные	-Y5	-Y1	-Y3	-Y 4	свободные
Y2	1	3	4	0	2
Y6	-2	-2		1	-3
-G	18	30	52	-6	36
базисные	-Y5	-Y1	-Y3	-Y 6	свободные
Y2	1	3	4	0	2
Y4	-2	-2		1	-3
-G	6	18	16	6	54

В индексной F- строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.

Выписываем решение согласно таблице 4:

Y₁= 0; Y₄=-3;

Y₂= 2; Y₅= 0;

Y₃ = 0; Y₆= 0;

Подставляем полученные решения в условия задачи:

I. II.

Два условия в II системе не совпадают, выписываем из в I системы эти условия и решаем как систему уравнений.

F=2X₁+X₂min = 2*6+6 = 18

Ответ к задаче:

Для эффективного откорма крупно рогатого скота необходимо 6 корма b1 и 6 корма b2 . При этом затраты минимальны и составят 18 руб.

II. Специальная часть

2.1 Планирование деятельности с использованием методов

линейного программирования

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

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

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

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

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

Постановку задачи методом линейного программирования можно представить следующим образом:

Имеются какие-то переменные x=(x1,x2,….,xn) и целевая функция этих переменных f(x)=(x1,x2,….,xn). Ставится задача: найти максимум или минимум целевой функции f(x) при условии, что переменные x принадлежат некоторой области, которая имеет ограничения.

Линейное программирование включает в себя ряд шагов:

1. Идентифицировать управляемые переменные и цель задачи.

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

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

4. Получить и оценить оптимальное решение. Оценка включает в себя анализ задачи на чувствительность. Наиболее распространенными направлениями использования линейного программирования в военном деле являются:

- задача о перевозках (транспортная задача)

- задача на распределение сил и средств (распределение сил и средств поражения по целям, распределение сил и средств разведки и др.)

2.2 Задачи о перевозках (транспортная задача).

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

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

Пусть имеется m складов, в которых сосредоточен некоторый однородный продукт (ГСМ, боеприпасы и т.д.) в количествах соответственно аi(i=1,2,…,m) единиц. Имеется n потребителей этого продукта в количествах соответственно bj(j=1,2,…,n) единиц. На основании опытов и расчетов известно, что на доставку одной единицы продукции

Рассмотрим применение метода линейного программирования на примере.

Предприятие производит два вида продукции X и Y. Доход предприятия составляет 0,10 тыс.руб. за 1 л продукции Х и 0,3 тыс.руб. за 1 л Y. Предприятие может продать всю продукцию, которая будет произведена, однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л продукта Х требуется 0,02 ч работы оборудования, а для производства 1 л Y - 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л X и Y соответственно. Время работы оборудования 24 ч. Ежедневно запас специального ингредиента 16 кг.

Сколько продукции каждого вида следует производить ежедневно, если цель предприятия состоит в максимизации ежедневного дохода?

Шаг 1. Определение переменных. В рамках заданных ограничений компания должна принять решение о том, какое количество каждого вида напитков следует выпускать. Пусть х - число литров продукта Х, производимое за день. Пусть у - число литров продукта Y, производимое за день.

Шаг 2. Определение цели и ограничений. Цель состоит в максимизации ежедневного дохода (целевая функция). Он максимизируется в рамках ограничений на количество часов работы оборудования и наличие специального ингредиента.

Шаг 3. Выразим цель через переменные:

F = 0,10 x 0,30 y (тыс.руб. в день).

Это целевая функция задачи - количественное соотношение, которое подлежит оптимизации.

Шаг 4. Выразим ограничения через переменные. Существуют следующие ограничения на производственный процесс:

а) Время работы оборудования. Для производства продукта Х и Y требуется: (0,02 х 0,04 у) часов работы оборудования ежедневно. Максимальное время работы оборудования в день составляет 24 ч, следовательно, объем производства должен быть таким, чтобы число затраченных часов работы оборудования было меньше либо равно 24 ч ежедневно. Таким образом,

б) Специальный ингредиент. Максимальный расход ингредиента составляет 16 кг в день, следовательно, объем производства должен быть таким, чтобы требуемое количество специального ингредиента составляло не более 16 кг в день. Таким образом,

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

в) Условие неотрицательности:

Окончательная формулировка задачи линейного программирования имеет следующий вид.

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

2.3 Простой пример задачи такого класса

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

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов

По данному условию сформулируем задачу линейного программирования.

Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов.

Формулировка ЗЛП: = 2x1 + 4x2 > max;

4x1 + 6x2 ? 120,

2x1 + 6x2 ? 72,

x2 ? 10;

x1 ? 0, x2 ? 0.

Подчеркнем, что каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Повторимся, методы решения ЗЛП мы будем рассматривать чуть позднее, а сейчас - пример задачи другого типа.

2. Задача о смесях (планирование состава продукции).

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

2.4 Основные теоремы линейного программирования

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

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

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

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

В частном случае, когда в систему ограничений входят только две переменные x1 и x2, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x1, x2 ? 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.

Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.

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

2.5 Методика решения задач ЛП графическим методом

I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если  неравенство истинное,

то    надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ - против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

2.6 Экономическая постановка задачи линейного

программирования

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии 60 изделий, второй линии 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

2.7 Построение математической модели.

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

 - суточный объем производства радиоприемников первой модели, [шт/сутки];

 - суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция

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

· их объемы производства, т.е. и радиоприемников в сутки;

· прибыль от их реализации  - согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели - $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

Возможные объемы производства радиоприемников и ограничиваются следующими условиями:

· количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;

· суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) - 80 шт;

· объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3)неотрицательностью объемов производства.

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

1) Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2) Ограничения по суточному объему первой и второй технологических линий имеют вид:

[шт/сутки]

3) Неотрицательность объемов производства задается как

.

Таким образом, математическая модель этой задачи имеет вид

2.8. Нахождение оптимального решения задачи с помощью

линейного метода.

Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).

прямая (1) - точки (0;95) и (63,(3);0), прямая (2) проходит через точку параллельно оси , прямая (3) проходит через точку параллельно оси .

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

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

Точки пересечения с осями - (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D - это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D - это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно [$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит 2500$ в сутки.

2.9 Программное решение задачи в EXSEL

Задачу о выпуске радиоприемников, решенную графическим методом, проверим в EXCELe..

Составим математическую модель и заполним таблицу.

	1-ое изделие	2-ое изделие		Ограничения
	Х1	Х2
Расход элементов	15	10		0
Суточный объем	60	80
Прибыль от реал.	40	20		0
		40*X1+20*Х2

Размещено на http://www.allbest.ru/

	МАХ
	15*Х1+10*Х2<=950
	X1<=60
	X2<=80

Из меню Сервис выбираем Поиск решений. Устанавливаем целевую ячейку, вариант оптимизации- максимизация, выставляем ограничения и устанавливаем адреса ячеек, изменяющие свое значение.

После выполнения решения получаем искомый результат:

	1-ое изделие	2-ое изделие		Ограничения
	Х1	Х2
	60	5
Расход элементов	15	10		950
Суточный объем	60	80
Прибыль от реал.	40	20		2500

Максимальная прибыль -2500 $.

Объем производства 1-ой модели-60 шт.

Объем производства 2-ой модели - 5 штук.

Заключение

Линейное программирование не имеет ничего общего с программированием, просто слово «программирование» при переводе с английского должно было называться «планирование».

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

оптимальная прибыль от реализации продукции достигается при следующем суточном производстве радиоприемников: 60 шт радиоприемников первой модели и 5 шт радиоприемников второй модели. При этом прибыль от реализации составит 2500$ в сутки.

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

С помощью MS EXCEL, в считанные секунды ,с помощью вставленной в EXCEL программы Поиск решений результаты , полученные графическим методом я подтвердила, что видно из рисунков со значениями в ячейках.

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

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

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

1. И.Л.Акулич, Математическое программирование в примерах и задачах, Москва, «Высшая школа», 1986;

1. Лищенко «Линейное и нелинейное программирование», 1987

2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», 1987

3. АстафуровВ.Г., Колодникова Н. - Компьютерное учебное пособие, раздел “Анализ на чувствительность с помощью двойственной задачи”, Томск-2002.

4. Алесинская Т.В. - Задачи по исследованию операций с решениями.

5. Смородинский С.С., Батин Н.В. - Оптимизация решений на основе методов и моделей математического программирования: Учебное пособие.

6. Кононов В.А. - Исследование операций. Для продвинутых математиков.

7. http://matlab.exponenta.ru/optimiz/book_1/10/2_10.php

Размещено на Allbest.ru