Министерство образования и науки, молодежи и спорта Украины
Сумской государственный университет
Кафедра компьютерных наук
Секция компьютеризованных систем управления
Обязательное домашнее задание №1
по дисциплине: Исследование операций
на тему: «Линейное программирование»
Вариант D5
Выполнил студент
группы СУ-02
Паламарчук А. И.
Проверил: Журба В. О.
Сумы 2011 г.
Обязательное домашнее задание по курсу «Исследование
операций»
Решение задачи состоит из двух этапов:
этап — построить математическую модель (составить систему ограничений в
виде неравенств и задать целевую функцию);
решить поставленную задачу графически;
этап — на основании составленной системы ограничений (первый этап)
записать систему уравнений в стандартной форме записи ЗЛП;
составить симплекс - таблицу и решить задачу симплекс - методом;
сравнить ответы, полученные в этапах 1 и 2.
Вариант d
Завод Electra производит два типа электрических двигателей, каждый на отдельной сборочной линии. Производительность этих линий составляет а1 и а2 двигателей в день. Двигатель первого типа использует в1 единиц некоего комплектующего, а двигатель второго типа в2 единиц этого же комплектующего. Поставщик может обеспечить на день с единиц этого комплектующего. Доходность двигателя первого типа составляет $ d1, второго $ d2. Определите оптимальную структуру ежедневного производства двигателей.
|
Вариант |
а1 |
а2 |
в1 |
в2 |
c |
а1 |
d2 |
|
5 |
500 |
700 |
12 |
8 |
7500 |
60 |
35 |
Графическое решение задачи линейного программирования Теоретические сведения
Графический метод решения задачи линейного программирования.
Графический метод, несмотря на свою очевидность и применимость лишь в случае малой размерности задачи, позволяет понять качественные особенности задачи линейного программирования, характерные для любой размерности пространства переменных и лежащие в основе численных методов ее решения. Поясним графический метод на примере задачи ЛП в основной форме для n = 2
(c, x) → max
Ax ≤ b
, где x = (x1, x2), c = (c1, c2), b = (b1, b2, ..., bm), A - матрица размера (m × 2).
Очевидно, что при данной постановке задачи допустимое множество X в плоскости (x1, x2) представляет собой многоугольник (не обязательно замкнутый), образованный пересечением полуплоскостей H+aibi (где ai - i-я строка матрицы A, i = 1, ..., m), соответствующих ограничениям вида ai1x1 + ai2x2 ≤ bi в исходной задаче. Линии уровня функции f(x) = (c, x) (линией уровня называется множество { }) образуют семейство параллельных прямых Hcα. При этом grad f(x) = c, т.е. градиент целевой функции всюду одинаков и является нормалью каждой из данных полуплоскостей. В соответствии с предыдущим, поиск решения задачи сводится к нахождению максимального числа α* среди всех таких α, что полуплоскость Hcα имеет непустое пересечение с X. При этом - множество решений задачи. При неограниченном решений может и не быть, т.е. при всех .
Из графического представления ясна характерная особенность задачи ЛП (при c ≠ 0): если ее решение существует, то оно достигается обязательно на границе. Отметим, что в рассмотренной задаче ЛП на максимум при поиске α* происходит как бы перемещение прямой Hcα в направлении вектора c. Если же решается задача ЛП на минимум, и, следовательно, ищется минимальное α*, удовлетворяющее указанным требованиям, то Hcα перемещается в направлении, противоположном вектору c.