Green-sell.info

Новые технологии
3 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Решение происходит в три этапа:

  1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
  2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
  3. Решение симплексным методом;
  • Решение онлайн
  • Видеоинструкция
  • Оформление Word

Переход от задачи минимизации целевой функции к задаче максимизации

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

Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x1 + 2x2 — 2x3 → min при ограничениях:
4x1 + 3x2 — x3≤10
— 2x2 + 5x3≥3
x1 + 2x3=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x4; во втором неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
4x1 + 3x2-1x3 + 1x4 + 0x5 = 10
0x1-2x2 + 5x3 + 0x4-1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = — x1 — 2x2 + 2x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

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

Двойственные или сопряженные задачи линейного программирования обладают тем свойством, что из решения одной из задач можно получить решение другой задачи. Здесь мы рассмотрим правила составления двойственных задач.

Симметричная двойственная задача

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(1.1) ;
(1.2)
Здесь , , есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками .

Двойственная задача имеет вид:
(2.1) ;
(2.2)
Здесь все строки системы (2.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит строк и столбцов. Двойственная задача имеет переменных . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) – двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) – двойственной. Задачи (1) и (2) называются симметричными двойственными задачами.

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

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

Дана задача линейного программирования:
;

Составить двойственную задачу.

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Первое и третье неравенства содержат знак . Умножим их на –1 :

Перепишем систему ограничений, явно указывая коэффициенты при переменных:

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, третью строку запишем как третий столбец.

Двойственная задача имеет вид:
;

Несимметричная двойственная задача

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с неотрицательными переменными и равенствами системы ограничений:
(3.1) ;
(3.2)
Здесь , , есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.

Двойственная задача имеет вид:
(4.1) ;
(4.2)
Здесь все строки системы (4.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (4.2) является транспонированной матрицей системы (3.2). Двойственная задача имеет переменных . Переменные могут быть как положительными, так и отрицательными.

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1) ;
(5.2)

Двойственная задача имеет вид:
(6.1) ;
(6.2)

Читать еще:  Программирование андроид как хранить данные

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки .

Связь с симметричной парой двойственных задач

Покажем, что несимметричную пару задач (3)-(4) можно получить из симметричной пары (1)-(2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)
и системой ограничений
(3.2)
Каждое равенство можно представить двумя неравенствами:

Неравенства со знаками умножим на –1 :

Система ограничений имеет неравенств.

По формулам (1)-(2) получаем двойственную задачу:
;

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

Сделаем подстановки
.
Поскольку и , то переменные могут быть как положительными, так и отрицательными.

И мы получаем двойственную задачу (4):
(4.1) ;
(4.2)

Если мы за исходную задачу возьмем (4), то, выполняя все действия в обратном порядке, получим двойственную задачу (3).

Тем же способом можно из задачи (5) получить двойственную задачу (6) и из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

Пусть мы имеем прямую задачу (1) на максимум, в системе ограничений которой -я строка является равенством. Тогда двойственная задача имеет вид (2) за одним исключением – переменная может быть как положительной, так и отрицательной. То есть отсутствует ограничение .

То же самое произойдет, если мы имеем прямую задачу (2) на минимум, в системе ограничений которой -я строка является равенством. Двойственная задача имеет вид (1) за одним исключением – переменная может быть любого знака.

Теперь пусть мы имеем прямую задачу (1) на максимум, но отсутствует ограничение . То есть переменная может быть как положительной, так и отрицательной. Тогда двойственная задача имеет вид (2) за одним исключением – -я строка системы ограничений является равенством.

И наконец, пусть мы имеем прямую задачу (2) на минимум, но отсутствует ограничение . Тогда двойственная задача имеет вид (1) за одним исключением – -я строка системы ограничений является равенством.

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

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

1. Для исходной задачи на максимум, все неравенства системы ограничений приводим к виду:
.
Для исходной задачи на минимум, все неравенства приводим к виду:
.
Если требуется поменять знак, то умножаем обе части неравенств на –1 .
2. Составляем двойственную задачу тем же способом, как для симметричной пары задач.
3. Если в исходной задаче, –я строка системы ограничений является равенством, то вычеркиваем условие неотрицательности –й переменной двойственной задачи.
4. Если в исходной задаче, отсутствует условие неотрицательности для –й переменной, , то в –й строке двойственной задачи меняем знак неравенства на знак равенства.

