Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
Высшего образования
«Тульский государственный университет»
Институт прикладной математики и компьютерных наук
КАФЕДРА ИБ
Методы оптимизации
Методические указания к выполнению курсовой (контрольной) работы для студентов заочной формы обучения
Направление (специальность) подготовки: 09.03.03 Прикладная информатика
Профиль (специализация) подготовки: Прикладная информатика в промышленности
Тула 2016 г.
Методические указания составлены доцентом Г.В. Басаловой и обсуждены на заседании кафедры ИБ,
протокол №___ от «_____» ______ 2016 г.
Зав. кафедрой _________________ А.А.Сычугов
ЦЕЛЬ ВЫПОЛНЕНИЯ РАБОТЫ
Курсовая работа предназначена для закрепления навыков решения задач по основным разделам дисциплины методы оптимизации.
Задание на работу
В курсовой работе необходимо решить три задачи:
— задача №1: тема «Задачи линейного программирования с двумя неизвестными. Графический метод решения»;
— задача №2: тема «Задачи линейного программирования. Симплексный метод решения»;
— задача №3: тема «Транспортные задачи».
В данных методических указаниях сначала приведены варианты заданий для задачи 1, а затем – для задачи №2, затем – для задачи №3.
Варианты задач выбираются по номеру студента в списке. Студентам, выполнившим не свой вариант (или вариант, совпадающий с вариантом другого студента) будет выдано новое задание.
Требования по оформлению приведены после вариантов заданий.
Краткие теоретические положения
Линейное программирование (ЛП) является наиболее простым разделом дисциплины «Методы оптимизации».
Задача линейного программирования представляет собой частный случай задачи оптимизации при наличии ограничений, который характеризуется тем, что
а) целевая функция является линейной;
б) система ограничений, выделяющая допустимую область решений, представляет собой систему линейных неравенств (или равенств).
Общая форма записи модели задачи ЛП
Целевая функция (ЦФ) , при ограничениях  | (1.1) |
Допустимое решение– это совокупность чисел (план) , удовлетворяющих ограничениям задачи (1.1).
Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение.
В некоторых случаях ограничивающие условия могут содержать как неравенства, так и равенства (смешанные ограничения). Если же все ограничения задачи ЛП (ЗЛП) заданы в виде строгих равенств, то такая форма называется канонической.
Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник. Каждая вершина этого многогранника определяет опорный план. В одной из вершин многогранника решений (т. е. для одного из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Если максимальное значение функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более двух переменных.
