Решение задачи линейного программирования - задачи о ресурсах

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

       Элементы  главной строки: 

           (8)

     

           (9) 

       Главный элемент:

     

         (10)

       Элементы  главного столбца: 

     

         (11)

     

         (12) 

       Все остальные элементы таблицы: 

     

        (13)

     

        (14)

     

        (15)

     

        (16) 

       При решении задачи программирования необходимо применять следующие рекомендации:

1. если в главном столбце пересчитываемой таблицы стоит нуль, то соответствующая ему строка переписывается в новую симплексную таблицу без изменений;
2. если в главной строке пересчитываемой таблицы стоит нуль, то соответствующий ему столбец переходит в новую таблицу без изменений;
3. если из числа базисных исключается искусственная переменная, то соответствующий ей столбец в новую симплексную таблицу не включается и, следовательно, не пересчитывается. Искусственные переменные вводятся только для получения исходного базисного плана. Впоследствии они выводятся из базиса и в число базисных больше не попадут.
6. Проверяем правильность расчета значений целевой функции и оценок по формулам. Переходим к шагу 2.

 

2 РАСЧЕТНО-АНАЛИТИЧЕСКАЯ  ЧАСТЬ 

       2.1 Содержательная постановка  задачи линейного

программирования 

       При производстве двух видов продукции используется 4 типа ресурсов.

       Норма расходов ресурсов на производство единицы продукции, общей объем каждого ресурса задан в таблице 1. 

Таблица 1

 

       Прибыль от реализации одной единицы продукции первого вида составляет 3 ден. ед., второго вида – 2 ден. ед.

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

       Что произойдет, если решать задачу на минимум, и почему? 

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

       Построение  модели начнем с обозначения неизвестных.

       Обозначим через - количество продукции S₁, а через - количество продукции S₂.

       Процесс построения оптимизационных математических моделей можно условно разделить на четыре основные этапа:

1. выбор объекта исследования;
2. определение цели исследования;
3. выбор критерия оптимальности;
4. выявление основных ограничений.

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

       Цель  исследования – формирования производственной программы выпуска продукции, обеспечивающей максимальную прибыль от ее реализации.

       Критерий  оптимальности – максимальную прибыль  от реализации продукции. Запишем формально этот критерий. Известно что доход от реализации единицы продукта S₁ составляет 3 ден. ед., а количество этой продукции S₁ составит ден. ед. Следовательно, доход от реализации всей продукции S₁ составит . Доход от реализации единицы продукции S₂ составляет 2 ден. ед., а  количество этой продукции – . Следовательно, доход от реализации всей продукции S₂ составит ден. ед. Учитывая, что доход от реализации S₁ и S₂ должен быть максимальным, критерий задачи будет иметь вид:

       Известно  также, что имеющиеся на предприятии  ресурсы ограничены. Это обстоятельство в свою очередь необходимо отразить в модели.

       Предприятие производит продукцию, используя четыре вида ресурсов. Естественно, что фактический расход каждого вида ресурса не должен превышать запаса соответствующего вида ресурса на предприятии. Поскольку расход каждого вида ресурса на единицу каждого вида продукции и запасы ресурсов известны, это обстоятельство отражается в следующих ограничениях: 

       Смысл первого ограничения состоит  в том, что фактический расход ресурса l₁ на производство продукции S₁ и S₂ не должен превышать запасы этого ресурса на предприятии. Аналогичный смысл имеют второе, третье, четвертое ограничения только для ресурсов l₂ и l₃ и l₄ соответственно.

       Количество  продукции, выпускаемое предприятием, должно быть величиной положительной или равной 0. Следовательно, в модели должно присутствовать ограничения не отрицательности переменных:

 и 

       В целом данная задача об использовании  ресурсов может быть представлена моделью: 

 

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

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

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

       Решим графическим методом задачу линейного программирования с двумя переменными: 

 

       Начнем  решение задачи с построения области  ее допустимых решений. В первую очередь  отобразим в прямоугольной системе  координат условия не отрицательности переменных. В двумерном пространстве уравнению соответствует прямая, а неравенству – полуплоскость, лежащая по одну сторону от прямой. Построим прямые:

 и 

которые лежат на границах полуплоскостей и  совпадают с осями координат. Полуплоскости:

 и 

лежат соответственно справа от оси 0х₁ и выше оси 0x₂. Множество точек, удовлетворяющих одновременно неравенствам:

 и ,

представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадает с точками первой четверти.

       Построим  первую полуплоскость, которая задается неравенством:

,

для этого  определим границу полуплоскости прямую l₁. Прямая l₁ описывается уравнением:

.

       Чтобы построить прямую l₁ необходимо задать две точки и .

       Построим  вторую полуплоскость, которая задается неравенством:

,

для этого определим границу полуплоскости прямую l₂. Прямая l₂ описывается уравнением:

.

       Чтобы построить прямую l₂ необходимо задать две точки и .

       Построим  третью полуплоскость, которая задается неравенством:

.

для этого  определим границу полуплоскости прямую l₃. Прямая l₃ описывается уравнением:

       Чтобы построить прямую l₃ необходимо задать две точки и .

       Построим  четвертую полуплоскость, которая задается неравенством:

,

для этого определим границу полуплоскости прямую l₄. Прямая l₄ описывается уравнением:

       Чтобы построить прямую l₄ необходимо задать две точки и .

       Методом пробной точки определяем полуплоскость, соответствующую данным неравенствам. Выбираем точку, не лежащую на прямой l₁, например, (0;0) и, подставив ее координаты в первое неравенство, получим:

       Точка (0;0) не лежит в искомой полуплоскости. Выбираем точку, не лежащую на прямой l₂, например, (0;0) и, подставив ее координаты во второе неравенство, получим:

       Точка (0;0) лежит в искомой полуплоскости. Выбираем точку, не лежащую на прямой l₃, например, (0;0) и, подставив ее координаты в третье неравенство, получим:

       Точка (0;0) лежит в искомой полуплоскости. Выбираем точку, не лежащую на прямой l₄, например, (0;0) и подставив ее координаты в первое неравенство, получим:

       Точка (0;0) не лежит в искомой полуплоскости.

       Построим  графически целевую функцию. Прямая f=0 описывается уравнением:

чтобы построить  прямую необходимо задать две точки: и .

       В общем случае f = 0 это семейство прямых (линий), каждая из которых представляет линию уровня параллельны друг другу. Для определения направления возрастания значений целевой функции f построим вектор (градиент)