Пример составления смешанной двойственной задачи

Дана задача линейного программирования:
;

Составить двойственную задачу.

Целевая функция имеет свободный член 5. Чтобы привести ее к виду (2.1), введем переменную и добавим равенство . Тогда задача примет вид:

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Третье неравенства содержат знак . Поэтому умножим его на –1 :

Перепишем систему ограничений, явно указывая коэффициенты при переменных:

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, и так далее.

Составим двойственную задачу как для симметричной пары.
;

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные , и могут иметь любой знак. Неотрицательной переменной является только . Поэтому условия неотрицательности переменных имеют вид:
.

Поскольку в исходной задаче переменные и могут иметь произвольные знаки, то 3-я и 4-я строки системы ограничений двойственной задачи являются равенствами.

Таким образом, двойственная задача имеет вид:
;

Из четвертого уравнения . Заменим переменную ее значением и умножим третью строку на –1 .

Автор: Олег Одинцов . Опубликовано: 19-08-2016

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

f(x) = ,

аij xj = bi , i = 1:m, (6.8)

где число переменных на два больше числа ограничений − равенств, т.е. n — m = 2, причем ранг матрицы А= m. Тогда две переменные в указанной системе уравнений, скажем х1 и х2, являются свободными, т.е. через них можно выразить все остальные переменные:

, (6.9)

где − некоторые числа. Подставляя эти выражения в целевую функцию, получаем

где γ1, γ2, δ − некоторые числа.

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

Используя геометрические построения, находим ее решение ( ). Подставляя эти числа в (6.9), (6.10), получаем решение и значение исходной задачи (6.8).

Пример 6.2. Используя графический метод, найти решение

Рис. 6.2. Допустимое множество задачи 6.2

Решение.Изобразим на плоскости (х1, х2) допустимое множество C данной задачи (многоугольник ABCDE, рис. 6.2) и одну из линий уровня —х1 -2х2 = — 3 целевой функции ¦(х). Направление убывания ¦(x) указывает вектор l = (1,2). Совершая параллельный перенос линии уровня вдоль направления l, находим ее крайнее положение. В этом положении прямая —х1 — 2х2 = — 3 проходит через сторону CD полиэдра ABCDE. Таким образом, все точки отрезка CD являются точками минимума функции ¦(х) на множестве X. Так как концы C и D этого отрезка имеют координаты (1,3) и (3,2) соответственно, то любая точка минимума функции ¦(х) представима в виде

Читать еще:  Системой программирования является

где . Минимальное значение целевой функции ¦ * = ¦(х*) = –7.

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

Рис. 6.3. Неограниченное многоугольное множество

Решение.Допустимое множество этой задачи представляет собой неограниченное многоугольное множество (рис. 6.3). Функция f(x) убывает в направлении l = (1,2). При параллельном переносе линии уровня вдоль направления l она всегда пересекает множество Х, а целевая функция f(x) неограниченно убывает. Поэтому рассмотренная задача не имеет решений.

Пример 6.4. Найти максимальное значение функции

при условиях:

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

Из целевой функции исходной задачи исключаем переменные x3, x4, x5 с помощью подстановки их значений из соответствующих уравнений системы ограничений. Получаем постановку задачи в стандартной форме:

f(x) = 2x1 + 3x2,

34.06. П6. Задания по теме Линейное программирование&quot

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

Значения коэффициентов системы ограничений системы неравенств

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

Значения коэффициентов системы ограничений системы неравенств

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

Графическим методом найти оптимальные решения при стремлении целевой функции к максимальному и минималь­ному значениям.

Значения коэффициентов целевой функции и системы ограничений

Составить математическую модель и провести экономичес­кий анализ задачи с использованием графического метода.

6.4. Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исход­ные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице.

Расход и суточные запасы исходных продуктов

Изучение рынка сбыта показало, что суточный спрос на краску для наружных (внутренних) работ никогда не превы­шает B3 т в сутки. Цена продажи 1 т краски для наружных работ — C1 ден. ед., для внутренних работ — C2 ден. ед.

Какое количество краски каждого вида должна произво­дить фирма, чтобы доход от реализации продукции был мак­симальным?

Значения коэффициентов условий задачи

Примечание. Если по условию задания спрос на краску для наружных (внутренних) работ не превышает B3 т в сутки, то в математической модели задачи следует принять, что коэффициент системы ограничений при неизвестном значении краски для наруж­ных (внутренних) работ, обозначенный в таблице K1 (K2), равен 1 (0), а при неизвестном значении краски для внутренних (наружных) ра­бот K2 (K1) равен 0 (1).

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

Решить задачу симплексным методом при стремлении це­левой функции к максимальному и минимальному значениям.

Значения коэффициентов целевой функции и системы ограничений

6.6. Составить математическую модель и решить задачу сим­плексным методом.

В производстве пользующихся спросом двух изделий, А и В, принимают участие 3 цеха фирмы. На изготовление одного изделия А 1-й цех затрачивает A1 ч, 2-й цех — A2 ч, 3-й цех — А3 ч. На изготовление одного изделия В 1-й цех затрачивает D1 ч, 2-й цех — D2 ч, 3-й цех — D3 ч. На производство обоих изделий 1-й цех может затратить не более B1 ч, 2-й цех — не более B2 ч, 3-й цех — не более B3 ч.

От реализации одного изделия А фирма получает доход C1 р., изделия В — C2 р.

Определить максимальный доход от реализации всех изде­лий А и В.

Значения коэффициентов условия задачи

6.7. Дана исходная задача

Составить математическую модель симметричной двойст­венной задачи. По решению двойственной или исходной зада­чи найти решение другой с использованием основных теорем двойственности.

Значения коэффициентов целевой функции и системы ограничений

6.8. Дана исходная задача

Составить математическую модель несимметричной двой­ственной задачи. По решению двойственной или исходной за­дачи найти решение другой с использованием основных теорем двойственности.

Значения коэффициентов целевой функции и системы ограничений

6.9. Решить транспортную задачу, заданную распределитель­ной таблицей

Значения коэффициентов распределительной таблицы

6.10. Решить транспортную задачу, заданную распредели­тельной таблицей

Значения коэффициентов распределительной таблицы

6.11. Составить математическую модель транспортной задачи и решить ее.

Фирма имеет три магазина розничной торговли, располо­женных в разных районах города (А, В, С). Поставки про­дукции в эти магазины осуществляются с двух складов D и Е, площади которых вмещают 30 и 25 т продукции соответ­ственно. В связи с возросшим покупательским спросом фирма планирует расширить площади магазинов, поэтому их потреб­ности в продукции с торговых складов составят 20, 35 и 15 т в день. Чтобы удовлетворить спрос на продукцию, предпола­гается строительство третьего склада, площади которого поз­волят хранить в нем 15 т продукции ежедневно. Руководство фирмы рассматривает два варианта его размещения. В таблице даны транспортные издержки, соответствующие перевозке продукции с двух существующих складов, и два варианта раз­мещения нового склада.

Читать еще:  Язык программирования as

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

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

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

Решить задачу методом Гомори, принимая по своему усмотрению стремление целевой функции к максимальному или минимальному значениям.

Значения коэффициентов целевой функции и системы ограничений

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

Решить задачу симплексным методом.

Значения коэффициентов целевой функции и системы ограничений

6.14. Решить транспортную параметрическую задачу, задан­ную распределительной таблицей

Значения коэффициентов распределительной таблицы

6.15. Решить задачу о назначении с использованием симплекс­ного метода.

Районная администрация финансирует 5 инвестиционных проектов, каждый из которых может быть осуществлен в тече­ние последующих трех лет. В связи с невозможностью финан­сирования в полном объеме определить, какие из инвестици­онных проектов, обеспечивающих максимально чистые приве­денные стоимости, могут быть осуществлены. Затраты, ожи­даемые чистые приведенные стоимости (ЧПС) и ограничения по финансированию проектов приведены ниже.

Таблица заданий по вариантам

Примечание. Задачу целесообразно решать на компьютере.

6.16. Решить задачу о назначениях.

В цехе предприятия имеется 5 универсальных станков, ко­торые могут выполнять 4 вида работ. Каждую работу еди­новременно может выполнять только один станок, и каждый станок можно загружать только одной работой.

В таблице даны затраты времени при выполнении станком определенной работы.

Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты вре­мени.

Значения коэффициентов распределительной таблицы

6.17. Решить задачу о назначениях.

Служба занятости имеет в наличии четыре вакантных мес­та по разным специальностям, на которые претендуют шесть человек. Проведено тестирование претендентов, результаты которого в виде баллов представлены в матрице

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

Значения коэффициентов матрицы

6.18. Дана задача линейного программирования с двумя целе­выми функциями

Составить математическую модель нахождения компро­миссного решения и найти его (решение математической мо­дели рекомендуется проводить на персональном компьютере).

Значения коэффициентов целевой функции и системы ограничений

Матричная и развернутая формы задачи линейного программирования

ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

Кафедра «Математика и моделирование»

Методические указания и варианты индивидуальных заданий для студентов заочного факультета

Линейное программирование. Решение задачи. Методические указания и варианты индивидуальных заданий для студентов заочного факультета, – СПб.: Петербургский государственный университет путей сообщения, 2006, 22 с.

Содержание пособия соответствует разделам математического программирования, изучаемым студентами в 3 семестре. Пособие предназначено для студентов специальностей УПП заочного факультета ПГУПС.

Рецензент: профессор В.В. Гарбарук (кафедра «Высшая математика» ПГУПС)

© Петербургский государственный университет

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

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

Задача. Найти экстремум линейной функции F, если ее аргументы удовлетворяют некоторым ограничениям.

Настоящие методические указания посвящены анализу задачи линейного программирования, даны ее различные формы записи и указаны некоторые способы ее решения.

Каждый студент должен будет сделать для своей задачи все ниже перечисленные действия.

1. Записать задачу в матричной форме

2. Записать каноническую задачу.

3. Решить задачу геометрически.

4. Найти начальный базисный план с помощью искусственных переменных.

5. Решить задачу симплекс-методом.

6. Написать двойственную задачу к искомой в матричной и развернутой формах.

7. Найти решение двойственной задачи и доказать его оптимальность с помощью теоремы двойственности.

Варианты задач и пример решения указаны в конце этих указаний.

Матричная и развернутая формы задачи линейного программирования

В этом параграфе мы сравним две формы записи задачи линейного программирования.

Определение 1. Следующая задача называется стандартной задачей линейного программирования.

Задача 1. Найти

, (1)

, , (2)

где A – матрица системы ограничений, имеющая m строк и n столбцов, b – столбец из m элементов; c, x – столбцы из n элементов. Таким образом, эти матрицы имеют вид

, , , . (3)

В развернутой форме эта стандартная задача линейного программирования может быть записана в следующем виде.

Задача 1’. Найти максимум линейной функции

,

.

Определение 2. Решением этих задач называется матрица (упорядоченный набор чисел) , удовлетворяющая системе ограничений (2) и обеспечивающая максимальное значение функции (1). Иногда это решение называется оптимальным планом задачи. Значение функции на оптимальном плане обозначается .

Определение 3. Линейная функция F задачи 1 называется целевой функцией, а множество D решений системы (2) – множеством допустимых решений (планов) этой задачи.

Пример 1. Записать задачу линейного программирования (1), (2) с матрицами

; ; ;

в развернутой форме .

Решение. В развернутой форме задача формулируется следующим образом.

Найти максимум функции при ограничениях

.

Пример 2. Записать следующую задачу линейного программирования в матричной форме.

Минимизировать линейную функцию при ограничениях

.

Решение.Для того чтобы записать эту задачу в матричной форме (1, 2), изменим неравенства в ограничениях задачи так, чтоб они имели одинаковый знак. Для этого умножим первое неравенство на –1. Мы получим следующую систему ограничений задачи:

Тогда в матричной форме задача примет вид

,

, ,

; ; ; .

Ссылка на основную публикацию
Adblock
detector