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

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

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

Найдем максимум функции  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

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

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

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

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

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

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

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

    [Z = sumlimits_{i = 1}^k {sumlimits_{j = 1}^n {{c_{ij}}{x_{ij}}} } ]

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

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

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

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

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

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

    [Z = sumlimits_{i = 1}^k {sumlimits_{j = 1}^n {{c_{ij}}{x_{ij}}} } ]

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

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

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

 

    [sumlimits_{i = 1}^k {{a_i}}  = sumlimits_{j = 1}^n {{b_j}} ]

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

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

    [sumlimits_{i = 1}^k {{a_i}}  > sumlimits_{j = 1}^n {{b_j}} ]» width=»109″ height=»56″></p>
<div style=

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

    [sumlimits_{i = 1}^k {{a_i}}  < sumlimits_{j = 1}^n {{b_j}} ]

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

Для случая а) 

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

Для случая б) 

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

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

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

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

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

 

    [{a_{k + 1}} = sumlimits_{j = 1}^n {{b_j}}  - sumlimits_{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

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

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

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

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

  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}]

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...