Wyniki wyszukiwania - BazTech

1

A new geometric approach to multiobjective linear programming problems

Kaci Mustapha, Radjef Sonia

Mathematica Applicanda

|

2023

|

Vol. 51, no. 1

3--12

EN

This paper is a follow-up to a previous work where we developed a new geometric approach to sensitivity analysis. In this paper, we present a simple method to determine whether a given multiobjective linear programming problem (MOLPP) has an ideal solution (i.e. all of the objective functions are optimized simultaneously) without having to calculate the optimal value of each objective function. First, we divide the space of linear forms into a finite number of sets based on a fixed convex polygonal subset of R2 using an equivalency relationship. All the elements from a given equivalency class have the same optimal solution. Next, we characterize the equivalence classes of the quotient set using a geometric approach to sensitivity analysis. Finally, a numerical example is given to illustrate the method.

PL

W tym artykule przedstawiamy nową metodę rozwiązywania problemów programowania liniowego z wieloma celami (MOLPP), która eliminuje potrzebę obliczania optymalnej wartości każdej funkcji celu. Metoda ta jest kontynuacją naszych wcześniejszych prac dotyczących analizy wrażliwości, gdzie opracowaliśmy nowe podejście geometryczne. Pierwszym krokiem naszego podejścia jest podział przestrzeni form liniowych na skończoną liczbę zbiorów opartych na stałym wypukłym podzbiorze wielokąta R2. Dokonujemy tego za pomocą relacji równoważności, która zapewnia, że wszystkie elementy z danej klasy równoważności mają takie same rozwiązanie optymalne. Następnie charakteryzujemy klasy równoważności zbioru ilorazowego za pomocą podejścia geometrycznego do analizy wrażliwości. Ten krok jest kluczowy w identyfikacji rozwiązania idealnego dla MOLPP. Korzystając z tego podejścia, możemy określić, czy dana MOLPP ma rozwiązanie idealne, bez konieczności obliczania optymalnej wartości każdej funkcji celu. Jest to znacząca poprawa w stosunku do istniejących metod, ponieważ znacznie zmniejsza złożoność obliczeniową i czas wymagany do rozwiązania MOLPP. Aby zilustrować naszą metodę, przedstawiamy numeryczny przykład, który dowodzi jej skuteczności. Nasza metoda jest prosta, ale potężna i może być łatwo zastosowana do szerokiego zakresu MOLPP. Niniejsza praca przyczynia się do dziedziny optymalizacji poprzez przedstawienie nowego podejścia do rozwiązywania MOLPP, które jest wydajne, skuteczne i łatwe do zaimplementowania.

2

Optymalizacja kosztów transportu gazu skroplonego LNG pod względem lokalizacji magazynów na przykładzie Polski

Popławski Tomasz, Kurkowski Bartosz

Rynek Energii

|

2021

|

Nr 4

3--8

PL

Wielu ekspertów zarówno z Polski jak i UE jednoznacznie stwierdza, że Gazociąg Nordstream 2 zmniejsza bezpieczeństwo gazowe zarówno Polski jaki i państw z Europy środkowowschodniej. W związku z tym konieczne są różne przedsięwzięcia w celu dywersyfikacji dostaw gazu do Polski. Przy istniejącej i wciąż rozwijającej się infrastrukturze drogowej oraz kolejowej, jak również w obliczu istnienia terminali do odbioru gazu w Świnoujściu i Gdańsku, jednym z możliwych działań w tym kierunku jest budowa nowych magazynów lub rozbudowa starych w taki sposób, aby można było przewozić i przechowywać tam skroplony gaz LNG. Jednak, aby przedsięwzięcie to było opłacalne, lokalizacje tych magazynów muszą tak zostać dobrane, aby zminimalizować przyszłe koszty transportowe. W niniejszym artykule zaproponowano metodę opartą o programowanie liniowe, która pozwala na optymalną alokację magazynów LNG. Jej innowacyjnym względem istniejących metod elementem jest dynamicznie aktualizująca się waga dostawcy, w zależności od przypisanych do niego odbiorców. Dla zaprezentowanego przykładu zaproponowana metoda pozwoliła na zmniejszenie kosztów drogowych o ponad 25%.

EN

Many experts from both Poland and the EU clearly state that the Nordstream 2 gas pipeline reduces gas safety both in Poland and in Central and Eastern European countries. With the existing and still developing road and rail infrastructure, as well as the gas receiving terminals in Świnoujście and Gdańsk, one of the possible actions is the construction of new warehouses or expansion of old ones so that LNG can be transported and stored there. However, for this venture to be profitable, the locations of these warehouses must be selected to minimize future transport costs. This article proposes a method based on linear programming that allows for the optimal allocation of LNG storage facilities. Its innovative element compared to the existing methods is the dynamically updating weight of the supplier, depending on the recipients assigned to it. For the example shown, the proposed method allowed to reduce road costs by more than 25%.

