Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 21
Текст из файла (страница 21)
Заменяем в базисе вектор а' на вектор а и для нового базиса строим третью симплексную таблицу: Вектор Ь > О, поэтому точка х = (О, г, 55, т, 0,0) является решением вспомогательной задачи и Я,„= О. Перейдем к решению основной задачи. Составим первую симплексную таблицу для начальной крайней точки х=(0,— г',ф,— г).
Разложения векторов х,а по базису а,а,а берем из последней симплексной з таблицы: Разрешающим столбцом является столбец а', разрешающая строка а4. Заменяем в базисе вектор а' на вектор а' и лля нового базиса строим вторую симплексную таблицу: 44. Методы нахождения начальной крайней точки Вектор Ь > О, поэтому точка х = (-, -, 5,0) является решением 5 5 5 исходной залечи и Я„„„= 15. Пример 2.
Решить методом искусственного базиса задачу: Решение. Рассмотрим вспомогательную задачу, добавляя искусствен- НЫЕ ПЕРЕМЕННЫЕ Х4, Хз. Исходная крайняя точка й = (О, О, 5, 3, 4). Базисные векторы а = (1,О, 0), ,4 (010) 5 Составим первую симплексную таблицу для вспомогательной задачи: 119 Глава 2. Линейное программирование 2х, + Зхз + хз + 2х4 < 30, 4хз + 2хз + хз + 2х4 ~ (40, хз + 2хз + Зхз + ха < 25.
Разрешающий столбец а, разрешающая строка а'. Заменяем в базисе вектор а на вектор а и лля нового базиса строим вторую 5 з симплексную таблицу: Во второй симплексной таблице разрешающий столбец а', разрешающая строка а . Заменяем в базисе вектор искусственных перемен- 4 ных а на вектор а и для нового базиса строим третью симплексную 4 з таблицу: Вектор гз > О, поэтому точка х = (-',;, -,0,0) является решением вспомогательной задачи с добавленными искусственными переменными, иЯ =О. Перейдем к решению основной задачи. Составим первую симплексную таблицу для начальной крайней точки х = (-,', —, 5). Разложения вектора х по базису а, а, аз берем из последней симплексной таблицы: з $4.
Методы нахождения начальной крайней точки Вектор зЗ > О, поэтому точка й = (з,—,3) является решением IЗ 2 Зз исходной задачи и Я = -2 Заметим, что на самом деле исходная задача тривиально решается, так как мы имеем систему из трех линейных уравнений с тремя /! 2 7ъ неизвестными. И зта система имеет единственное решение х = (-, з, -). /7ример 3. Решить, вводя искусственные переменные задачу; 2х, + хз+ Зхз+ 5х4 — гпах; х; > О, з = 1,2,3,4, добавив неотрицательные переменные хз,хмхз, получим задачу в канонической форме: 2х~+хз+Зхз+5х4- шах; хз >О, з= 1,...,7, 2х~ + Зхз + хз + 2х4+ хз =- 30, 4х~+2хз+ хз +2хз +ха — — 40, хз + 2хз + Зхз + х4 + хз = 25. Исходная крайняя точка х = (0,0,0,0,30,40,25).
Базисные векторы а = (1, О, 0), а = (О, 1, 0), аз = (О, О, 1) . Составим первую симплексную таблицу: 121 6 4. Методы нахождения начальной крайней точки 120 Глава ?. Линейное программирова вне 4.4. Задачи Задачи линейного программирования в канонической форме с не- заданной первоначальной крайней точкой. Решить методом искус- ственного базиса.
х,>0, 5=1,2,3, х~ + 4хз + хз -а шах; 4.1. х~ — хз + хз = 3, 2х| — 5хз хз = О. х,>0, 5=1,2,3, х, — !Охз + хз - гпах; 4.2. х, — 5,5хз — 7хз = — 13, х ~ — 14, 5хз + 7хз = 15. х!+ 2хз + Зхз — 4Х4 -~так; ха>0, 5=1,2,3,4, 4.3. х1+ хз — хз + х4 = 2, х~ + 14хз + 10хз — 10х4 = 24. а = 1,2,3,4, ха >О, х, — 5хз — хз + Х4 — шах; 4.4. х~ + Зхз + Зхз + Х4 = 3, 2х1 + хз — Х4 = 4.
= 1,2,3,4, х; ~ ~О, х~ + хз + хз + Х4 — пзах; 4.5. 4х~ + 2хз + 5хз — х4 = 5, 5х1 + Зх + бхз — 2х4 = 5, Зх~ + 2хз+4хз — х4 = 4. 1,2,3,4, х; > О, х, +10хз — хз +5ха 4.6. х + 2хз — хз — ха -х, + 2хз +Зхз+ ха х| + 5хз + хз — ха 5=1,...,5, з:,>О, х~ + 2хз 4.7 з бх~ Х~ + Хз х, > О, а = 1,..., 5, +хз — хз + ха + а:з+ хз + х4 + хз + 2хз + Зх4 + хз + Зхз + бха ха > О, а = 1, 6, — 4хз + хз + — 14х5 + ! 2хз + хз + 2хз — !бхз + 8хз + В первой симплексной таблице разрешающим столбцом является столбец а, Разрешающая строка аз, ! = 15.
Заменяем в базисе вектор а на вектор а и для нового базиса строим вторую симплексную таблицу: Во второй симплексной таблице разрешающий столбец а, разрешающая строка аз, 4 = 4. Заменяем в базисе вектор а на вектор а и для нового базиса строим третью симплексную таблицу для базиса аа, ва, а: Вектор 45 > О, поэтому крайняя точка х = (0,0,4,13,0,10,0) является решением расширенной задачи, а решением искодной задачи является точка й = (0,0,4,13), Я,„= 77. х~ 48 Зх| бх, 1Ох, х, 14Х~ х~ 16х~ + Зхз+4ха + хз — 2ха + хз — 2ха — 2ха > знал; = 1, =2, = 5. + 5хз - шал; + 7хз — — 2, +7хз =2, + 7х5 — 2хз- шах; — 2хз = 1О, — 4хз = 20, — 7хз = 30.
Ха + Хз + Хб 5Х4 + бхз + Зха + Х5 7х4 + 4хз+ 5ха так; 8, О, 12. !2З б 5. т)увнсввргявя задача Глава 2. Лввейвое программирование 122 5 5. Транспортная задача 5.1. Постановка задачи и! и ~~у а, =,~ 6, =М. у=! у=! х! <ау, Е у = 1,...,пу, у=! т и с; хц — пцп; у=! у=! >О, 2=1,...,пт, (с, х): = 1,...,п, =а„у=!,...,гп, и ~~у х! у=! пу х, (а) (Ь) =6, 2 =1,...,п.
неравенствами имеют вид; *;. < Ьуэ у' = 1,..., п, Е- 2 !! хп а! у22 у=! х!л Ху! хп апю ь, Важный частный случай задач линейного программирования транспортные залачи. Зто математические модели разнообразных прикладных задач по оптимизации перевозок.
В этом параграфе мы приведем постановку транспортной задачи, методы отыскания исходной крайней точки, решение залачи методом потенциалов, двойственную к транспортной задаче, обоснование метода потенциалов, задачу о назначении, примеры. Гралслортлой зидочей ло критерию стоимости называется следующая задача о минимизации стоимости перевозок.
Пусть в пунктах отправления А!,..., А сосредоточено соответственно а„...,а единиц некоторого однородного груза. Зтот груз следует перевезти в п пунктов назначения В„...,В„, причем в каждый из них наале:кит завезти соответственно 6!,...,Ь„единиц груза. Стоимость перевозки единицы груза из пункта А! в пункт В равна с;.. Обозначая через х; количество единиц груза, предназначенного к отправке из пункта А, в пункт Ву, получим задачу нахождения плана перевозок, при котором общая стоимость окажется минимальной: В матричном виде ограничения задачи (а) — (Ь) ! ! ... 1 0 0 ...
0 ... 0 0 .. 0 0 0 ... 0 ! 1 ... 1 ... 0 0 ... 0 0 0 ... 0 0 0 ... 0 ... 1 1 ... 1 ! О ... 0 1 0 ... 0 ... 1 0 ... 0 0 ! ... 0 0 1 ... 0 ... 0 1 ... 0 0 0 ... ! 0 О ... 1 ... 0 0 ... 1 План перевозок и стоимость перевозок представляются в виде векторов х = (хб, ! пп 1,..., пу, !' = 1,...,п), с = (с;у, у пп 1,..., пт, 2 = 1, ..., п) с!!ответственно илн матриц Х = (хуу)ю=!,,т, С = (су)г=!, т.
Уравнения (а) означают, что из пункта отправления А! весь груз вывезен в пункты назначения (потребления). Уравнения (Ь) означают, что количество груза. завезенного в пункт В со всех пунктов отправления, соответствует требуемому. Естественно считать, что общий запас груза на всех пунктах отправления равен суммарной потребности всех пунктов назначения, т,е.
В этом случае говорят, что имеется замклутоя модель транспортной задачи. Если суммарные запасы отправителей больше суммарной потребноп1 и сти пунктов назначения, т. е. 2, а! > 2 Ь, то равенства (а) заменяются у=! у=! неравенствами а условие (Ь) остается без изменений. В этом случае вводится фиктивный пг и пункт назначения Впе! с требуемой величиной завоза Ь„е, = 2; а! — 2; Ьу у=! у=! и нулевыми стоимостями перевозок в этот пункт. Добавляя новые неотрицательные переменные хт„+ !, у = 1,..., тп, приходим к замкнутой модели транспортной задачи с ограничениями в виде равенств (а) — (Ь). Если суммарные запасы отправителей меньше суммарных запросов п3 и пунктов назначения, т.е.
2,'а, < 2 Ь, то равенства (Ь) заменяются т=! у=! а условие (а) остается без изменений. В этом случае вводится фиктивный и пункт отправления А +! с требуемой величиной вывоза а +, — — 2 6— у=! 2 ат и нулевыми стоимостями перевозок из этого пункта. Добавляя у=! новые неотрицательные переменные х !.!;, у = 1,...,и, приходим к замкнутой модели транспортной задачи с ограничениями в виде равенств (а)-(Ь). 125 $5. Траиеяортяая задача Глава 2.
Ляеейиое ирограммироваиие 124 5.2. Особенностн задача Доказательство. выполняться: и н хб = Транспортная задача является задачей линейного программирования и может быть решена симплекс-методом, который значительно упрощается в зилу простого строения системы ограничений (а)-(Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
