Нахождение целочисленного решения задач линейного программирования.




Цель работы: Использование процедуры «Поиск решения» для нахождения целочисленного решения задач линейного программирования.

Содержание работы:

- найти целочисленное решение заданной задачи линейного программирования.

- определить дефицитное сырье (сырье, которое в процессе работы используется полностью).

- найти зависимость целочисленного решения задачи от количества дефицитного сырья.

- найти зависимость целочисленного решения задачи от технологий (меняя величины затрат дефицитного материала на производство единицы продукции каждого вида).

 

Записываем исходные данные (лаб. раб. №1):

 

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

После введения формул для левых частей ограничений, остатков сырья и целевой функции (лаб. раб. №1) будем иметь:

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               
                   

 

Вызываем процедуру «Поиск решения».Указываем,что целевая функция находится в ячейке F11 и что ее нужно максимизировать.Также указываем на неотрицательность и целочисленность переменных. Записываем ограничения

F3 ≤ E3, F4 ≤ E4, F5 ≤ E5, F6 ≤ E6

 

 

После выполнения вичислений получим:

 

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

 

Наиболее дефицитным является сырье 4-го вида. Находим решение целочисленной задачи для значений М4 ={35; 56; 77; 98; 119; 140; 161}.

Поле выполнения вычислений получим:

 

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               
 
  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

 

Таким образом, имеем зависимость стоимости продукции от сырья 4-го вида (наиболее дефицитного):
 
Сырье Х              
Стоимость У              

 

Выясним степень влияния технологий на оптимальное решение. Для этого изменим величины затрат дефицитного материала:

 

  А B C D E F G
  Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья  
    A B C      
             
             
             
             
               
  Цена ед. продукции            
               
    x1 x2 x3   Целевая ф-ия  
               

 

Сравнивая полученное решение с решением исходной задачи, видим, что технологии сильно влияют на оптимальное решение

 

Лабораторная работа № 4.

 

ТРАНСПОРТНАЯ ЗАДАЧА

 

Цель работы: Использование процедуры «Поиск решения» для составления оптимального плана перевозок.

Содержание работы:

- ввод исходных данных.

- запись формул целевой функции и ограничений для стандартной транспортной задачи.

- нахождение решения стандартной транспортной задачи, используя процедуру «Поиск решения».

- решение транспортной задачи при наличии дополнительных ограничений (ограничение количества перевозимых изделий в определенном направлении, задание количества перевозимых изделий в заданном направлении и т. д.)

 

Постановка задачи: Задана матрица С стоимостей перевозки единицы товара, вектор производства а (количество товара, производимого каждым производителем), вектор потребления b (количество товара, потребляемого каждым потребителем).

 

С = а= (30; 5; 45; 70) b= (10; 35; 16; 25; 35)

 

Составить план перевозок, чтобы суммарные транспортные расходы были минимальными.

 

Решение.

 

Суммарное количество производимого товара равно 150. Суммарное количество потребляемого товара равно 121. Введем фиктивного потребителя с объемом потребления 150-121=29. Стоимость перевозки к фиктивному потребителю возьмем больше любой другой стоимости, например, 10. Тогда исходные данные запишутся:

 

 

С 1= а= (30; 5; 45; 70) b 1 = (10; 35; 16; 25; 35; 29)

 

 

В Excel вводим исходные данные, выделяем место для решений (B10:G13),полагая начальные значения 0 или любые другие числа. Записываем в ячейку I10 формулу для количества товара, вывезенного от 1-го производителя:

 

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                  =cумм(B10:G10)
                   
                   
                   
                   
  Завезено потребителям                

После ввода этой формулы (ENTER) и протаскиванию по ячейкам I11:I13 получим

 

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям                

 

В B15 записываем формулу для количества товара,завезенного 1-му потребителю:

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям =сумм (B10:B13)    
                       

 

После введения формулы и протаскивания на ячейки C15:G15 получим:

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям                

 

 

В I15 записываем формулу для целевой функции

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям             Цел. ф-ия =суммпроизв(B2:F5;B10:F13)

 

 

Введя формулу, получим

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям             Цел. ф-ия  

 

 

Вызываем процедуру «Поиск решения», указываем, что целевая функция должна достичь минимума, что целевая функция находится в ячейке I17 и что изменять нужно ячейки B10:G10. Далее нужно добавить ограничения неотрицательности и целочисленности решений. Также добавим ограничения, указывающие, что весь товар дожжен быть вывезенным от производителей и завезен потребителям (включая фиктивные):

 

I10=H2

I11=H3

I12=H4

I13=H5

B15=B7

C15=C7

D15=D7

E15=E7

F15=F7

G15=G7

После вычислений получим

 

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потребителям             Цел. ф-ия  

 

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

 

Потребит.   Производит.               Остаток
             
             
             
             

 

Транспортные расходы составят 226 д.е.

 

Предположим теперь, что от 3-го производителя обязательно нужно вывезти не менее 30 единиц товара. Тогда нужно записать формулу для подсчета количества товара,вывезенного от 3-го производителя (без учета фиктивного потребителя)

 

  A B C D E F G H I
    Матр. стоимостей Производители    
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                =сумм(B12: F12)  
                   
                   
  Завезено потребителям               Цел. ф-ия  

 

После введения формулы получим

 

  A B C D E F G H I
    Матр. стоимостей Производители    
                   
                   
                   
                   
                   
  Потребители                  
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
  Завезено потребителям             Цел. ф-ия  

 

Вызываем процедуру «Поиск решений».К предыдущим ограничениям нужно добавить

 

H12 ≥ 30. После выполнения решения получим

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
                   
  Потреби- тели                
                   
    Матр. перевозок   Вывезено от производителей
                   
                   
                   
                   
                   
  Завезено потреби- телям             Цел. ф-ия  

 

Предположим теперь, что от 3-го производителя к 4-му потребителю можно завести только 10 единиц товара. Тогда к предыдущим условиям нужно добавить условие

 

E12 = 10

 

После выполнения решения получим:

 

  A B C D E F G H I
    Матр. стоимостей Произво- дители  
                   
                   
                   
                   
  &n


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: