Графический способ решения задач линейного программирования



Скачать 75.58 Kb.
Дата11.05.2016
Размер75.58 Kb.
Лабораторная работа

ГРАФИЧЕСКИЙ СПОСОБ РЕШЕНИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


Цель работы:

1) Ознакомиться с моделью общей задачи линейного программирования.

2) Научиться составлять экономико-математические модели линейных задач.

3) Ознакомиться с технологией решения задач линейного программирования графическим способом



1.Общие сведения

Задача линейного программирования, задаваемая в общей форме, формулируется следующим образом: найти экстремальное значение целевой функции

при условиях

Если целевая функция (1) максимизируется при условии, что все ограничения имеют вид неравенств (2), т.е. s=m , и все переменные (4) неотрицательны, то такую задачу называют симметричной.

Задача канонической формы ставится так: найти максимальное значение целевой функции (1) при условии (3), когда s=0, и соблюдении ограничений (4).

Геометрическая интерпретация задач дает возможность наглядно представить их структуру, выявить особенности. Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно.

Рассмотрим случай двух переменных:

(5)

Дадим геометрическую интерпретацию элементов этой задачи.

Каждое из ограничений (6), (7) задаёт на плоскости x1Ox2 некоторую полуплоскость. Полуплоскость – выпуклое множество. Напомним, что выпуклым называют множество, которое вместе с любыми своими точками x1 и x2 содержит и все точки отрезка  x1; x2. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений (ОДР) задачи есть выпуклое множество.

Возможны ситуации, когда область допустимых решений ЗЛП



  • выпуклый многоугольник;

  • неограниченная выпуклая многоугольная область;

  • единственная точка;

  • прямая линия;

  • луч;

  • отрезок;

  • пустое множество.

Геометрическая интерпретация целевой функции.

Пусть ОДР задачи ЛП – непустое множество.

Выберем произвольное значение целевой функции , получим . Это уравнение прямой линии. В точках прямой целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции. Найдем частные производные целевой функции по x1 и x2: .

Частная производная функции показывает скорость её возрастания вдоль данной оси. с1 и с2 – скорости возрастания соответственно вдоль осей Ox1 и Ox2. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор указывает направление наискорейшего убывания целевой функции Его называют антиградиентом.

Вектор перпендикулярен к прямой семейства .

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок её графического решения.

1. С учетом системы ограничений строится область допустимых решений.

2. Строится вектор .

3. Проводится произвольная линия, перпендикулярная к вектору .

4. При решении задачи на максимум перемещается линия уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении.

В случае задачи на минимум линия уровня перемещается в антиградиентном направлении.

5. Определяется оптимальный план и экстремальное значение целевой функции .

Возможны следующие случаи:


  • оптимальный план единственный;

  • оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через сторону области допустимых решений;

  • целевая функция неограниченна;

  • область допустимых решений состоит из единственной точки, где целевая функция достигает одновременно и максимального и минимального значения;

  • задача не имеет решения: ОДР – пустое множество, т.е. система ограничений задачи несовместна.

Перейдем к геометрической интерпретации задачи линейного программирования с n переменными.



Множество планов , компоненты которых удовлетворяют ограничению-неравенству , геометрически представляют собой гиперплоскость n-мерного пространства. Это выпуклое множество. Множество планов , компоненты которых удовлетворяют неравенству , образует полупространство n-мерного пространства, которое также является выпуклым множеством. Множество планов, удовлетворяющих системе ограничений ЗЛП, представляет собой пересечение конечного числа полупространств и потому является выпуклым.

Геометрически задача сводится к нахождению точки многогранника (многоугольной области), определяемого неравенствами (9), (10), через которую проходит гиперплоскость семейства (8), соответствующая наибольшему значению F.

Графическим методом можно решить ЗЛП с n>2 переменными, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением .

В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.
Список задач

Задачи с двумя переменными


  1. Найти максимум и минимум линейной функции

При условиях-ограничениях:
























  1. Найти максимум и минимум линейной функции

При условиях-ограничениях:





  1. Найти максимум и минимум линейной функции

При условиях-ограничениях:











  1. Найти максимум и минимум линейной функции

При условиях-ограничениях:







Фирма производит два безалкогольных широко популярных напитка «Колокольчик» и «Буратино». Для производства 1л «Колокольчика» требуется 0,02 ч работы оборудования, а для «Буратино» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Буратино» - 0,35 руб. Определить ежедневный план производства напитков каждого вида, обеспечивающий максимальный доход от их продажи.



На приобретение оборудования для нового производственного участка выделено 20 тыс. ден. ед. Оборудование должно быть размещено на площади, не превышающей 72 м2. Предприятие может заказать оборудование двух видов: более мощные машины типа А стоимостью 5 тыс. ден. ед., требующие производственные площади 6 м2 (с учетом проходов) и дающие 8 тыс. ед. продукции за смену, и менее мощные машины типа Б стоимостью 2 тыс. ден. ед., занимающие площадь 12 м2 и дающие за смену 6 тыс. ед. продукции. Машин типа А можно заказать не более 3 ед. Найти оптимальный вариант приобретения оборудования, обеспечивающий максимум общей производительности нового участка. Ответ: (2;5)

  1. д

Фирма производит и продает столы и шкафы из древесины хвойных и лиственных пород. Расход каждого вида в кубометрах на каждое изделие задан в таблице.




Расход древесины, м3

Цена изделия,

тыс. руб.



хвойные

лиственные

Стол

0,15

0,2

0,8

Шкаф

0,3

0,1

1,5

Запасы древесины

80

40




Определить оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максимального дохода фирмы.



Сельскохозяйственное предприятие может приобрести тракторы марок М1 и М2 для выполнения работ Р1, Р2 и Р3. Производительность тракторов при выполнении указанных работ, общий объём работ и стоимость каждого трактора приведены в таблице. Найти оптимальный вариант приобретения тракторов, обеспечивающий выполнение всего комплекса работ при минимальных денежных затратах на технику.

Вид работ

Объём работ, га

Производительность
трактора марки

М1

М2

Р1

Р2

Р3



60

40

30



4

8

1



3

1

3



Стоимость трактора, ден. ед.

7

2

Задачи с n переменными

Графическим методом можно решать задачу линейного программирования с n>2 переменными, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n-m ≤ 2.

  1. Решить графически









Найти оптимальное сочетание посевов пшеницы и кукурузы на участках различного плодородия площадью 100 и 200 га. Данные об урожайности приведены в таблице. По плану должно быть собрано не менее 1500ц пшеницы и 4500ц кукурузы. Цена 1ц пшеницы 6 ден. ед., кукурузы 4 ден.ед. Критерий оптимальности – максимум валовой продукции в денежном выражении.

Культура

Урожайность (ц/га) участка

I

II

Пшеница

20

15

Кукуруза

35

30






















Указания: решить три задачи графическим методом: две задачи с двумя переменными и одну задачу с n переменными (выбор номеров задач осуществляем преподаватель).


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница