Задание Задача нахождения оптимального плана - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Ю. О. Чернышев «Разработка параллельного алгоритма нахождения оптимального... 1 85.14kb.
Задача нахождения наибольшей общей подпоследовательности 1 61.47kb.
Алгоритм нахождения спектра больших матриц 1 35.12kb.
Задача оптимального управления ресурсами промышленного предприятия... 1 153.57kb.
Использование технологии. Net remoting для решения задачи поисковой... 4 421.63kb.
Дискретное программирование 1 48.87kb.
Контрольные вопросы по курсу Основная задача линейного программирования. 1 45.33kb.
Задача оптимального программирования. Получение оптимальных решений... 1 18.73kb.
П. В. Светлов, Рецензент: проф. Л. А. Бордаг 1 12.81kb.
Мк-26-11 Индивидуальный выбор оптимального количества особенностей... 1 176.62kb.
Задача №1 Производственная задача 7 Задача №4 Задача о распределении... 6 787.52kb.
Уроки корпоративного управления в народной мудрости 2: Анализ басни... 1 315.34kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Задание Задача нахождения оптимального плана - страница №1/1

Задание 1. Задача нахождения оптимального плана

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



Вид

сырья



Номы расхода сырья на одно изделие, кг

Общее количество сырья, кг

Х1

Х2

I

II


5

4


7

9


35

36


Прибыль от реализации одного изделия, руб.

2


3




Математическая постановка задачи:

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

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

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





Строим график функции для первого и второго уравнений, для этого выражаем x2 из 1-го и 2-го уравнений:



- получаем точки (0; 5); (7; 0);

- получаем точки (0; 4); (9; 0)

Рис. 1 Область допустимых решений

Областью допустимых решений является многоугольник ОАВС, где точки имеют соответствующие координаты: О (0; 0); А (0; 4); В (3,7; 2,35); С (7; 0). Координаты точки В получены в результате пересечений прямых, их находим решая систему уравнений: . Получаем x1=3,7; x2=3,7.

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

Точкой, от которой начинается движение вдоль вершин многогранника ограничений является точка О (0; 0), а f(0; 0)=0. Движение будет осуществляться по часовой стрелке.

Найдем значение целевой функции в точке А с координатами (0; 4):

f(0; 4)=2*0+3*4=12. Так как fA>fO – движение продолжается.

Найдем значение целевой функции в точке В с координатами (3,7; 2,35):

f (3,7; 2,35)=2*3,7+3*2,35=14,45. Так как fВ>fА – движение продолжается в том же направлении.

Найдем значение целевой функции в точке С с координатами (7; 0):

f (7; 0)=2*7+3*0=14. Так как fВ>fС – движение вдоль вершин многогранника прекращается.

Таким образом, получаем что точка В (3,7; 2,35) является оптимальной.

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

Рассмотрим продолжение дерева ветвлений к задаче № 3. Окончательные ветви дерева ветвлений для задачи 5 представлены на следующей странице.



Рис. 2. Область допустимых решений

Расположение точек смотреть на рис. 2.



Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет f=14 в точках В(4; 2) и С(7; 0).

Ответ: оптимальное значение f=14 в точках В(4; 2) и С(7; 0).