Программа расчета оптимального распределения ресурсов

Содержание

 

Введение                                                                                      

 

1. Постановка задачи                                                               

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

3. Текстовый пример (выбор метода решения)                      

4. Разработка проекта  программы                                          

5. Кодирование модулей                                                           

Заключение

Литература

Приложение 1. Текст модулей  программы

Приложение 2. Иллюстрационный  плакат

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

 

Математическая модель – описание процесса математическими средствами, в которых отражены основные свойства и количественные соотношения реальной действительности. Предметом исследования математической теории исследования операций являются модели процессов оптимизации. Эти модели порождены задачами на условный экстремум. Важнейшей особенностью таких моделей является многовариантность допустимых решений. Задачей этого предмета является выявление структуры множества допустимых значений и разработка эффективных методов нахождения оптимального решения. Обычный перебор всех допустимых решений для нахождения оптимального варианта не годится, так как число возможных вариантов огромно. Классические методы нахождения экстремума здесь также не годятся: 1. Они требуют существования частных производных во всех областях, где существует экстремум. В то время в задачах оптимизации целевая функция достигает экстремума на границе области, где частные производные не существуют. 2. Классические методы применимы для небольшого числа переменных. 3. Для задач на условный экстремум типичными ограничениями, налагаемыми на переменные, являются неравенства, к которым классические методы не применимы.

Задачи оптимизации требуют особого подхода, для их решения необходимы специальные методы.

 

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

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

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

Настоящая курсовая работа посвящена наиболее распространенному методу решения задачи линейного программирования – симплекс-методу. Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании.

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

1. Через конечное число шагов задача будет решена или обнаружится отсутствие ее решения.

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

Этот метод был разработан американским математиком Джорджем Данцигом в 1947 году.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Постановка задачи

Фабрика производит 3 основных типа товара, изделию I требуется 3 единицы сырья А и 1 единица сырья В, оно приносит прибыль в 6 единиц.

Изделию II требуется 4 единицы сырья А и 3 единицы сырья В, оно приносит прибыль в 3 единицы.

Изделию III требуется 1 единица сырья А и 2 единицы сырья В, оно приносит прибыль в 2 единицы.

Доступны 20 единиц сырья А и 10 единиц сырья В. Найти оптимальный план.

 

В таблице предоставлены  сведения о расходах ресурса на заданную продукцию и возможную прибыль.

 

 

	I	II	III	Запас
А	3	4	1	20
В	1	3	2	10
Прибыль	6	3	2

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Условие задачи можно представить в виде следующей таблицы

Изделие Сырье	I	II	III	Запас
А	3	4	1	20
В	1	3	2	10
Прибыль	6	3	2

План выпуска продукции  из имеющегося сырья имеет вид:      

                 X₁ X₂ X₃

          

 Ограничения сырья:                         

                 3*X₁ + 4*X₂ + X₃ <= 20                                                

                 X₁ + 3*X₂ + 2*X₃ <= 10                                               

                                               

  Суммарная выручка будет иметь вид:

F(X) = 6*x₁ + 3*x₂ + 2x₃  

 _X1 x₂ x₃ >= 0

Где:

X₁ – количество единиц продукции I вида.

X₂ – количество единиц продукции II вида.

X₃ – количество единиц продукции III вида.

3 * X₁ – сырье А, потраченное на изготовление продукции I в количестве  X₁.

4 * X₂ – сырье А, потраченное на изготовление продукции II в количестве  X₂.

1 * X₃ – сырье А, потраченное на изготовление продукции III в количестве  X₃..

1 * X₁ – сырье B, потраченное на изготовление продукции I в количестве  X₁

3 * X₂ – сырье В, потраченное на изготовление продукции II в количестве  X₂.

2 * X₃ – сырье В, потраченное на изготовление продукции III в количестве  X₃.

Задача основная, но не каноническая, так как система  уравнений не является канонической. Ни в одном из уравнений нет базисного неизвестного.

 

 

 

Получим основную задачу ЛП из общей.

Основной называется задача, если все ограничения системы являются уравнениями (равенствами).

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

И полученная основная задача имеет вид:

 

3*x₁+4*x₂+ x₃ + x₄=20

x₁+3*x₂+ 2*x₃ + x₅=10

X_i 0   i=1, 5

 

F(x) = 6*x₁ + 3*x₂ + 2*x₃ + 0*x₄ + 0*x₅          max

 

 

 

 

 

3. Текстовый пример (выбор метода решения)

Для решения данной задачи я взял за основу симплекс-метод.

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

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

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

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

 

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

Например:

a₁₁x₁+a₁₂x₂+x₃=b₁

a₂₁x₁+a₂₂x₂+x₄=b₂

X_i ,   i=1, 4

F(x) = с_c - с₁х₁ - с₂х₂

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

Особенность канонической задачи в том, что она всегда имеет начальный базисный план. Для его получения достаточно свободные переменные положить =0  (x₁=x₂=0) тогда x₃=b₁ ; x₄=b₂ , тогда значение целевой функции равно с₀ (F(x)=c₀ ), а x=(0,0,b₁,b₂)

 

Решение канонической задачи ЛП будем находить симплекс-методом, с использованием симплекс-таблицы.

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

1. Через конечное число  шагов задача будет решена  или обнаружится отсутствие ее  решения.

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

Последняя строка таблицы  называется индексной и заполняется  коэффициентами целевой функции по следующему правилу:

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

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

В х₀ находятся значения базисных неизвестных. Если в задаче л/п система уравнений каноническая, а коэффициенты целевой функции выражены не только через свободные неизвестные, то такая задача называется “почти канонической”. При внесении такой задачи в симплекс таблицу индексная строка подсчитывается по правилу цен.

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

 

Алгоритм симплекс метода.