3

Comparative Study of AMPL, Pyomo and JuMP Optimization Modeling Languages on a Network Linear Programming Problem Example

Karbowski Andrzej, Wyskiel Krzysztof

Pomiary Automatyka Robotyka

|

2021

|

R. 25, nr 3

23--30

EN

The purpose of this work is a comparative study of three languages (environments) of optimization modeling: AMPL, Pyomo and JuMP. The comparison will be based on three implementations of the shortest path problem formulated as a linear programming problem. The codes for individual models and differences between them will be presented and discussed. Various aspects will be taken into account, such as: simplicity and intuitiveness of implementation, availability of specific data structures for a LP network problems, etc.

PL

Celem pracy jest zbadanie i porównanie możliwości trzech języków (środowisk) modelowania optymalizacyjnego: AMPL, Pyomo i JuMP. Porównanie zostanie oparte na trzech implementacjach zadania najkrótszej ścieżki sformułowanego jako zadanie programowania liniowego. Przedstawione i omówione zostaną kody poszczególnych modeli oraz różnice między nimi. Pod uwagę będą brane różne aspekty, takie jak: prostota i intuicyjność implementacji, dostępność określonych struktur danych dla problemów z siecią LP itp.

4

A new geometric approach for sensitivity analysis in linear programming

Kaci Mustapha, Radjef Sonia

Mathematica Applicanda

|

2021

|

Vol. 49, no. 2

145--157

EN

The article presents a geometric method of sensitivity analysis in linear programming, which is a computationally practical way to study the behavior of an optimal solution to a linear programming problem. In this approach, we improve the implementation of the constraints, and then we formulate the problem of linear programming geometrically. In this way, we obtain a new, equivalent geometrical formulation of the problem for the sensitivity analysis using the concepts of affine geometry. It consists in entering the objective function coefficient vector in the polar coordinates and determining all angles for which the solution remains unchanged. The method is presented in detail and illustrated by a numerical example.

PL

W niniejszym artykule przedstawiamy nowe podejście geometryczne do analizy wrażliwości w programowaniu liniowym, które jest praktyczne obliczeniowo. Pozwala analizować zachowania optymalnego rozwi¡zania problemu programowania liniowego przy zmianach danych zadania. Najpierw ustalamy dopuszczalną dziedzinę (naprawiamy ograniczenia liniowe). Następnie geometrycznie formułujemy problem programowania liniowego. Nast¦pnie podajemy nowe równoważne sformułowanie geometryczne problemu analizy wrażliwości przy użyciu pojęć geometrii afinicznej. Piszemy wektor współczynników funkcji celu we współrzędnych biegunowych i wyznaczamy wszystkie kąty, dla których rozwiązanie pozostaje niezmienione. Proponowane podejście zostało szczegółowo przedstawione i zilustrowane przykładem liczbowym.

5

An example to illustrate several aspects of optimization theory in Managerial Economics

Lahiri Somdeb

Managerial Economics

|

2021

|

Vol. 22, no. 1

23--34

EN

We provide a single example that illustrates all aspects of linear, integer and dynamic programming, including such concepts such as value of perfect and imperfect information. Such problems, though extremely plausible and realistic are hardly ever discussed in managerial economics.

6

Optimum transportation of relief materials aftermath the disaster

Nautiyal A., Kumar A., Poddar A., Parajuli N.

Journal of Achievements in Materials and Manufacturing Engineering

|

2021

|

Vol. 109, nr 1

26--41

EN

Purpose: Natural disasters disrupt not only the lives of individuals but also the functioning of society. Given the unpredictability of disasters and the uncertainty associated with them, preparation is the best way to mitigate and reduce the effects of the disaster. Design/methodology/approach: The study presents a mathematical model in the form of a multi-objective linear programming problem for the relief distribution from the airports which minimizes the total operational cost as well as travel time. Further, the solution approach and analytical results have also been discussed. Findings: The main aims at the preparedness stage are to identify and build infrastructures that might function as useful operation centres during a disaster. The study also provides decisions that include the type and number of vehicles for each affected location. Research limitations/implications: Airports can function as centres for relief collection and distribution. However, relief operations carried out through airports are often subject to problems such as stockpiling. Further, various modes are available for the transport of relief supplies- air, water, and land transport modes primarily. While aircraft and helicopters are faster, their costs of operation are too high. Instead, trucks are economical but very slow as compared to aircraft. Practical implications: The choice of model depends on many factors including the availability of vehicles, availability of routes, and criticality of situations. The choices made in turn affect the costs and the time of operations. Originality/value: The model converts a disaster scenario into a demand-supply problem with the aim being to decide allocations at specified intervals of time.

