 |
Графический метод решения задач
|
|
|
|
При наличии в задаче линейного программирования двух переменных, а в системе ограничений — неравенств она может быть решена графическим методом [14].
В системе координат Х1ОХ2 находят область допустимых решений, строят нормальный вектор 
и линию уровня. Перемещая линию уровня по направлению для задач на максимум, находим наиболее удаленную от начала координат точку и ее координаты. В том случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины и являются целочисленным решением. Аналогично решается задача на минимум.
Прогнозирование эффективного использования производственных площадей
Рассмотрим следующую задачу.
Задача 6. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего принято решение об установке в одном из цехов дополнительного оборудования, занимающего 19/3м2 площади. На приобретение дополнительного оборудования фирма выделила 10 усл. ед., при этом она может купить оборудование двух видов. Приобретение одного комплекта оборудования 1-го вида стоит 1,0 усл. ед., 2-го вида — 3 усл. ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 шт., а одного комплекта оборудования 2-го вида — на 4 шт. Зная, что для установки одного комплекта оборудования 1-го вида требуется 2 м2 площади, а для оборудования 2-го вида — 1м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.
|
|
|
Решение. Составим математическую модель задачи. Предположим, что фирма приобретает х 1комплектов дополнительного оборудования 1-го вида и х 2комплектов оборудования 2-го вида. Математическая модель задачи будет иметь вид
при ограничениях:
 |
Рисунок 20
Получим задачу целочисленного программирования, так как неизвестных только два (x 1и x 2). Найдем решение задачи графическим способом. ОABC — область допустимых решений (ОДР). Оптимальное решение задача имеет в точке В(9/5,41/15), при этом максимальное значение целевой функции составляет 218/15 ед. Полученное оптимальное решение нецелочисленное. Условию целочисленности переменных удовлетворяют координаты 12 точек. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОABC многоугольником OKEMRNF, содержащим все допустимые точки с целочисленными координатами. Строим вектор (2,4). Линию уровня перемещаем по направлению , получим в точке Е (1, 3) максимальное значение целевой функции: 
= 2 · 1+ 4 · 3 = 14 усл. ед.
Таким образом, фирме следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида, что обеспечит ей при имеющихся ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции, равное 14 усл. ед. в смену.
Метод Гомори
Решим эту же задачу методом Гомори, ее математическая модель:
при ограничениях:
Таблица 21 - Симплексная таблица задачи.
| БП | ci | bi | ||||
| А 1 | А 2 | А 3 | А 4 | |||
| А 3 | 19/3 |  1
| ||||
| А 4 | ||||||
| -2 | -4 | ||||
| А 3 |  5/3
| -1/3 | ||||
| А 2 | 10/3 | 1/3 | 1/3 | |||
| 40/3 | -2/3 | 4/3 | |||
| А 1 | 9/5 | 3/5 | -1/5 | |||
| А 2 | 41/15 | -1/5 | 2/5 | |||
|
| 218/15 | 2/5 | 6/5 |
Получим 
= (9/5,41/15), L (
)= 218/15.
|
|
|
Найдем дробные части чисел 9/15 и 41/15:
Учитывая дробные части чисел 3/5 и —1/5:
составляем дополнительное ограничение целочисленности для 1-й строки: 3/5 x 3 + 4/5 x 4 ≥4/5, или 3/5 x 3 + 4/5 x 4 - х5 = 4/5, которое вводим в таблицу. Получим 
цел = (1,3), L () = 14.
Сравнивая полученное значение целевой функции целочисленного решения со значением при оптимальном решении, заметим, что условие целочисленности задачи приводит к уменьшению значения целевой функции [19].
Таблица 22 - Окончательная симплексная таблица.
| БП | ci | bi | |||||
| А 1 | А 2 | А 3 | А 4 | А 5 | |||
| А 1 | 9/5 | 3/5 | -1/5 | ||||
| А 2 | 41/15 |  -1/5
| 2/5 | ||||
| 4/5 | 3/5 | 4/5 | -1 | ||||
| А 1 | -1 | ||||||
| А 2 | 2/3 | -1/3 | |||||
| А 3 | 4/3 | 4/3 | -5/3 | ||||
|
| 2/3 | 2/3 |
Ответ. цел. = (1,3), L () = 14.
|
|
|
