Целочисленное программирование методом отсечений Гомори
Составление содержательной постановки для оптимизационной задачи целочисленного программирования. Сущность графического метода отсекающих плоскостей. Узловые точки координатной сетки, уменьшенные системой ограничений как область допустимых решений.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 04.05.2014 |
| Размер файла | 449,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
1. Постановка задачи
Составить содержательную постановку для заданной оптимизационной задачи целочисленного программирования (управляющие переменные, ограничения, целевая функция):
1. Вычислить оптимальное целочисленное решение графическим методом отсекающих гиперплоскостей (решение без учета целочисленности, решение с учетом целочисленности, решение с учетом целочисленности).
2. Факторы эффективности оптимального целочисленного решения.
2. Решение
Рассмотрим графический метод отсекающих плоскостей. Решим задачу ЦЧП - задача №1:
ОДР (Областью допустимых решений) задачи ЦЧП являются узловые точки координатной сетки ограниченные системой ограничений.
Построим диаграмму области допустимых решений ОДР1 задачи №1, рисунок 1:
Рис 1. Задача ЦЧП, задача №1
Строим область допустимых решений:
Табл. 1
Допустимыми решениями задачи ЦЧП являются целочисленные узлы координатной сетки, ограниченные условиями (1-3). Вершина B (целевая функция достигает своего максимума) имеет не дробные координаты, которые являются допустимыми решениями целочисленной задачи.
Шаг 1. Решим ослабленную задачу ЦЧП, т.е. без условия целочисленности переменных, задача №2:
Для задачи №2 построим диаграмму ОДР2 и вычислим оптимальное решение. Изобразим на рисунке 2.
Рис 2. Задача №2
ОДР задачи №2 является выпуклый треугольник ABC. Оптимальное решение - координаты вершины В(2,5; 4,5) и значение целевой функции F(В) = 37 у.е. Полученное оптимальное решение оказалось нецелочисленным, обе переменные - дробные.
Шаг 2. Введем в систему ограничений задачи №2 ПДО №1 для переменной. , получим задачу 3:
Для задачи №3 построим диаграмму ОДР3 и вычислим оптимальное решение, рис 3:
Рис. 3
Для задачи №3 ОДР является ABґС, оптимальным решением - координаты вершины Вґ(2; 3), значение целевой функции у.
Шаг 3. Введем в систему ограничений задачи №3 ПДО №2 для переменной , получим задачу №4.
Для задачи №4 построим диаграмму ОДР4 и вычислим оптимальное решение, рис 4.
оптимизационный целочисленный отсекающий графический
Рис 4. Задача №4
Отсекающие точки (3;3) и (4;1).
Для задачи №4 ОДР является A,B"C, оптимальное решение - координаты вершины B"(3;3) - целые, значение целевой функции F(B") = 30 y.e, оптимальное решение - целочисленно. Отсекающие точки(3;3) (4;1).
Следовательно, вычислено оптимальное целочисленное решение (), обеспечивающее max целевой функции исходной задачи ЦЧП. Задача ЦЧП решена.
Размещено на Allbest.ru
...Подобные документы
Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Описание задачи линейного целочисленного программирования. Общий алгоритм решения задач с помощью метода границ и ветвей, его сущность и применение для задач календарного планирования. Пример использования метода при решении задачи трех станков.
курсовая работа [728,8 K], добавлен 11.05.2011Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Формы задачи линейного программирования, каноническая форма. Симплекс-метод: теоретические основы, прямой алгоритм; метод Гомори. Математическая и техническая постановка задачи, программная реализация: запуск, графический интерфейс и созданные функции.
курсовая работа [578,7 K], добавлен 04.02.2011Алгоритм решения оптимизационной задачи линейного программирования (ЗЛП) – планирования производства симплекс методом и при помощи средства "Поиск решения" в Microsoft Excel. Описание работы, графический интерфейс и схема программы для решения ЗЛП.
дипломная работа [2,3 M], добавлен 19.09.2010Нахождение области допустимых значений и оптимумов целевой функции с целью решения графическим методом задачи линейного программирования. Нахождение оптимальных значений двойственных переменных при помощи симплексного метода и теории двойственности.
контрольная работа [116,0 K], добавлен 09.04.2012Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Теоретические основы экономико-математических методов. Этапы принятия решений. Классификация задач оптимизации. Задачи линейного, нелинейного, выпуклого, квадратичного, целочисленного, параметрического, динамического и стохастического программирования.
курсовая работа [2,3 M], добавлен 07.05.2013Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Оптимальный план прямой задачи. Значения функций целочисленного и нецелочисленного решений. Оптимальное решение двойственной задачи и условия дополняющей нежесткости. Условия канонической задачи линейного программирования. Метод Жордана–Гаусса.
контрольная работа [323,0 K], добавлен 20.01.2011Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010Задача линейного программирования: определение количества продуктов для получения максимального дохода от реализации, расчет цены для минимальной общей стоимости затрат на производство с помощью графического и симплекс-метода. Решение транспортных задач.
курсовая работа [519,5 K], добавлен 06.05.2011Составление линейной оптимизационной модели и ее решение графическим методом. Сетевое и календарное планирование, расчет и представление на графике временных характеристик событий. Управление запасами, расчет наиболее выгодного режима работы завода.
контрольная работа [1,5 M], добавлен 15.11.2010Основные подходы к математическому моделированию систем, применение имитационных или эвристических моделей экономической системы. Использование графического метода решения задачи линейного программирования для оптимизации программы выпуска продукции.
курсовая работа [270,4 K], добавлен 15.12.2014Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Характеристика графических методов решения задачи линейного программирования, сущность их геометрической интерпретации и основные этапы.
курсовая работа [609,5 K], добавлен 17.02.2010