7

Conditions and a computation method of the constrained regulation problem for a class of fractional-order nonlinear continuous-time systems

Si Xindong, Yang Hongli, Ivanov Ivan G.

International Journal of Applied Mathematics and Computer Science

|

2021

|

Vol. 31, no. 1

17--28

EN

The constrained regulation problem (CRP) for fractional-order nonlinear continuous-time systems is investigated. New existence conditions of a linear feedback control law for a class of fractional-order nonlinear continuous-time systems under constraints are proposed. A computation method for solving the CRP for fractional-order nonlinear systems is also presented. Using the comparison principle and positively invariant set theory, conditions guaranteeing positive invariance of a polyhedron for fractional-order nonlinear systems are established. A linear feedback controller model and the corresponding algorithm of the CRP for fractional nonlinear systems are also proposed by using the obtained conditions. The presented model of the CRP is formulated as a linear programming problem, which can be easily implemented from a computational point of view. Numerical examples illustrate the proposed method.

8

Risk management in the process of personnel allocation to jobs

Krynke Marek

System Safety : Human - Technical Facility - Environment

|

2020

|

Vol. 2, nr 1

82--99

EN

The strategy should be designed in such a way as the risk management can operate not only as a system for avoiding losses, but also risk management should allow recognizing and making use of occasions and create new opportunities for the organization. Risk management includes both an evaluation (analytical and evaluation) undertaking as well as planning and control activities aimed at minimizing (reducing) risk or maintaining it at an acceptable level. Security management can in particular be reduced to the issue of risk management, because risk is a quantitative expression of the functioning of systems in an environment where there are active sources of threats to system security. The article presents the problem of personnel allocation in hazardous conditions, emphasizing the possibilities of undertaking optimization actions in the safety management process. A mathematical model was formulated for this issue. An algorithm solving the problem of personnel allocation is presented. The proposed analysis is the starting point for determining the risk when using multi-station work.

9

Managing the effectiveness of machines during the assignment of tasks to the production

Krynke Marek

Quality Production Improvement - QPI

|

2020

|

Vol. 2, Iss. 1

188--196

EN

The allocation of production tasks to specific production resources is an important part of preparing the manufacturing process. The amount of profit and costs incurred depends on this division. The efficiency of production resources depends not only on the technologies used, but also on the tasks that will be carried out on them. Therefore, the management of machine efficiency includes both an evaluation (analytical and assessment undertaking, e.g. OEE) and planning activities aimed at maximizing the efficiency of machines by appropriately assigning production tasks to them. The article presents the problem of the allocation of production of various products to various production resources, including the efficiency of the use of machines and devices, emphasizing the possibilities of undertaking optimization actions in the cost management process. A mathematical model was formulated for this issue. An algorithm solving the problem of allocation of production tasks is presented. The solution was obtained using the Octave computing environment.

10

A linear programming methodology for approximate dynamic programming

Díaz Henry, Sala Antonio, Armesto Leopoldo

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 2

363--375

EN

The linear programming (LP) approach to solve the Bellman equation in dynamic programming is a well-known option for finite state and input spaces to obtain an exact solution. However, with function approximation or continuous state spaces, refinements are necessary. This paper presents a methodology to make approximate dynamic programming via LP work in practical control applications with continuous state and input spaces. There are some guidelines on data and regressor choices needed to obtain meaningful and well-conditioned value function estimates. The work discusses the introduction of terminal ingredients and computation of lower and upper bounds of the value function. An experimental inverted-pendulum application will be used to illustrate the proposal and carry out a suitable comparative analysis with alternative options in the literature.

11

Pipe-lining Dynamic Programming Processes in Order to Synchronize Energy Production and Consumption

Bendali Fariha, Quilliot Alain, Mole Kamga Eloise, Mailfert Jean, Toussaint Hélène

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

303--306

EN

Synchronizing heterogeneous processes remains a difficult issue in Scheduling area. Related ILP models are in trouble, because of large gaps induced by rational relaxation. We propose here a pipe-line decomposition of a dynamic programming process for energy production and consumption scheduling, and describe the way related sub-processes interact in order to achieve efficient synchronization.

12

An Experimental Study on Symmetry Breaking Constraints Impact for the One Dimensional Bin-Packing Problem

Hadj Salem Khadija, Kieffer Yann

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

317--326

EN

We consider the classical One-Dimensional Bin Packing Problem (1D-BPP), an NP-hard optimization problem, where, a set of weighted items has to be packed into one or more identical capacitated bins. We give an experimental study on using symmetry breaking constraints for strengthening the classical integer linear programming proposed to optimally solve this problem. Our computational experiments are conducted on the data-set found in BPPLib and the results have confirmed the theoretical results.

13

Heuristic method of assembly scheduling of multi-option products for assembly line with intermediate buffers

Magiera Marek

Technologia i Automatyzacja Montażu

|

2019

|

nr 3

4--10

EN

The method intended to build the possibly shortest assembly schedules is presented in the paper. The method is constructed for assembly lines without parallel machines. The intermediate buffers are located between the assembly machines. A flow of products of different types is unidirectional in the assembly line. The proposed method is a heuristic because the fixed tasks are characterized by a large size and considerable computational complexity. It is a relaxation heuristic. The linear mathematical model is used in the mentioned heuristic method. The method is constructed for assembly scheduling for multioption products. Assembly of various types of products in different variants is the reply to the contemporary challenges faced by the manufacturers, who try to satisfy the demands of individual customers. The planned downtimes of machines are regarded in the method, for example downtime of machines connected with maintenance. The results of computational experiments with proposed heuristic method are presented. The described heuristic method is compared with optimal method based on the integer programming. The fixed makespans and computational fixed times using heuristic method and optimal method are compared.

PL

Przedstawiono metodę przeznaczoną do budowy najkrótszych harmonogramów montażu produktów w liniach montażowych bez maszyn równoległych. Konfiguracja linii montażowej uwzględnia obecność buforów międzyoperacyjnych pomiędzy maszynami. Przepływ równocześnie montowanych produktów różnych typów jest jednokierunkowy. Ze względu na rozmiary rozwiązywanych problemów i związaną z tym złożoność obliczeniową metoda jest heurystyką. Jest to heurystyka relaksacyjna, w której wykorzystano model zadania programowania liniowego. Metoda dotyczy produktów wielowariantowych. Produkty danego typu mogą różnić się wariantami wykonania - specyficznymi cechami, uwzględniającymi wymagania odbiorców. Metodę wyróżnia także uwzględnienie planowanych przestojów maszyn, np. przeznaczonych na konserwację. Zaprezentowano wyniki eksperymentów obliczeniowych, za pomocą których oceniono jakość opracowanej metody. Długości harmonogramów wyznaczanych za pomocą przedstawionej metody porównano z długościami harmonogramów optymalnych, znanymi dzięki zastosowaniu modelu zadania programowania całkowitoliczbowego. Porównano także czasochłonność obliczeń.

14

Analysis of the problem of staff allocation to work stations

Krynke Marek, Mielczarek Krzysztof, Vaško Alan

Quality Production Improvement - QPI

|

2019

|

Vol. 1, Iss. 1

545--550

EN

The proper organization of work is to set the workflow to the slightest effort of man and machine operation to obtain maximum results. The article presents the problem of the allocation of personnel that occurs in a real company. The mathematical model for this issue was formulated. An algorithm solving the problem of personnel allocation is presented. The proposed analysis is a starting point for determining the production capacity and load of each workstation, which is particularly important when using multi-station work and balancing the production line.

15

Zarządzanie zadaniami pracowników w branży budowlanej

Krynke Marek

Budownictwo o Zoptymalizowanym Potencjale Energetycznym

|

2019

|

Vol. 8 Nr 1

137--145

PL

Właściwa organizacja pracy polega na takim ustawieniu przebiegu pracy, aby przy najmniejszym nakładzie pracy człowieka lub urządzeń uzyskiwać maksymalne rezultaty działania. Artykuł prezentuje problem przydziału personelu, który występuje w rzeczywistej firmie świadczącej usługi budowlane. Sformułowano model matematyczny dla tego zagadnienia. Przedstawiono algorytm rozwiązujący problem alokacji personelu. Zaproponowana analiza stanowi punkt wyjścia do określenia możliwości usługowych oraz obciążenia każdego pracownika, co jest szczególnie istotne w przypadku stosowania pracy wielostanowiskowej.

EN

The proper organization of work is to set the workflow to the slightest effort of man and machine operation to obtain maximum results. The article presents the problem of the allocation personnel, that occurs in a real company that provides construction services. The mathematical model for this issue was formulated. An algorithm solving the problem of personnel allocation is presented. The proposed analysis is a starting point for determining the production capacity and load of each workstation, which is particularly important when using multi-station work.

16

A novel integer linear programming model for routing and spectrum assignment in optical networks

Hadhbi Youssouf, Kerivin Hervé, Wagler Annegret

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

127--134

EN

The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years. Existing integer linear programming models for the problem are either very complex and suffer from tractability issues or are simplified and incomplete so that they can optimize only some objective functions. The majority of models uses edge-path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. An alternative is to use edge-node formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance. However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions. Our contribution is to provide the first complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model. Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t. several objective functions. We further devise some directions of future research.

17

A Minimum set-cover problem with several constraints

Dörpinghaus Jens, Düing Carsten, Weil Vera

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

115--122

EN

A lot of problems in natural language processing can be interpreted using structures from discrete mathematics. In this paper we will discuss the search query and topic finding problem using a generic context-based approach. This problem can be described as a a Minimum Set Cover Problem with several constraints. The goal is to find a minimum covering of documents with the given context for a fixed weight function. The aim of this problem reformulation is a deeper understanding of both the hierarchical problem using union and cut as well as the non-hierarchical problem using the union. We thus choose a modeling using bipartite graphs and suggest a novel reformulation using an integer linear program as well as novel graph-theoretic approaches.

18

Kaskadowy model cenowy wspomagający procesy decyzyjne przy wykorzystaniu metod programowania liniowego

Senczyna K.

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2018

|

z. 127

231--241

PL

W artykule omawiana jest możliwość wykorzystania metod programowania liniowego w sytuacji, gdy w danym przedsiębiorstwie jest wdrożony kaskadowy model cenowy. Dzięki strukturze liniowej kaskadowego modelu pojawia się możliwość wprowadzenia metod programowania liniowego w optymalizacje procesów decyzyjnych dotyczących wyznaczania odpowiedniej ceny kontraktów. Optymalizowane są te elementy proces decyzyjnego, dla których jest możliwe zdefiniowanie poziomu ograniczeń zasobów. Funkcja celu jest zbudowana w oparciu o wartość parametru Pocket Margin zdefiniowanego w kaskadowym modelu cenowym, jako wartość wyliczająca wynik ekonomiczny dla danej transakcji. Przygotowane i wyliczone rozwiązanie programu liniowego jest wyłącznie propozycją dla kadry menadżerskiej, mająca na celu wspieranie procesu decyzyjnego dodatkowymi informacjami.

EN

The article discusses the possibility of using linear programming methods in a situation where a cascaded pricing model is implemented in a given company. Thanks to the linear structure of the cascading model, there is the possibility of introducing linear programming methods into optimization of decision-making processes concerning determining the appropriate price of contracts. These elements of the decision process are optimized for which it is possible to define the level of resource constraints. The goal function is built based on the value of the Pocket Margin parameter defined in the cascaded pricing model, as the value calculating the economic result for a given transaction. The prepared and calculated solution of the linear program is only a proposal for the managerial staff, aimed at supporting the decision-making process with additional information.

19

Application of optimization methods in planning of patients accommodation in the spa companies

Szromek A. R.

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2018

|

z. 119

289--300

EN

The aim of the article is to present the possibilities of using selected optimization methods to planning accommodation in spa establishments. Therefore, two methods of solving problems in the field of linear programming were used. The first is the north-west angle method, and the second is the Vogel's approximation method. The methods used so far in logistics in the field of planning a production program can be effectively used also in spa services and improving the efficiency of business models of spa enterprises.

20

A software program for optimal 1D cutting suport

Pacek M., Horla D.

Studia z Automatyki i Informatyki

|

2018

|

T. 43

95--107

EN

The paper summarizes the procedure of solving 1D optimal cutting problems, giving details of coding it using dynamic programming, knapsack problem formulation and column generation approach. Finally, the software program for optimal 1D cutting support is described, which is the open code version enabling researchers to extent its capabilities. The paper ends by giving solutions to stated problems and the description of the GUI of the program. At the end of the paper, the reference to the other paper of the authors discussing the effectiveness of the proposed solution is given, tightly connected with this paper.

PL

W artykule przedstawiono procedurę rozwiązywania zadania optymalizacji docinania 1D, włączając szczegóły zakodowania algorytmu przy użyciu programowania dynamicznego, formalizmu zadania plecakowego oraz metody generowania kolumn. W końcu, opisano program wspomagania optymalnego docinania, w postaci programu w otwartym kodzie co pozwoli badaczom na jego dalsze rozwijanie. Artykuł zawiera rozwiązania przykładowych zadań optymalizacji, jak i też opis interfejsu użytkownika. Zawarto również odnośnik do drugiego artykułu autorów, przedstawiającego efektywność zastosowanych metod.