Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I Цели и задачи изучения дисциплины
  2. I. Характеристика проблемы, на решение которой направлена подпрограмма
  3. I. Характеристика проблемы, на решение которой направлена Программа
  4. I. Характеристика проблемы, на решение которой направлена Программа
  5. II Разрешение космологической идеи о целокупности деления данного целого в созерцании
  6. II. Основные задачи и функции деятельности ЦБ РФ
  7. II. Основные задачи и функции медицинского персонала

Создание модели в MS Excel предполагает использование надстройки «Поиск решения». Сначала мы решаем модель при удалении всех условий, получив, таким образом, задачу линейного программирования (ЛП). Такова общепринятая практика для очень больших моделей, т.к. задачи линейного программирования намного легче решить, чем задачи целочисленного программирования (ЦП). В данном случае это проиллюстрирует некоторые общие отношения между решением задачи линейного программирования (ЛП-решением) и задачи целочисленного программирования (ЦП-решением). ЛП-решение показано на рисунке 4.5.

  A B C D E F G H I
  Варианты прибыли А В С   Альтернативы А В С
  Уч 1         Уч 1      
  Уч 2         Уч 2      
  Уч 3         Уч 3     0,52
  Уч 4         Уч 4      
                   
                   
  Затраты А В С   Доход      
  Уч 1         40,89      
  Уч 2                
  Уч 3         Затраты   Бюджет  
  Уч 4           <=    

 

Рисунок 4.5 – Решение задачи ЛП в MS Excel

Диапазон ячеек G2:I5 представляет переменные решения.

Диапазон ячеек B2:D5 представляет переменные решения

Диапазон ячеек B9:D12 представляет переменные решения

Целевая функция задается в ячейке F9 формулой

F9 = СУММПРОИЗВ(B2:D5;G2:I5).

Затраты вычисляются в ячейке F12 формулой

F12 = СУММПРОИЗВ(B9:D12;G2:I5).

 

Надстройка «Поиска решения» имеет следующий вид (Рис.4.6 a,b):

a)

b)

Рис. 4.6. Решение задачи ЛП с помощью надстройки «Поиск решения»

 

После нажатия кнопки «Выполнить» «Поиск решения» находит максимальное значение функции, заданной формулой в ячейке F9, за счет изменения ячеек диапазона G2:I5 (Чтобы задать диапазон изменяемых ячеек, достаточно установить курсор в окно «Изменяемые ячейки», а затем, перейдя на основную таблицу, установить курсор «мыши» на ячейку G2 и, удерживая нажатой левую клавишу, «протянуть» курсор до ячейки I5).

Ограничениями являются неравенства F12 ≤ H12 (затраты не превышают бюджета) и G2:I5 ≤ 1 (значения ячеек в указанном диапазоне, отражающие факт использования данного участка для каждого проекта, не превышают 1) (Рис. 4.6a). (Чтобы задать эти ограничения, надо нажать кнопку «Добавить» и в открывшемся диалоговом окне указать ячейки или диапазоны, а также знак равенства или неравенства). Условие неотрицательности, относящееся к «изменяемым ячейкам», задано в окне «Параметры» (рис. 4.6b). Отметим, что условие целочисленности пока не включено в ограничения.

Решение задачи ЛП (рис.4.5.):

z = 40.89, A1 = 1, B3 = 1, B4 = 1, C1 = 1, C3 = 0.52.

Равенство F12=H12 показывает, что такое решение использовало бы весь свой бюджет.

Модель ЛП является редукцией модели ЦП, потому что снято одно из ограничений модели ЦП, а именно требование целочисленности значений переменных. Ошибочно считать, что округление решения ЛП-задачи позволит получить целочисленное решение. В нашем случае С3 округляется до 1, что дает невозможное решение, потому что оно нарушает бюджетное ограничение. Округление С3 до 0 дает возможное решение, но оно не является оптимальным ЦП-решением. В общем случае округление нецелочисленных оптимальных решений задачи ЛП до целого не обеспечивает оптимальное решение задачи ЦП. В более сложных задачах часто бывает трудно найти возможные решения путем округления.

Обратим внимание на то, что в найденном решении все переменные кроме одной принимают целое значение, хотя целые значения и не заданы условиями. Это происходит потому, что, как отмечено выше, оптимальное решение задачи ЛП находится на границе ОДР и является одним из базисных решений, а базисные решения имеют столько же базисных переменных, сколько существует ограничений. Каждая небазисная переменная находится на верхней (1) или нижней (0) границе, в то время как базисным переменными могут придаваться дробные значения. С одним ограничением можно было бы ожидать не более одного дробного значения, как мы видим в нашем случае. Вполне возможно, что базисная переменная будет достигать одной из своих границ.


Дата добавления: 2015-07-15; просмотров: 85 | Нарушение авторских прав


Читайте в этой же книге: Этапы системного анализа-синтеза | Классификация систем и инструментов аналитической деятельности | Терминология | Решение и анализ задач ЛП графическим методом | Укрупненный алгоритм решения графическим методом | Пример решения | Анализ чувствительности к изменениям правых частей ограничений | Анализ чувствительности к изменению коэффициентов ЦФ | Целочисленное программирование | Терминология |
<== предыдущая страница | следующая страница ==>
Модели линейного и целочисленного программирования| Решение задачи целочисленного программирования

mybiblioteka.su - 2015-2024 год. (0.006 сек.)