Решения задач линейного программирования геометрическим методом
Этап 1.
Сначала на координатной плоскости x1Ox2 строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям:
1.6)
Не приводя строгих доказательств, укажем те случаи, которые тут могут получится.
1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 1а).
2. Неосновной случай получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 1б. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение х1 + х 2 ≤ 3. Оставшаяся часть будет неограниченным выпуклым многоугольником.
|
|
|
Наконец, возможен случай, когда неравенства (1.6) противоречат друг другу, и допустимая область вообще пуста.
Рассмотрим теорию на конкретном примере:
Найти допустимую область задачи линейного программирования, определяемую ограничениями
1.32)

Решение:
1. Рассмотрим прямую –x1+x2 = 1. При x1 = 0, x2 = 0, а при x2= 0, x1= -1. Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря x1 = x2 = 0, получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.а.
2.
Рассмотрим
прямую
. При
, а при . Таким
образом, эта прямая проходит через точки (0, -1/2) и (1,0). так как
(4.б).
3.
Наконец,
рассмотри
м прямую
. Она проходит через
точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит
ниже прямой, изображенной на рис. 4.в.
Сводя все вместе и добавляя условия х1 ≥ 0,х2 ≥ 0 получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения (1.32). Обратим внимание на то, что получившаяся область имеет вид выпуклого многоугольника.

Этап 2.
Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция с1х1+с2х2 =>max.
|
Рассмотрим прямую с1х1+с2х2 = L. Будем увеличивать L. Что будет происходить с нашей прямой?
Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (с1,с2), так как это вектор нормали к нашей прямой и одновременно вектор градиента функции
f(х1,х2) = с1х1+с2х2 .
А теперь сведем всё вместе. Итак, надо решить задачу

![]()
Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая с1х1+с2х2 = L пересекает допустимую область. Это пересечение дает какие-то значения переменных (х1,х2), которые являются планами.
Этап 3
Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 7). В конце концов эта прямая выйдет на границу допустимой области как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с1х1+с2х2 = L с допустимой областью будет пустым. Поэтому то положение прямой с1х1+с2х2 = L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.

Рис. 7
II. ПРАКТИЧЕСКИЙ РАЗДЕЛ
Задача №1
Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице 1.1..
Таблица 1.1.
| Вид сырья |
|
Общее количество сырья, кг |
| I | 12 4 | 300 |
| II | 4 4 | 120 |
| III | 3 12 | 252 |
| Прибыль от реализации одного изделия, ден. ед. | 30 40 | ? |
Составить такой план выпуска продукции, при котором прибыль предприятия
от реализации продукции будет максимальной при условии, что изделие В надо
выпустить не менее, чем изделия А.
Решение.
Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х1 +4 х2) единиц ресурса I, (4х1 +4х2) единиц ресурса II, (3х1 +12х2) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
![]()
12х1 +4х2 ≤ 300;
3х1 + х2 ≤
75; ![]()
4х1 +4х2 ≤ 120;
х1 + х2 ≤ 30;
3х1 +12х2 ≤ 252. х1 +4х2 ≤ 84.
По смыслу задачи переменные х1 ≥ 0, х2 ≥0. (1,1)
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.
Суммарная прибыль А составит 30х1 от реализации продукции А и 40х 2 от реализации продукции В, то есть : F = 30х1 +40х 2. (1,2)
Изобразим многоугольник решений данной задачи.
В ограничениях задачи поменяем знаки неравенства на знаки равенства.
Проведем оси: на горизонтальной будут указываться значения переменной х1, а на вертикальной — х2 .Далее рассмотрим условие неотрицательности переменных: x1 ≥ 0 и х2 ≥ 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е выше оси x1 и правее оси х2).
Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:
3х1 + х2 = 75;
х1 + х2 = 30;
х1 +4х2 = 84.
а затем на плоскости провести эти прямые.
Например, неравенство 3х1 + х2 ≤ 75 заменяется уравнением прямой 3х1 + х2 = 75. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой Можно положить х1 = 0, тогда х2 = 75/1 = 75.. Аналогично для х2 = 0 находим x1 = 75/3 = 25. Итак, наша прямая проходит через две точки (0, 75) и (25;0). Аналогично найдём остальные точки и запишем их в таблицу 1.2..
Таблица 1.2.
| 3х1 +х2 ≤ 75; | х1 +х2 ≤ 30; | х1 +4х2 ≤ 84. | |||
| х1 | х2 | х1 | х2 | х1 | х2 |
| 0 | 75 | 0 | 30 | 0 | 21 |
| 25 | 0 | 30 | 0 | 84 | 0 |
Согласно данной таблицы, построим график в программе Excel.

Заштрихованная область, изображённая на рисунке, является областью допустимых значений функции F. Т.к. целевая функция F стремиться к max, то идя по направлению вектора n, получим точку B с оптимальным решением. Для определения ее координаты возьмем две прямые, на пересечении которых она образуется:
![]()
![]()
3х1 + х2 ≤ 75,
х1 = 19,64, ![]()
х1 + 4х2 ≤ 84, х2 = 16,09. , т. е. B(16,09; 19,64)
максимальное значение линейной функции равно :
Fmax = 30*16,09 + 40*19,64 = 1232,80.
Итак, Fmax = 1232,80 при оптимальном решении х1 = 16,09, х2 = 19,64, т. е. максимальная прибыль в 1232,80 ден. ед. может быть достигнута при производстве 16,09 единиц продукции А и 19,64 единиц продукции В.
Ответ: Fmax = 1232,80.
Задача № 2
Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а также величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 2.1.
Таблица 2.1.
| Вид сырья | Запас сырья | Количество единиц сырья, идущих на изготовление единицы продукции | |
| Р1 | Р2 | ||
| S1 | 20 | 2 | 5 |
| S2 | 40 | 8 | 5 |
| S3 | 30 | 5 | 6 |
| Прибыль от единицы продукции, руб. | 50 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: | |