Линейное программирование


Линейное программирование

Постановка задачи:

  1. Решить задачу линейного программирования в MS Excel с помощью Поиска решения.
  2. Показать графически область допустимых значений и целевую функцию.

Найдем максимум функции  F = -2X1 + 2X2→max  при ограничениях:
X1+ X2 ≥1
-5X1 + X2 ≥0,3
X1 – X2 ≤1
X1 + X2 ≤6
X1 ≥0
X2 ≥0
Сформируем страницу электронной таблицы и постановку задачи линейного программирования в диалоговом окне Поиск решения

После выполнения поставленной задачи, получаем следующие значения переменных. Как видим, при найденных значениях х12 целевая функция принимает минимальное значение, равное 2 и этому удовлетворяют все ограничения поставленной задачи.

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

Решение нижеприведенных задач дается во Flash-роликах, которые Вы можете скачать совершенно бесплатно.

Симплекс-метод

Постановка задачи:

  1. Необходимо найти такие Х1 и Х2, которые удовлетворяют всем условиям и доставляют максимум критерию L:

    \[\begin{array}{l} L = 5{x_1} + 3{x_2} \to \max \\ \left\{ \begin{array}{l} 3{x_1} + 5{x_2} \le 15\\ {x_1} + {x_2} \ge 2\\ 5{x_1} + 2{x_2} \le 10\\ \forall {x_i} \ge 0 \end{array} \right. \end{array}\]

 Этапы решения (выборочно):

Преобразование неравенств в равенства (шаг 3)

Шаг 3

Заполнение начальной таблицы (шаг 4)

Шаг 4

Этапы решения (Flash-ролик) можно скачать совершенно бесплатно     

Транспортная задача

Транспортная задача является одной из наиболее распространённых задач линейного программирования и находит широкое практическое приложение.

Постановка транспортной задачи.

Некоторый однородный продукт, сосредоточенный у k поставщиков Аi в количестве а(i = 1,…,k) единиц, необходимо доставить потребителям Bj в количестве b(j=1, …, nед. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Обозначим через  xij  количество единиц груза, запланированных к перевозке от i-го  поставщика  к  j-му  потребителю. Так как от i-го  поставщика  к  j-му  потребителю запланировано к перевозке  xij  единиц  груза, то стоимость  перевозки составит  сij  xij.

Стоимость всего плана выразится двойной суммой 

    \[Z = \sum\limits_{i = 1}^k {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } \]

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены: 

    \[\sum\limits_{j = 1}^n {{x_{ij}} = {a_i}} ,{\rm{    }} i = 1,...,k\]

б) все потребности должны быть удовлетворены: 

    \[\sum\limits_{i = 1}^k {{x_{ij}} = {b_i}} ,{\rm{    }} j = 1,...,n\]

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

    \[Z = \sum\limits_{i = 1}^k {\sum\limits_{j = 1}^n {{c_{ij}}{x_{ij}}} } \]

Найти минимальное значение линейной функции при следующих ограничениях:

    \[\begin{array}{l} \sum\limits_{j = 1}^n {{x_{ij}} = {a_i}} ,{\rm{ }} i = 1,...,k\\ \sum\limits_{i = 1}^k {{x_{ij}} = {b_i}} ,{\rm{ }} j = 1,...,n\\ {x_{ij}} \ge 0, i = 1,...,k, j = 1,...,n \end{array}\]

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям: 

    \[\sum\limits_{i = 1}^k {{a_i}}  = \sum\limits_{j = 1}^n {{b_j}} \]

Транспортная задача, в которой суммарные запасы и потребности совпадают, называется закрытой моделью; в противном случае–открытойДля открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности: 

    \[\sum\limits_{i = 1}^k {{a_i}}  > \sum\limits_{j = 1}^n {{b_j}} \]

б) суммарные потребности превышают суммарные запасы: 

    \[\sum\limits_{i = 1}^k {{a_i}}  < \sum\limits_{j = 1}^n {{b_j}} \]

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

Для случая а) 

    \[\begin{array}{l} \sum\limits_{j = 1}^n {{x_{ij}} \le {a_i}} ,{\rm{ }} i = 1,...,k\\ \sum\limits_{i = 1}^k {{x_{ij}} = {b_j},{\rm{ }}j = 1,...n, {\rm{ }}{x_{ij}} \ge 0} \end{array}\]

Для случая б) 

    \[\begin{array}{l} \sum\limits_{j = 1}^n {{x_{ij}} = {a_i}} ,{\rm{ }} i = 1,...,k\\ \sum\limits_{i = 1}^k {{x_{ij}} \le {b_j},{\rm{ }}j = 1,...n, {\rm{ }}{x_{ij}} \ge 0} \end{array}\]

Открытая модель решается приведением к закрытой модели.

В случае (а) , когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребность которого:

    \[{b_{n + 1}} = \sum\limits_{i = 1}^k {{a_i} - } \sum\limits_{j = 1}^n {{b_j}} \]

В случае (б) , когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Ak+1, запасы которого:

    \[{a_{k + 1}} = \sum\limits_{j = 1}^n {{b_j}}  - \sum\limits_{i = 1}^k {{a_i}} \]

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

Постановка задачи

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

ai \ bj

45

45

100

160

180

6

7

3

2

90

5

1

4

3

170

3

2

6

2

Проверка на сбалансированность

Правило северо-западного угла

Все этапы решения (Flash-ролик) можно скачать совершенно бесплатно    

Целочисленное программирование

Постановка задачи:

  1. Необходимо найти такие Х1 и Х2 , которые удовлетворяют всем условиям и доставляют максимум критерию L, причем Х1 и Х2 должны быть целыми числами:

    \[\begin{array}{l} L = 9{x_1} + 5{x_2} \to \max \\ \left\{ \begin{array}{l} 3{x_1} - 6{x_2} \ge 1\\ 5{x_1} + 2{x_2} \le 28\\ \forall {x_i} \ge 0 \end{array} \right. \end{array}\]

Этапы решения (Flash-ролик) можно скачать совершенно бесплатно  

Смотри также по теме: