Линейное геометрическое программирование

Санкт-Петербургский  Государственный Политехнический  университет

Механико-Машиностроительный факультет

Кафедра информационных технологий в машиностроении

Отчет

по лабораторной работе 
 
 
 
 

Дисциплина: Вычислительная математика

Тема: Линейное геометрическое программирование

Вариант №1 
 
 
 
 
 
 

Студент гр. 2041/3                      Остапчук М. В.      

Преподаватель    Щенев В. В,     

                                                                       

                                                                     «___»  ___________ 2011 г. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Санкт-Петербург

2011 

Цель  работы:

Ознакомиться  с методами линейного программирования и получить навыки решения простейших задач путем их геометрической интерпретации  с использованием вычислительной системы  MathCad. 

Задание:

Найти минимум  целевой функции при заданных ограничениях. 

целевая функция

1 ограничение

2 ограничение

3 ограничение

 
 

 
 

 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнение  задания 

Рассмотрим производственную задачу:

      Пусть некоторая фирма изготавливает 2 вида красок. Цена одной тонны первой краски равна 2 тыс.руб, а второй – 3 тыс.руб. Нужно определить оптимальный  суточный объем производства в тоннах для первой краски – x и второй краски – y. В качестве целевой функции выберем суммарный суточный доход фирмы z = 2x + 3y, который надо минимизировать при следующих ограничениях на расход материалов: 

 
 
 
 
 
 
 

     Таким образом, мы приходим к следующей  математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется  найти такое, при котором функция  z принимает минимальное значение.

      Найдем  решение сформулированной задачи, используя  ее геометрическую интерпретацию. Сначала  определим многоугольник решений. Для этого в неравенствах системы  ограничений и условиях неотрицательности  переменных знаки неравенств заменим  на знаки точных равенств и построим соответствующие прямые. Пересечение  полученных полуплоскостей определяет многоугольник ABC решений данной задачи. 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Чтобы найти  точку, в которой функция x принимает минимальное значение, построим вектор c = (2,3) и прямую 2x + 3y = h, где h – некоторая постоянная такая, что прямая 2x + 3y = h имеет общие точки с многоугольником решений. Построим прямую 2x + 3y = 3. Для нахождения минимального значения целевой функции задачи передвигаем прямую в направлении, противоположном направлению вектора c. Минимальное значение целевая функция принимает в любой точке отрезка AB. 

Найдем с помощью MathCad координаты точки A

Определяем целевую  функцию

Оптимальное значение целевой функции

 
 
 
 
 
 
 
 
 
 
 
 
 
 

Проанализируем  влияние начальных условий на оптимальное решение.

      При уменьшении ресурса 2x + y с 5 т/сутки до 4 т/сутки происходит уменьшение оптимального значения с 5 до 4 тыс.руб/сутки. 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Вывод: без изменения оптимального значения целевой функции ресурс x + y может быть снижен с 5 до 2.5 т/сутки.